Uncountability of the real numbers: Kolmogorov and Fomin

Reference: Introductory Real Analysis by Kolmogorov and Fomin.

Several examples of countable sets were given earlier, and many more examples of such sets could be given. In fact, according to Theorem 2(refer previous blog(s)), the union of a finite or countable number of countable sets is itself countable. It is now natural to ask whether there exist sets which are uncountable. The existence of such sets is shown by:

$\bf{Theorem5}$

$\bf{The \hspace{0.1in}set \hspace{0.1in}of \hspace{0.1in}real \hspace{0.1in}numbers \hspace{0.1in}in \hspace{0.1in}the \hspace{0.1in}closed \hspace{0.1in}unit \hspace{0.1in}interval \hspace{0.1in}[0,1] \hspace{0.1in}is \hspace{0.1in}uncountable.}$

$\bf{Proof}$

Suppose we have managed to count some or all of the real numbers in $[0,1]$ , arranging them in a list:

$\alpha_{1}=0.a_{11}a_{12}a_{13}\ldots a_{1n}\ldots \ldots$

$\alpha_{2}=0.a_{21}a_{22}a_{23}\ldots a_{2n}\ldots \ldots$

$\alpha_{3}=0.a_{31}a_{32}a_{33}\ldots a_{3n}\ldots \ldots$

$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

$\alpha_{n}=0.a_{n1}a_{n2}a_{n3}\ldots a_{nn} \ldots \ldots$

$\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots$

where $a_{ik}$ is the $k^{th}$ digit in the decimal expansion of the number $\alpha_{i}$ . Consider the decimal $\beta=0.b_{1}b_{2}b_{3}\ldots b_{n}\ldots\ldots$ constructed as follows: For $b_{1}$ choose any digit (from 0 to 9) different from $a_{11}$ , for $b_{2}$ any digit different from $a_{22}$ , and so on, and in general, for $b_{n}$ any digit different from $a_{nn}$ . Then, the decimal $\beta$ cannot coincide with any decimal in the first list. In fact, $\beta$ differs from $\alpha_{1}$ in at least the first digit, from $\alpha_{2}$ in at least the second digit, and so on, since in general $b_{n} \neq a_{nn}$ for all n. Thus, no list of real numbers in the interval $[0,1]$ can include all the real numbers in $[0,1]$ .

The above argument must be refined slightly since certain numbers, namely those of the form $\frac{p}{10^{q}}$ , can be written as decimals in two ways, either with an infinite run of zeros or an infinite run of nines. For example, $\frac{1}{2}=\frac{5}{10}=0.500000\ldots=0.499999\ldots$ , so that the fact that two decimals are distinct does not necessarily mean that they represent real numbers. However, this difficulty disappears if in constructing $\beta$ , we require that $\beta$ contain neither zeros nor nines, for example, by setting $b_{n}=2$ if $a_{nn}=1$ and $b_{n}=1$ if $a_{nn}=1$ .

Thus, the set $[0,1]$ is uncountable. Other examples of uncountable sets equivalent to $[0,1]$ are:

(i) The set of points in any closed interval $[a,b]$ .

(ii) The set of points on the real line.

(iii) The set of points in any open interval $(0,1)$ .

(iv) The set of points in the plane or in space.

(v) The set of all points on a sphere or inside a sphere.

(vi) The set of all lines in the plane

(vii) The set of all continuous real functions of one or several variables.

The fact that the sets (i) and (ii) are equivalent to $[0,1]$ is proved as in examples 1 and 3 (previous blog) while the fact that the sets (iii) to (vii) are equivalent to $[0,1]$ is best proved $\it{indirectly}$ (problems 7 and 9 in the following exercise).

$\bf{The \hspace{0.1in}power \hspace{0.1in}of \hspace{0.1in}a \hspace{0.1in}set}$

Given any two sets M and N, suppose M and N are equivalent. Then, M and N are said to have the same $\it{power}$ . Roughly speaking, “power” is something shared by equivalent sets. If M and N are finite, then M and N have the same number of elements, and the concept of the power of a set reduces to the usual notion of the number of elements in a set. The power of the set $\mathscr{Z^{+}}$ of all positive integers, and hence, the power of any countable set, is denoted by the symbol $\aleph_{0}$ , read as “aleph null.” A set equivalent to the set of real numbers in the interval $[0,1]$ and hence, to the set of all real numbers, is said to have the power of the $\it{continuum}$ , denoted by $c$ , or often by $\aleph$ .

For the powers of finite sets, that is, for the positive integers, we have the notions of “greater than” and “less than,” as well as the notions of equality. We now show how these concepts are extended to the case of of infinite sets.

Let A and B be any two sets, with powers $m(A)$ and $m(B)$ , respectively. If A is equivalent to B, then $m(A)=m(B)$ by definition. If A is equivalent to a subset of B and if no subset of A is equivalent to B, then, by analogy with the finite case, it is natural to regard $m(A)$ is less than $m(B)$ or $m(B)$ as greater than $m(A)$ . Logically, however, there are two further possibilities:

i) B has a subset equivalent to A, and A has a subset equivalent to B;

ii) A and B are not equivalent, and neither has a subset equivalent to the other.

In case (i), A and B are equivalent and hence, have the same power, as shown soon by the Cantor-Bernstein theorem (Theorem 7 below). Case (ii) would obviously show the existence of powers that cannot be compared, but it follows from the well-ordering theorem that this case is actually impossible. Therefore, taking both of these theorems on faith, we see that any two sets A and B either have the same power or else satisfy one of the relations $m(A)<m(B)$ or $m(A)>m(B)$ . For example, it is clear that $\aleph_{0}<c$ . ( $\bf{Quiz \hspace{0.1in} why}$ ).

