Main: |
Index |

Previous: |
1.1 Sets and Functions |

Next: |
1.3 Ordinal Sets and Ordinal Numbers |

Theorem 1

Every subset of a countable set is countable.

Let $A$ be countable, with elements $a_1, a_2, \ldots,$ and let $B$ be a subset of $A$. Among the elements $a_1, a_2, \ldots,$ let $a_{n_1}, a_{n_2},\ldots$ be those in the set $B$. If the set of numbers $n_1, n_2, \ldots$ has a largest number, then $B$ is finite. Otherwise $B$ is countable with correspondence $i\leftrightarrow a_{n_i}$.

■

Theorem 2

The union of a finite or countable number of countable sets $A_1, A_2,\ldots$ is itself countable.

Theorem 3

Every infinite set has a countable subset.

Let $M$ be an infinite set and $a_1$ any element of $M$. Being infinite, $M$ contains an element $a_2$ distinct from $a_1$, and element $a_3$ distinct from $a_1$ and $a_2$, and so on. Continuing this process we get a countable subset $$ A = \{a_1, a_2,\ldots, a_n,\ldots\} $$ of the set $M$.

■

Definition

Two sets $M$ and $N$ are said to be

Theorem 4

Every infinite set is equivalent to one of its proper subsets.

According to Theorem 3, any infinite set $M$ contains a countable subset: $$ A = \{a_1, a_2,\ldots, a_n,\ldots\}, $$ and partition $A$ into two countable subsets. $$ A_1 = \{a_1, a_3, a_5, \ldots\}, \quad A_2 = \{a_2, a_4, a_6, \ldots\}. $$ Obviously, we can establish a one-to-one correspondence between the countable sets $A$ and $A_1$ with $a_n\leftrightarrow a_{2n-1}$. This correspondence can be extended to a one-to-one correspondence between the sets $A\cup(M-A) = M$ and $A_1\cup(M-A) = M - A_2$ by simply assigning $x$ itself to each element $x\in M-A$. But $M-A_2$ is a proper subset of $M$.

■

Theorem 5

The set of real numbers in the closed unit interval $[0,1]$ is uncountable.

Theorem 6

Given any set $M$, let $\mathscr{M}$ be the set whose elements are all possible subsets of $M$. Then the power of $\mathscr{M}$ is greater than the power of the original set $M$.

Theorem 7 (**Cantor-Bernstein**)

Given two sets $A$ and $B$, suppose $A$ contains a subset $A_1$ equivalent to $B$, while $B$
contains a subset $B_1$ equivalent to $A$. Then $A$ and $B$ are equivalent.
A set $A$ is countable if there is a one-to-one correspondence between the elements of $A$ and $\N$, or in other words, if there exists an injective function $f: A\rightarrow \N$.

Let us call the set $A$ and the subset $S$ and assume $S$ is uncountable. Let us assume for contradiction that $A$ is countable, so there exists an injective function $f: A\rightarrow \N$. Since $S\subset A$, we can define the function $g(x) = \{f(x)\;|\; x\in S\}$ which is an injective function $g:S\rightarrow\N$. But this is impossible since $S$ is uncountable. Hence, $A$ must be uncountable.

■

The statement we want to prove is: if the set $S\subset A$ is uncountable, then $A$ is uncountable.

The contrapositive statement is: if $A$ is countable, then $S\subset A$ is a countable. This follows from Theorem 1. It follows that if $S\subset A$ is uncountable, then $A$ is uncountable.

■

Assume first that $M$ is a countable. By Theorem 2, $M\cup A$ is countable, so $M\sim M\cup A$.

Assume now that $M$ is uncountable. Since $M$ is an uncountable subset of $M\cup A$, then $M\cup A$ is uncountable by Problem 1, so $M\sim M\cup A$.

■

a) The set of all numbers with two distinct decimal expansions (like $0.5000\ldots$ and $0.4999\ldots$).

Let us call the set of numbers with two distinct decimal expansions $D$.

