# Recent questions tagged set-theory&algebra

1
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 $f$ existed. Let $T = \{s \in S \mid s \notin f (s)\}$ and show that no element $s$ can exist for which $f (s) = T.]$
2
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.
3
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 these functions. Do this by associating to the real number $0.\:d_{1}d_{2} \dots d_{n}\dots$ the function $f$ with $f (n) = dn.]$
4
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.]
5
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.]$
6
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 positive integers as an infinite bit string with ... complement of the $ith$ bit of the $ith$ string in the list. Show that this new bit string cannot appear in the list.]
7
Show that $(0, 1)$ and $R$ have the same cardinality. [Hint: Use the Schröder-Bernstein theorem.]
8
Use the Schröder-Bernstein theorem to show that $(0, 1)$ and $[0, 1]$ have the same cardinality.
9
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 obtain a one-to-one polynomial function $Z \times Z \rightarrow Z.$ It is an open question whether there is a one-to-one polynomial function $Q \times Q \rightarrow Q.$
10
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.
11
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.
12
Show that the set of all finite bit strings is countable.
13
Show that the set $Z^{+} \times Z^{+}$ is countable.
14
Show that the union of a countable number of countable sets is countable.
15
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.]
16
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.
17
Show that there is no infinite set $A$ such that $\mid A \mid < \mid Z^{+} \mid = ℵ_{0}.$
18
Show that if $A$ is an infinite set, then it contains a countably infinite subset.
19
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.$
20
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 $\mid A \mid = \mid B \mid$ and $\mid B \mid = \mid C\mid ,$ then $\mid A\mid =\mid C\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 .$
Show that if $A$ and $B$ are sets $\mid A \mid = \mid B \mid ,$ then $\mid P(A) \mid = \mid P(B)\mid.$