We have now seen infinite sets of two different sizes, $\aleph_0$ and $c$. Are there others? Is there a largest infinite size, i.e., a largest cardinal number? Recall that for any set $A$, the power set of $A$, written ${\cal P}(A)$, is the collection of all subsets of $A$. For example, ${\cal P}(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}$. For finite sets, the power set is not just larger than the original set, it is much larger (see exercise 1). This makes it natural to hope that the power set of an infinite set will be larger than the base set.

Let $\overline A< \overline B$ mean that $\overline A\le \overline B$, but $A$ and $B$ do not have the same cardinality. The next theorem answers both questions posed above.

Cantor's theorem implies that there are infinitely many infinite cardinal numbers, and that there is no largest cardinal number. It also has the following interesting consequence:

There is no such thing as the "set of all sets''.

Suppose $A$ were the set of all sets. Since every element of ${\cal P}(A)$ is a set, we would have ${\cal P}(A)\subseteq A$, so $$ \overline {{\cal P}(A)}\le \overline A\le \overline {{\cal P}(A)}. $$ By the Schröder–Bernstein Theorem, $\overline {{\cal P}(A)}= \overline A$, but this contradicts Cantor's Theorem.

Many questions about the cardinal numbers remain. Since we know that $\Z$ and $\Q$ are the same size, and that $\R$ is larger, one very natural question is whether there are any sets `between' $\Z$ and $\R$, that is, strictly bigger than $\Z$ (and $\Q$) but strictly smaller than $\R$. The continuum hypothesis says:

There is no set $A$ with $\aleph_0 < \overline A< c$.

That is, the continuum hypothesis asserts that $c$ is the first cardinal number larger than $\aleph_0$. Remarkably, the continuum hypothesis cannot be proved to be true and cannot be proved to be false. In the 1920's, Kurt Gödel showed that the continuum hypothesis cannot be disproved, and in the early 1960's, Paul Cohen showed that it cannot be proved either.

Georg Cantor. Cantor (1845–1918) was born in St. Petersburg and grew up in Germany. He took an early interest in theological arguments about continuity and the infinite, and as a result studied philosophy, mathematics and physics at universities in Zurich, Göttingen and Berlin, though his father encouraged him to pursue engineering. He did his doctorate in number theory and then worked in analysis before doing his pioneering work in the theory of sets.

The prevailing opinion in the nineteenth century was that `completed' infinities could not be studied rigorously; only `potential' infinity made sense—for example, the process of repeatedly adding one, starting at 1, would never finish and was therefore infinite, but most mathematicians viewed the completed set of positive integers (or any other infinite set) as a dubious concept at best. An infinite set can be placed in one to one correspondence with a proper subset of itself; most mathematicians saw this as a paradox, and `solved' the problem by declaring that `infinite sets' simply make no sense.

A few mathematicians went against the grain; Dedekind realized that the `paradoxical' correspondence between a set and one of its proper subsets could be taken as the definition of an infinite set. Cantor took this notion much further, showing that infinite sets come in an infinite number of sizes. Cantor knew most of what we have seen in this chapter: he showed that the rational numbers are countable, that $\R$ is not countable, that ${\cal P}(A)$ is always bigger than $A$. The algebraic numbers are those real numbers that are roots of polynomials with rational coefficients—for example, $\sqrt{2}$ is a solution of $x^2-2=0$, and is therefore irrational and algebraic (all rational numbers are algebraic). There are `more' algebraic numbers than rational numbers, in the sense that the algebraic numbers form a proper superset of the rationals, but Cantor showed that the set of algebraic numbers is countable. This means that the transcendental numbers (that is, the non-algebraic numbers, like $\pi$ and $e$) form an uncountable set—so in fact almost all real numbers are transcendental.