Any number with two distinct decimal expansions has a representation that terminates with an infinite number of 0s, which means there are a finite number of non-zero decimals. This in turn means that it can be represented as a fraction and is therefore rational. Since there are rational numbers that do not have two distinct decimal expansions, such as $1/3$ or $4/7$, the set $D$ is a proper subset of $\Q$. For every $n\in\N$, $n + 1/2 \in D$ so it is an infinite set.

We assume for contradiction that $D$ is uncountable. Since it is a proper subset of $\Q$, then by Problem 1, $\Q$ must be uncountable. This is a contradiction, so we conclude that $D$ is a countable set.

■

b) The set of all rational points in the plane (points with rational coordinates).

Since $\Q$ is a countable set, we can write $\Q = \{q_1, q_2, q_3, \ldots\}$. If we fix $q_1$ we get the following set: $$ Q_1 = \{(q_1, p)\;|\; p\in\Q\}, $$ which are all rational points in the plane with $q_1$ in the $x$ position. We can create a one-to-one correspondence with $\Q$ by simply setting $p\leftrightarrow (q_1, p)$ for each $p\in\Q$, which shows that $Q_1$ is countable. For every $q_i\in\Q$ we define the following sets which are countable by the same argument. $$ Q_i = \{(q_i, p)\;|\; p\in\Q\}, $$ We can now define the following union which are all rational points in the plane: $$ \mathcal{Q} = \bigcup_{n=1}^\infty Q_n, $$ which is a countable union of countable sets. By Theorem 2, $\mathcal{Q}$ is a countable set.

■

c) The set of all rational intervals (intervals with rational endpoints).

Define $\mathscr{Q}_1$ to be the set of all open intervals with rational endpoints. $$ \mathscr{Q}_1 = \{(p,q)\;|\; p,q\in\Q\}. $$ Using $\mathcal{Q}$ from (b), we can create a bijection from $\mathcal{Q}$ to $\mathscr{Q}_1$ by setting $(p,q)\leftrightarrow(p,q)$ which shows that $\mathscr{Q}_1$ is a countable set.

In a similar way, we can define the following three sets of half-open and closed intervals $$ \mathscr{Q}_2 = \{[p,q)\;|\; p,q\in\Q\}. $$ $$ \mathscr{Q}_3 = \{(p,q]\;|\; p,q\in\Q\}. $$ $$ \mathscr{Q}_4 = \{[p,q]\;|\; p,q\in\Q\}. $$ which are all countable sets by the same argument as for $\mathscr{Q}_1$. We have four countable sets, and by Theorem 2 their union is a countable set.

■

Will use a theorem not mentioned in the book.

Theorem A.1

A finite cartesian product of countable sets is countable.

d) The set of all polynomials with rational coefficients.

(

Finite polynomials with rational coefficients are on the following form $$ p_0 + p_1x + p_2x^2 + p_3x^3 + \ldots + p_nx^n $$ where $p_i\in\Q$ for all $i$. We define the set of all rational polynomials as follows: $$ P = \{p_0 + p_1x + \ldots + p_nx^n\;|\; p_0,p_1,\ldots, p_n\in\Q\} $$ For any rational polynomial, we can create the following bijection. $$ p_0 + p_1x + p_2x^2 + \ldots + p_nx^n \leftrightarrow (p_0, p_1, p_2, \ldots, p_n)\in\Q\times\Q\times\Q\times\ldots\times\Q = \textbf{Q}^n. $$ Since $\Q$ is countable and this is a finite cartesian product, then by Theorem A.1, $\textbf{Q}^n$ is countable. Since we have a bijection between $P$ and $\textbf{Q}^n$, it follows that $P$ is countable.

■

From the fundamental theorem of algebra, any non-constant $n$th degree polynomial can be factored into $n$ first degree polynomials, $$ p_0 + p_1x + p_2x^2 + p_3x^3 + \ldots + p_nx^n = r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1}) $$ where $p_0,\ldots, p_n\in\Q$ and $r_0,\ldots,r_n\in\C$. Define $R$ as the set of all roots of polynomials with rational coefficients. $$ R = \{r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1})\;|\; r_0, r_1, r_2, \ldots, r_n\in\C\} $$ Using the fundamental theorem, we can create a one-to-one correspondence from the set of all polynomials $P$ to the set of all roots $R$, since the roots are uniquely determined by the coefficients. $$ (p_0, p_1, p_2, \ldots, p_n) \leftrightarrow (r_0, r_1, r_2, \ldots, r_n) \leftrightarrow r_n(x-r_0)(x-r_1)\ldots(x-r_{n-1}) $$ Since we have a bijection from the countable set $P$ to $R$, the set $R$ is countable. To find the set of all algebraic numbers, we take the union of all sets $r\in (r_0, r_1, r_2, \ldots, r_n)$ and call it $\mathcal{A}$. $$ \mathcal{A} = \bigcup_{r\in R} r. $$ Since this is a countable union of countable sets, the set of all algebraic numbers $\mathcal{A}$ is countable by Theorem 2.

