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:

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

where is the digit in the decimal expansion of the number . Consider the decimal constructed as follows: For choose any digit (from 0 to 9) different from , for any digit different from , and so on, and in general, for any digit different from . Then, the decimal cannot coincide with any decimal in the first list. In fact, differs from in at least the first digit, from in at least the second digit, and so on, since in general for all n. Thus, no list of real numbers in the interval can include all the real numbers in .

The above argument must be refined slightly since certain numbers, namely those of the form , can be written as decimals in two ways, either with an infinite run of zeros or an infinite run of nines. For example, , 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 , we require that contain neither zeros nor nines, for example, by setting if and if .

Thus, the set is uncountable. Other examples of uncountable sets equivalent to are:

(i) The set of points in any closed interval .

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

(iii) The set of points in any open interval .

(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 is proved as in examples 1 and 3 (previous blog) while the fact that the sets (iii) to (vii) are equivalent to is best proved (problems 7 and 9 in the following exercise).

Given any two sets M and N, suppose M and N are equivalent. Then, M and N are said to have the same . 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 of all positive integers, and hence, the power of any countable set, is denoted by the symbol , read as “aleph null.” A set equivalent to the set of real numbers in the interval and hence, to the set of all real numbers, is said to have the power of the , denoted by , or often by .

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 and , respectively. If A is equivalent to B, then 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 is less than or as greater than . 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 or . For example, it is clear that . ().

. The very deep problem of the existence of powers between 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 be the set whose elements are all possible subsets of M. Then, the power of is greater than the power of the original set M.

.

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

, ,

has been establshed between the elements a, b of M and certain elements A, B, of (that is, certain subsets of M). Then, A, B do not exhaust all the elements of $latex\mathscr{M}$, that is, all subsets of M. To see this, let be the set of elements of M which do not belong to their “associated subsets.” More exactly, if we assign a to X if , but not if . Clearly, X is a subset of M and hence, an element of . Suppose there is an element such that , and consider whether or not x belongs to X. Suppose . Then, , since, by definition, X contains element not contained in its associated subset. On the other hand, suppose . Then, , 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 , that is, . .

Thus, given any set M, there is a set of larger power, a of still larger power, and so on, indefinitely. in particular, there is no set of”largest” power.

.

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

, .

Given any two sets A and B, suppose A contains a subset 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 , and a one-to-one function g mapping B into :

, and . therefore , that is, is a subset of A_{1} equivalent to all of A.

Similarly, is a subset of equivalent to B. Let be the subset of A into which the mapping gf carries the set , and let be the subset of A into which gf carries . More generally, let be the set into which is carried by gf.

Then, clearly

Setting , we can represent A as the union of pairwise disjoint sets:

.

From the above, we can conclude that , and ,

where

where

where

But is equivalent to (the former is carried into the latter by the one-to-one function gf), is equivalent to and so on. Therefore, N is equivalent to . It follows from the representations above that a one-to-one correspondence can be set up between the sets A and . But, is equivalent to B, by hypothesis. Therefore, A is equivalent to B. .

.

Here, we can even ‘afford the unnecessary luxury” of explicitly writing down a one-to-one function carrying A into B, that is, , if and , if .

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

We will continue with exercises and their solutions soon,

Nalin Pithwa