In addition to the arithmetic of infinite cardinal numbers, Cantor developed the theory of infinite ordinal numbers. The two concepts are practically the same for finite numbers, so the idea that infinite ordinals and infinite cardinals are different takes some getting used to. Since there is essentially only one way to make a total order out of four objects (namely, pick a first, a second, a third and a fourth), the cardinal number 4 (`how many') and the ordinal number 4 (`what order') are easily confused. For infinite sets the situation is radically different. The ordinal number of the positive integers, called $\omega$, is simply the usual total ordering of the positive integers. `Addition' of ordinals is accomplished by placing the orders side by side: $1+\omega$ `looks like' one item followed by a countable number of items in the same order as the positive integers—this looks just like the positive integers. On the other hand, $\omega+1$ looks like the positive integers followed by a single item, and is much different than the usual ordering of the positive integers, even though the size of the two ordered sets is the same. (The easiest way to see that there is a crucial difference between the two orderings is to note that one element of $\omega+1$ has an infinite number of predecessors, while all of the elements of $1+\omega$ have a finite number of predecessors.)

Cantor was unable to secure a position at a major university, including Berlin, where he most desired to be. This failure was due in large part to the influence of Kronecker, a mathematician at Berlin, who ridiculed all talk of completed infinities, convinced that only finite processes could be justified. (As a result, he didn't believe in irrational numbers, since they could not be `produced' by a finite process.) Beginning in 1884, Cantor suffered a series of nervous breakdowns, presumably related to the refusal of so many mathematicians to accept his work; Cantor himself had occasional doubts about his results—the proofs were clear and rigorous, but the results still seemed paradoxical. Cantor died in a mental institution in 1918, though he did get some positive recognition for his work before his death. Writing a few years after Cantor's death, the great mathematician David Hilbert called Cantor's work "the most astonishing product of mathematical thought, one of the most beautiful realizations of human activity in the domain of the purely intelligible.'' The years since have more than justified this assessment of Cantor's work.

The information here is taken from A History of Mathematics, by Carl Boyer, New York: John Wiley & Sons, 1968. For a more detailed account of Cantor's life and work, see Georg Cantor, His Mathematics and Philosophy of the Infinite, by Joseph Dauben, Harvard University Press, 1979.

Exercises 4.10

Ex 4.10.1 Verify Cantor's Theorem for finite sets by showing that if $A$ has $n$ elements, then ${\cal P}(A)$ has $2^n$ elements.

The representation of a real number as a decimal is almost, but not quite, unique. The problem arises only with those numbers that have "terminating'' decimal expansions, like $1=.99999…$ and $.246=.2459999…$. A similar statement, of course, is true if we use some other base $b$. For example, in base 2, $1=.11111…$ and $.11=.101111…$.

Recall from exercise 7 of section 4.9 that $\overline {{[0,1]}}=c$. If $b$ is a base for a number system, define a function $f_b\colon {\cal P}(\N\mskip 1mu)\to [0,1]$ as follows: if $S\subseteq \N$, let $$ f_b(S)=\sum_{i\in S}b^{-i}. $$ For example, writing expansions in base $b$, $$ \eqalign{f_b(\{1,2,3\})&=.111000…,\cr f_b(\{odd numbers\})&=.10101010…,\cr f_b(\{prime numbers\})&=.011010100…} $$

Ex 4.10.2 What kind of function is $f_{10}$? How about $f_2$?

Ex 4.10.3 Use exercise 2 to prove $\overline{{\cal P}(\N)}=c$. Knowing this, the continuum hypothesis can be rephrased: There is no set $A$ such that $\overline{\N}< \overline A< \overline{{\cal P}(\N)}$.

Ex 4.10.4 Suppose $A$ and $B$ are sets.

a) If $\overline A\le \overline B$, prove $\overline{{\cal P}(A)} \le \overline{{\cal P}(B)}$.

b) Use part (a) to prove that if $\overline A=\overline B$, then $\overline{{\cal P}(A)}= \overline{{\cal P}(B)}$.

Ex 4.10.5 Note that if $A$ and $B$ are disjoint (i.e., $A\cap B=\emptyset$) finite sets with $m$ and $n$ elements, respectively, then $A\cup B$ has $m+n$ elements. We want to use this idea to define the sum of infinite cardinal numbers.

a) Suppose that $A$ and $B$ are sets, not necessarily disjoint. Show that $A_0=A\times \{0\}$ and $B_1=B\times \{1\}$ are disjoint, and show that $A\approx A_0$ and $B\approx B_1$. We use this to define the sum of two cardinal numbers by the formula $\overline A+\overline B=\overline {A_0\cup B_1}$.

b) Show that this definition is independent of the sets $A$ and $B$, i.e., if $A\approx A'$ and $B\approx B'$, then $A_0\cup B_1\approx A'_0\cup B'_1$. (Find a bijection from $A_0\cup B_1$ to $A'_0\cup B'_1$.)

Ex 4.10.6 Use exercise 5 of section 4.8 to show that $\aleph_0+\aleph_0=\aleph_0$.

If $A$ and $B$ are sets, let map$(A,B)$ denote the collection of all functions from $A$ to $B$. Observe that if $A$ has $n$ elements and $B$ has $m$ elements, map$(A,B)$ has $m^n$ elements. We want to define $\overline B^{{\overline A}}$ to mean $\overline {{map(A,B)}}$. In order to do so, we need to verify that if $f\colon A\to A'$ and $g\colon B\to B'$ are bijections, we can find a bijection $h\colon map(A,B)\to map(A',B')$. To this end, if $\phi\in map(A,B)$, let $h(\phi)=g\circ \phi\circ f^{-1}$. Conversely, if $\phi\in map(A',B')$, let $k(\phi)=g^{-1}\circ \phi\circ f$.

Ex 4.10.7 Verify that $h$ and $k$ are inverse functions (and hence bijective).

If $S\subseteq A$, define the characteristic function of $S$ by the equation, $$ \chi_S(x)= \cases{ 1,& if $x\in S$; \cr 0,& if $x\notin S$. \cr} $$

Ex 4.10.8 Show that associating $S$ with $\chi_S$ defines a one-to-one correspondence between ${\cal P}(A)$ and map$(A,\{0,1\})$. This implies that $\overline {{{\cal P}(A)}}=2^{{\overline A}}$. (Hint: if $\phi\in map(A,\{0,1\})$, for which $S\subseteq A$ does $\phi=\chi_S$?)

Ex 4.10.9 Suppose that $a/b$ is a rational number. Show that it is algebraic by finding a polynomial with rational coefficients that has $a/b$ as a root. Also, find a polynomial with integer coefficients that has $a/b$ as a root.