Second Problem Set from Kolmogorov and Fomin: Introductory Real Analysis

bf{Problem 1}.

Prove that a set with an uncountable subset is itself uncountable.

\bf{Problem 2}.

Let M be any infinite set and let set A be any countable set. Prove that M \sim M\bigcup A.

\bf{Problem 3}.

Prove that each of the following sets is countable:

(a) The set of all numbers with two distinct decimal representations (like 0.50000…and 0.49999…).

(b) The set of all rational points in the plane (that is, points with rational coordinates)

(c) The set of all rational intervals (That is, intervals with rational end points)

(d) The set of all polynomials with rational coefficients.

\bf{Problem 4}.

A number \alpha is called algebraic if it is a root of a polynomial equation with rational coefficients. Prove that the set of all algebraic numbers is countable.

\bf{Problem 5}

Prove the existence of uncountably many transcendental numbers, that is, numbers which are not algebraic. Hint: Use Theorems 2 and 5 of previous blog(s).

\bf{Problem 6}

Prove that the set of all real functions (more generally, functions taking values in a set containing at least two elements) defined on a set M is of power greater than the power of M. In particular, prove that the power of the set of all real functions (continuous and discontinuous) defined in the interval [0,1] is greater than c. Hint: Use the fact that the set of all characteristic functions (that is, functions taking values 0 and 1) on M is equivalent to the set of all subsets of M.


Give an indirect proof of the equivalence of the closed interval [a,b], the open interval (a,b) and the half-open interval [a,b) or (a,b). Hint: Use theorem 7 (the Cantor-Bernstein theorem).


Prove that the union of a finite set of a finite or countable number of sets each of power c is itself of power c.


Prove that the each of the following sets has the power of the continuum:

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

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

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


Develop a contradiction inherent in the notion of the “set of all sets which are not members of themselves”. Hint: Is this set a member of itself? Comment: Thus, we will be careful to sets which are “too big,” like the “set of all sets”.

We will go through the solutions of the above soon,


Nalin Pithwa




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

























Set Theory, Relations, Functions: Kolmogorov and Fomin

Set Theory, Relations, Functions: Preliminaries: Part VIII

Set Theory, Relations, Functions: Preliminaries: part VIIIA

Set Theory, Relations, Functions: Preliminaries: Part IX: (tutorial problems)

Set Theory, Relations, Functions: preliminaries: part 10: more tutorial problems for practice

Towards Baby Analysis: Part I: INMO, IMO and CMI Entrance