Recent questions tagged kenneth-rosen / GATE Overflow for GATE CSE

1 votes

2 answers

451

Kenneth Rosen Edition 7 Exercise 6.1 Question 1 (Page No. 396)
There are $18$ mathematics majors and $325$ computer science majors at a college. In how many ways can two representatives be picked so that one is a mathematics major and the other is a computer science major? In how many ways can one representative be picked who is either a mathematics major or a computer science major?

There are $18$ mathematics majors and $325$ computer science majors at a college.In how many ways can two representatives be picked so that one is a mathematics major and...

admin

6.9k views

admin asked Apr 23, 2020

1 votes

2 answers

452

Kenneth Rosen Edition 7 Exercise 2.5 Question 40 (Page No. 177)
Show that if $S$ is a set, then there does not exist an onto function $f$ from $S$ to $P(S),$ the power set of $S$. Conclude that $\mid S\mid < \mid P(S)\mid .$ This result is known as Cantor's theorem. [Hint: Suppose such a function ... $s$ can exist for which $f (s) = T.]$

Show that if $S$ is a set, then there does not exist an onto function $f$ from $S$ to $P(S),$ the power set of $S$. Conclude that $\mid S\mid < \mid P(S)\mid .$ This res...

admin

660 views

admin asked Apr 21, 2020

0 votes

0 answers

453

Kenneth Rosen Edition 7 Exercise 2.5 Question 39 (Page No. 177)
We say that a function is computable if there is a computer program that finds the values of this function. Use question $37$ and $38$ to show that there are functions that are not computable.

We say that a function is computable if there is a computer program that finds the values of this function. Use question $37$ and $38$ to show that there are functions th...

admin

251 views

admin asked Apr 21, 2020

1 votes

1 answer

454

Kenneth Rosen Edition 7 Exercise 2.5 Question 38 (Page No. 177)
Show that the set of functions from the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is uncountable. [Hint: First set up a one-to-one correspondence between the set of real numbers between $0$ and $1$ and a subset of ... to the real number $0.\:d_{1}d_{2} \dots d_{n}\dots $ the function $f$ with $f (n) = dn.]$

Show that the set of functions from the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is uncountable. [Hint: First set up a one-to-one correspondence be...

admin

710 views

admin asked Apr 21, 2020

0 votes

0 answers

455

Kenneth Rosen Edition 7 Exercise 2.5 Question 37 (Page No. 177)
Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought of as a string of symbols from a finite alphabet.]

Show that the set of all computer programs in a particular programming language is countable. [Hint: A computer program written in a programming language can be thought o...

admin

269 views

admin asked Apr 21, 2020

0 votes

0 answers

456

Kenneth Rosen Edition 7 Exercise 2.5 Question 36 (Page No. 177)
Show that there is a one-to-one correspondence from the set of subsets of the positive integers to the set real numbers between $0$ and $1$. Use this result and question $34$ and $35$ to conclude that $ℵ_{0} < \mid P(Z^{+})\mid =\mid R\mid.\:[$Hint: Look at the first part of the hint for Exercise $35.]$

Show that there is a one-to-one correspondence from the set of subsets of the positive integers to the set real numbers between $0$ and $1$. Use this result and question ...

admin

257 views

admin asked Apr 21, 2020

0 votes

0 answers

457

Kenneth Rosen Edition 7 Exercise 2.5 Question 35 (Page No. 177)
Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one-to-one correspondence. Represent a subset of the set of ... $ith$ string in the list. Show that this new bit string cannot appear in the list.]

