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{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.}


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 :


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.


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{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.


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}.


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.


The above proof is also as beautifully explained in General Topology, Schaum Series.

We will continue with exercises and their solutions soon,

Nalin Pithwa

























Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.