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.

Theorem 4.10.1 (Cantor's Theorem) If $A$ is any set, then $\overline A< \overline {{\cal P}(A)}$.

**Proof.**
First, we need to show that $\overline A\le \overline {{\cal P}(A)}$:
define an injection $f\colon A\to {\cal P}(A)$ by $f(a)=\{a\}$. Now
we need to show that there is no bijection $g\colon A\to {\cal P}(A)$.
For a contradiction, suppose $g$ is such a bijection. Let
$$
S=\{a\in A: a\notin g(a)\}\subseteq A.
$$
Since $S\in {\cal P}(A)$, $S=g(x)$, for some $x\in A$, because $g$ is
a surjection. There are two possibilities: $x\in S$ and $x\notin S$.

1. If $x\in S$, then $x\notin g(x)=S$, i.e., $x\notin S$, a contradiction.

2. If $x\notin S$, then $x\in g(x)=S$, i.e., $x\in S$, a contradiction.

Therefore, no such bijection is possible. $\qed$

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:

That is, the continuum hypothesis asserts that $c$ is the first cardinal number larger than $\aleph_0$. Remarkably, the continuum hypothesisThere is no set $A$ with $\aleph_0 < \overline A< c$.

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