Show that there is no one-to-one correspondence from the set of positive integers to the power set of the set of positive integers. [Hint: Assume that there is such a one...

admin

244 views

admin asked Apr 21, 2020

0 votes

0 answers

458

Kenneth Rosen Edition 7 Exercise 2.5 Question 34 (Page No. 177)
Show that $(0, 1)$ and $R$ have the same cardinality. [Hint: Use the Schröder-Bernstein theorem.]

Show that $(0, 1)$ and $R$ have the same cardinality. [Hint: Use the Schröder-Bernstein theorem.]

admin

194 views

admin asked Apr 21, 2020

0 votes

0 answers

459

Kenneth Rosen Edition 7 Exercise 2.5 Question 33 (Page No. 177)
Use the Schröder-Bernstein theorem to show that $(0, 1)$ and $[0, 1]$ have the same cardinality.

Use the Schröder-Bernstein theorem to show that $(0, 1)$ and $[0, 1]$ have the same cardinality.

admin

199 views

admin asked Apr 21, 2020

0 votes

0 answers

460

Kenneth Rosen Edition 7 Exercise 2.5 Question 32 (Page No. 177)
Show that when you substitute $(3n + 1)^{2}$ for each occurrence of $n$ and $(3m + 1)^{2}$ for each occurrence of m in the right-hand side of the formula for the function $f (m, n)$ in question $31,$ you ... $Q \times Q \rightarrow Q.$

Show that when you substitute $(3n + 1)^{2}$ for each occurrence of $n$ and $(3m + 1)^{2}$ for each occurrence of m in the right-hand side of the formula for the function...

admin

197 views

admin asked Apr 21, 2020

0 votes

0 answers

461

Kenneth Rosen Edition 7 Exercise 2.5 Question 31 (Page No. 177)
Show that $Z^{+} \times Z^{+}$ is countable by showing that the polynomial function $f : Z^{+} \times Z^{+}\rightarrow Z^{+}$ with $f(m, n) = \dfrac{(m + n − 2)(m + n − 1)}{2} + m$ is one-to one and onto.

Show that $Z^{+} \times Z^{+}$ is countable by showing that the polynomial function $f : Z^{+} \times Z^{+}\rightarrow Z^{+}$ with $f(m, n) = \dfrac{(m + n − 2)(m + n �...

admin

222 views

admin asked Apr 21, 2020

0 votes

0 answers

462

Kenneth Rosen Edition 7 Exercise 2.5 Question 30 (Page No. 177)
Show that the set of real numbers that are solutions of quadratic equations $ax^{2} + bx + c = 0,$ where $a, b,$ and $c$ are integers, is countable.

Show that the set of real numbers that are solutions of quadratic equations $ax^{2} + bx + c = 0,$ where $a, b,$ and $c$ are integers, is countable.

admin

214 views

admin asked Apr 21, 2020

0 votes

0 answers

463

Kenneth Rosen Edition 7 Exercise 2.5 Question 29 (Page No. 177)
Show that the set of all finite bit strings is countable.

Show that the set of all finite bit strings is countable.

admin

156 views

admin asked Apr 21, 2020

0 votes

0 answers

464

Kenneth Rosen Edition 7 Exercise 2.5 Question 28 (Page No. 177)
Show that the set $Z^{+} \times Z^{+}$ is countable.

Show that the set $Z^{+} \times Z^{+}$ is countable.

admin

170 views

admin asked Apr 21, 2020

0 votes

0 answers

465

Kenneth Rosen Edition 7 Exercise 2.5 Question 27 (Page No. 177)
Show that the union of a countable number of countable sets is countable.

Show that the union of a countable number of countable sets is countable.

admin

196 views

admin asked Apr 21, 2020

0 votes

0 answers

466

Kenneth Rosen Edition 7 Exercise 2.5 Question 26 (Page No. 177)
Use question $25$ to provide a proof different from that in the text that the set of rational numbers is countable. [Hint: Show that you can express a rational number as a string of digits with a slash and possibly a minus sign.]

Use question $25$ to provide a proof different from that in the text that the set of rational numbers is countable. [Hint: Show that you can express a rational number as ...

admin

258 views

admin asked Apr 21, 2020

0 votes

0 answers

467

Kenneth Rosen Edition 7 Exercise 2.5 Question 25 (Page No. 177)
Prove that if it is possible to label each element of an infinite set $S$ with a finite string of keyboard characters, from a finite list characters, where no two elements of $S$ have the same label, then $S$ is a countably infinite set.

Prove that if it is possible to label each element of an infinite set $S$ with a finite string of keyboard characters, from a finite list characters, where no two element...

admin

245 views

admin asked Apr 21, 2020

0 votes

0 answers

468

Kenneth Rosen Edition 7 Exercise 2.5 Question 24 (Page No. 177)
Show that there is no infinite set $A$ such that $\mid A \mid < \mid Z^{+} \mid = ℵ_{0}.$

Show that there is no infinite set $A$ such that $\mid A \mid < \mid Z^{+} \mid = ℵ_{0}.$

admin

195 views

admin asked Apr 21, 2020

0 votes

0 answers

469

Kenneth Rosen Edition 7 Exercise 2.5 Question 23 (Page No. 177)
Show that if $A$ is an infinite set, then it contains a countably infinite subset.

Show that if $A$ is an infinite set, then it contains a countably infinite subset.

admin

205 views

admin asked Apr 21, 2020

0 votes

0 answers

470

Kenneth Rosen Edition 7 Exercise 2.5 Question 22 (Page No. 177)
Suppose that $A$ is a countable set. Show that the set $B$ is also countable if there is an onto function $f$ from $A$ to $B.$

Suppose that $A$ is a countable set. Show that the set $B$ is also countable if there is an onto function $f$ from $A$ to $B.$

admin

218 views

admin asked Apr 21, 2020

0 votes

0 answers

471

Kenneth Rosen Edition 7 Exercise 2.5 Question 21 (Page No. 177)
Show that if $A, B,$ and $C$ are sets such that $\mid A\mid \leq \mid B \mid $ and $\mid B \mid \leq \mid C\mid ,$ then $\mid A\mid \leq \mid C \mid .$

Show that if $A, B,$ and $C$ are sets such that $\mid A\mid \leq \mid B \mid $ and $\mid B \mid \leq \mid C\mid ,$ then $\mid A\mid \leq \mid C \mid .$

admin

187 views

admin asked Apr 21, 2020

0 votes

0 answers

472

Kenneth Rosen Edition 7 Exercise 2.5 Question 20 (Page No. 177)
Show that if $\mid A \mid = \mid B \mid $ and $\mid B \mid = \mid C\mid ,$ then $\mid A\mid =\mid C\mid .$

Show that if $\mid A \mid = \mid B \mid $ and $\mid B \mid = \mid C\mid ,$ then $\mid A\mid =\mid C\mid .$

admin

187 views

admin asked Apr 21, 2020

0 votes

0 answers

473

Kenneth Rosen Edition 7 Exercise 2.5 Question 19 (Page No. 177)
Show that if $A, B, C,$ and $D$ are sets with $ \mid A \mid = \mid B\mid $ and $\mid C\mid =\mid D\mid ,$ then $\mid A \times C \mid = \mid B \times D\mid .$

Show that if $A, B, C,$ and $D$ are sets with $ \mid A \mid = \mid B\mid $ and $\mid C\mid =\mid D\mid ,$ then $\mid A \times C \mid = \mid B \times D\mid .$

admin

196 views

admin asked Apr 21, 2020

0 votes

0 answers

474

Kenneth Rosen Edition 7 Exercise 2.5 Question 18 (Page No. 177)
Show that if $A$ and $B$ are sets $\mid A \mid = \mid B \mid ,$ then $\mid P(A) \mid = \mid P(B)\mid.$

Show that if $A$ and $B$ are sets $\mid A \mid = \mid B \mid ,$ then $\mid P(A) \mid = \mid P(B)\mid.$

admin

178 views

admin asked Apr 21, 2020

0 votes

0 answers

475

Kenneth Rosen Edition 7 Exercise 2.5 Question 17 (Page No. 176)
If $A$ is an uncountable set and $B$ is a countable set, must $A − B$ be uncountable?

If $A$ is an uncountable set and $B$ is a countable set, must $A − B$ be uncountable?

admin

255 views

admin asked Apr 21, 2020

0 votes

0 answers

476

Kenneth Rosen Edition 7 Exercise 2.5 Question 16 (Page No. 176)
Show that a subset of a countable set is also countable.

Show that a subset of a countable set is also countable.

admin

182 views

admin asked Apr 21, 2020

0 votes

0 answers

477

Kenneth Rosen Edition 7 Exercise 2.5 Question 15 (Page No. 176)
Show that if $A$ and $B$ are sets, $A$ is uncountable, and $A \subseteq B,$ then $B$ is uncountable

Show that if $A$ and $B$ are sets, $A$ is uncountable, and $A \subseteq B,$ then $B$ is uncountable

admin

201 views

admin asked Apr 21, 2020

0 votes

0 answers

478

Kenneth Rosen Edition 7 Exercise 2.5 Question 14 (Page No. 176)
Show that if $A$ and $B$ are sets with the same cardinality, then $\mid A \mid \leq \mid B \mid $ and $\mid B \mid \leq \mid A\mid.$

Show that if $A$ and $B$ are sets with the same cardinality, then $\mid A \mid \leq \mid B \mid $ and $\mid B \mid \leq \mid A\mid.$

admin

193 views

admin asked Apr 21, 2020

0 votes

0 answers

479

Kenneth Rosen Edition 7 Exercise 2.5 Question 13 (Page No. 176)
Explain why the set $A$ is countable if and only if $\mid A \mid \leq \mid Z^{+}\mid.$

Explain why the set $A$ is countable if and only if $\mid A \mid \leq \mid Z^{+}\mid.$

admin

181 views

admin asked Apr 21, 2020

0 votes

0 answers

480

Kenneth Rosen Edition 7 Exercise 2.5 Question 12 (Page No. 176)
Show that if $A$ and $B$ are sets and $A \subset B$ then $\mid A \mid \leq \mid B\mid.$

Show that if $A$ and $B$ are sets and $A \subset B$ then $\mid A \mid \leq \mid B\mid.$

admin

170 views

admin asked Apr 21, 2020

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true