■

If $M$ is an uncountable set and $A\subset M$ is a countable set, then $M-A$ is uncountable.

Assume $M$ is uncountable and $A\subset M$ is countable. Assume for contradiction that $M-A$ is countable. Since $A$ and $M-A$ are countable, then by Theorem 2, $A\cup(M-A) = M$ is countable. But this is a contradiction, since $M$ is uncountable. Hence, $M-A$ must be countable.

■

Prove the existence of uncountably many

Define the set of transcedental numbers as $\R$ minus the algebraic numbers: $\mathcal{T} = \R - \mathcal{A}$. By Theorem 5, $[0,1]$ is uncountable, and since $[0,1]\subset\R$ then by Problem 1, $\R$ is uncountable.

Since $\R$ is uncountable and $\mathcal{A}\subset\R$ is countable, then $\mathcal{T}=\R-\mathcal{A}$ is uncountable by the previous Lemma. Therefore there are uncountably many transcedental numbers.

■

For any subset $A\subset M$ we can define the corresponding identity function $\1_A(x)$, such that $$ \1_A(x) = \left\{ \begin{matrix} 1 & x\in A, \\ 0 & x\not\in A. \end{matrix} \right. $$ If we define $\mathscr{M} = \{A \,|\, A\subset M\}$ we get a one-to-one correspondence $\mathscr{M} = \{A \,|\, A\subset M\}\leftrightarrow \{\1_A \,|\, A\subset M\}$ which shows that these sets are equivalent: $\mathscr{M}\sim \{\1_A \,|\, A\subset M\}$. By Theorem 6, $\mathscr{M}$ has a power greater than $M$ and since it is equivalent to $\mathscr{M}$, so does the set of indicatior functions which is a subset of all possible functions.

■

The set $[0,1]$ is uncountable and has the power of the continuum. But by the previous result, the set of real functions defined on $[0,1]$ has a greater power.

■

Repeated use of the Theorem 7 (Cantor-Bernstein). Assume $c,d\in\R$ such that $a < c < d < b$. Now we define the intervals $(c,d)\subset[a, b]$ and $[c,d]\subset(a, b)$. Since $(c, d)\sim (a, b)$ and $[c, d]\sim[a, b]$, then by Theorem 7, $[a, b]\sim (a, b)$. The same argument can be used to show that all the intervals are equivalent.

■

Let $A_1, A_2, A_3, \ldots$ be sets of power $c$. Since intervals of type $[a, b)$ also have power $c$, we can construct a bijection between the sets $A_i$ and the interval $[i-1, i)$ for $i\in\N$.

For $A_1$ there is a bijection with $[0, 1)$ and for $A_2$ there is a bijection with $[1, 2)$. It follows that we get a bijection from $A_1\cup A_2$ to $[0, 2)$, and since $[0, 2)$ has power $c$, so does $A_1\cup A_2$.

We will use proof by induction. Assume $A_1\cup\ldots A_k$ has a bijection to $[0, k)$ which means both sets have power $c$. There is a bijection between $A_{k+1}$ and $[k, k+1)$. The union $A_1\cup\ldots\cup A_k\cup A_{k+1}$ has power $c$ since it has a bijection with $[0, k+1)$.

By induction the countable union $$ \bigcup_{n=1}^\infty A_n $$ has power $c$. The finite case follows by setting $A_m = \emptyset$ for all $m\geq N$ for some $N\in\N$.

■

Will use a theorem not mentioned in the book.

Theorem A.2 **Schröder-Bernstein**

If there exists an injection $f$: $A\rightarrow B$ and an injection $g: B\rightarrow A$, then there exists a bijection $h: A\rightarrow B$.

(a) The set of all infinite sequences of positive integers.

Let $\mathcal{S}$ be the set of infinite sequences. We can create a bijection between $\mathcal{S}$ and $[0,1]$. We do this by finding an injection in both directions. For the sequence $$ d_1, d_2, d_3, \ldots $$ we could define the number $0.d_1d_2d_3\ldots\in[0,1]$, but this is not unique, since $$ 1, 2, 3, 0, 0, \ldots $$ $$ 12, 3, 0, 0, \ldots $$ $$ 1, 23, 0, 0, \ldots $$ $$ 123, 0, 0, \ldots $$ would all point to $0.123000\ldots$. Instead, we define $b_i$ to be the binary representation of $d_i$ and replace $,$ with $2$. This will give an injection from the set $\mathcal{S}\rightarrow[0,1]$. $$ 1, 2, 3, 0, 0, \ldots \rightarrow 0.12102112020\ldots $$ $$ 12, 3, 0, 0, \ldots \rightarrow 0.11002112020\ldots $$ $$ 1, 23, 0, 0, \ldots \rightarrow 0.12101112020\ldots $$ $$ 123, 0, 0, \ldots \rightarrow 0.11110112020\ldots $$ Now to find an injection from $[0,1]$ to $\mathcal{S}$. This can be done by simply setting $$ 0.d_1d_2d_3\ldots \rightarrow d_1, d_2, d_3, \ldots. $$ By Theorem A.2 (Schröder-Bernstein), there exists a bijection between $[0,1]$ and $\mathcal{S}$ which means they are equivalent sets and $\mathcal{S}$ has the power $c$.

■

(b) The set of all ordered $n$-tuples of real numbers.

Will show that we can make an injection from $(x_1, \ldots, x_n)\rightarrow\R$ and from $\R\rightarrow(x_1, \ldots, x_n)$ where $x_i\in\R$ and then apply Theorem A.2.

Injection $\R\rightarrow(x_1, \ldots, x_n)$. For any $x\in\R$ just place this in the first spot and set all others to 0: $(x, 0, \ldots, 0)$ and we have an injection.

Injection $(x_1, \ldots, x_n)\rightarrow\R$. In this case the numbers $x_i$ are on the form $$ x_i = d^i.d_1^id_2^id_3^i\ldots. $$ For the integral part, we use the binary $b^i$ of $d^i$ and separate the different numbers with 2, as we did in part (a). Then for the decimals, we run through each in turn, so we get: $$ b^12b^22\ldots 2b^n.d_1^1d_1^2\ldots d_1^nd_2^1d_2^2\ldots d_2^nd_3^1\ldots $$ which creates an injection.

By injection both ways, we have a bijection by Theorem A.2. This shows that the set of $n$-tuples has the same power as $\R$; the continuum $c$.

■

(c) The set of all infinite sequences of real numbers.

Define this set as: $$ X = \{A\,|\, A\not\in A\}. $$

This is a set of sets, such as $Y = \{B, C, D\}$. In this case $Y\not\in Y$ so $Y\in X$.

From the hint we will try to answer if $X$ is in $X$. Assume that $X\not\in X$. By the membership condition $X\not\in X\Rightarrow X\in X$ which is a contradiction. If we assume $X\in X$, this cannot be true since $X$ is the set of all sets that don't contain themselves so we violate the membership condition $A\not\in A$. Another contradiction. As such, this set cannot exist.