$\bf{\it{Remark}}$ . The very deep problem of the existence of powers between $\aleph_{0}$ and c is touched upon later (in this text or blog series). As a rule, however, the infinite sets encountered in analysis are either countable or else have the power of the continuum.

We have already noted that countable sets are the “smallest” infinite sets. It has also been shown that there are infinite sets of power greater than that of a countable set, namely, sets with the power of the continuum. It is natural to ask whether there are infinite sets of power greater than that of the continuum or, more generally, whether there is a “largest” power. These questions are answered by :

$\bf{Theorem6}$

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.

$\bf{Proof}$ .

Clearly, the power of p of the set $\mathscr{M}$ cannot be less than the power $\mu$ of the original set M, since the “single-element subsets” (or “singletons”) of $M$ form a subset of $\mathscr{M}$ equivalent to M. Thus, we need only show that m and $\mu$ do not coincide. Suppose a one-to-one correspondence

$a\leftrightarrow A$ , $b \leftrightarrow B$ , $\ldots$

has been establshed between the elements a, b $\ldots$ of M and certain elements A, B, $\ldots$ of $\mathscr{M}$ (that is, certain subsets of M). Then, A, B $\ldots$ do not exhaust all the elements of $latex\mathscr{M}$, that is, all subsets of M. To see this, let $X$ be the set of elements of M which do not belong to their “associated subsets.” More exactly, if $a \leftrightarrow A$ we assign a to X if $a \notin A$ , but not if $a \in A$ . Clearly, X is a subset of M and hence, an element of $\mathscr{M}$ . Suppose there is an element $x \in M$ such that $x \leftrightarrow X$ , and consider whether or not x belongs to X. Suppose $x \notin X$ . Then, $x \in X$ , since, by definition, X contains $\it{every}$ element not contained in its associated subset. On the other hand, suppose $x \notin X$ . Then, $x \in X$ , since X consists precisely of those elements which do not belong to their associated subsets. In any event, the element x corresponding to the subset X must simultaneously belong to X and not belong to X. But, this is impossible!! It follows that there is no such element x. Therefore, no one-to-one correspondence can be established between the sets $M, \mathscr{M}$ , that is, $m \neq \mu$ . $\bf{QED}$ .

Thus, given any set M, there is a set $\mathscr{M}$ of larger power, a $\mathscr{M^{*}}$ of still larger power, and so on, indefinitely. in particular, there is no set of”largest” power.

$\bf{Section6}$

$\bf{The \hspace{0.1in} Cantor \hspace{0.1in} Bernstein \hspace{0.1in} Theorem}$ .

Now, we prove an important theorem already used in the preceding section:

$\bf{Theorem7}$ , $\bf{Cantor\hspace{0.1in}-Berstein}$ .

Given any two sets A and B, suppose A contains a subset $A_{1}$ equivalent to B, while B contains a subset B, equivalent to A. Then, A and B are equivalent.

$\bf{Proof}$ .

By hypothesis, there is a one-to-one function f mapping A into $B_{1}$ , and a one-to-one function g mapping B into $A_{1}$ :

$f(A)=B_{1}\subset B$ , and $g(B)=A_{1} \subset A$ . therefore $A_{2}=gf(A)=g(f(A))=g(B_{1}) \subset g(B) = A_{1}\subset A$ , that is, $g(B_{1})$ is a subset of A_{1} equivalent to all of A.

Similarly, $B_{1}=fg(B)=f(g(B))=f(A_{1})$ is a subset of $B_{1}$ equivalent to B. Let $A_{3}$ be the subset of A into which the mapping gf carries the set $A_{1}$ , and let $A_{4}$ be the subset of A into which gf carries $A_{2}$ . More generally, let $A_{k+2}$ be the set into which $A_{k}, k=1,2,\ldots$ is carried by gf.

Then, clearly

$A \supset A_{1} \supset A_{2} \supset \ldots \supset A_{k}\supset A_{k+1}\supset \ldots$

Setting $D = \bigcap_{k=1}^{\infty}A_{k}$ , we can represent A as the union of pairwise disjoint sets:

$A=(A-A_{1})\bigcup (A_{1}-A_{2})\bigcup (A_{2}-A_{3}) \bigcup \ldots \bigcup (A_{k}-A_{k+1})\bigcup \ldots \bigcup D$ .

From the above, we can conclude that $A=D \bigcup M \bigcup N$ , and $A_{1}=D \bigcup M \bigcup N_{1}$ ,

where $M = (A_{1}-A_{2}) \bigcup (A_{3}-A_{4}) \bigcup \ldots$

where $N=(A-A_{1})\bigcup (A_{2}-A_{3}) \bigcup \ldots$

where $N_{1}= (A_{2}-A_{3}) \bigcup (A_{4}-A_{3}) \bigcup \ldots$

But $A-A_{1}$ is equivalent to $A_{2}-A_{3}$ (the former is carried into the latter by the one-to-one function gf), $A_{2}-A_{3}$ is equivalent to $A_{4}-A_{3}$ and so on. Therefore, N is equivalent to $N_{1}$ . It follows from the representations above that a one-to-one correspondence can be set up between the sets A and $A_{1}$ . But, $A_{1}$ is equivalent to B, by hypothesis. Therefore, A is equivalent to B. $\bf{QED}$ .

$\bf{Remark}$ .

Here, we can even ‘afford the unnecessary luxury” of explicitly writing down a one-to-one function carrying A into B, that is, $\phi(a)=g^{-1}(a)$ , if $a \in D \bigcup M$ and $\phi(a)=f(a)$ , if $a \in D \bigcup N$ .