Cantor’s Theorem and the Unending Hierarchy of Infinities

The power set of the set {x,y,z}, containing all its subsets, has 2^3=8 elements. Image from Wikimedia Commons.

In 1891, Georg Cantor published a seminal paper, U”ber eine elementare Frage der Mannigfaltigkeitslehren — On an elementary question of the theory of manifolds — in which his “diagonal argument” first appeared. He proved a general theorem which showed, in particular, that the set of real numbers is uncountable, that is, it has cardinality greater than that of the natural numbers. But his theorem is much more general, and it implies that the set of cardinals is without limit: there is no greatest order of infinity.

The Theorem

The proof of the theorem is quite simple, but also quite subtle and certainly quite clever. For finite sets, the result is obvious: a set with ${n}$ elements has ${2^n}$ subsets and, of course, ${\forall n\in\mathbb{N}\,[n<2^n]}$ . Thus, every finite set is smaller than its power set. The figure above shows the power set of the set ${\{x,y,z\}}$ of three elements. The power set has ${2^3=8}$ elements. As an aside, we note that the diagram in the figure has the topological structure of a cube; this is no coincidence.

Cantor’s argument is applicable to all sets, finite, countable and uncountable. His theorem states that there is never a bijection between a set ${A}$ and its power set ${\mathscr{P}(A)}$ , the set of all subsets of ${A}$ . A bijection is a one-to-one mapping with a one-to-one inverse. Moreover, since ${A}$ is clearly smaller than its power set — just map each element ${x}$ to the set ${\{x\}}$ , an injection but not a surjection — we conclude that

$\displaystyle \mathrm{card}\ A < \mathrm{card}\ \mathscr{P}(A) \,,$

where ${\mathrm{card}}$ represents the cardinality of a set. Repeating the power set operation, we have

$\displaystyle \mathrm{card}\ \mathscr{P}(A) < \mathrm{card}\ \mathscr{P}(\mathscr{P}(A)) \,.$

and, since this process can be iterated indefinitely, there is no limit and we have an infinite sequence of ever-greater infinities.

The case of the natural numbers is of central interest. Cantor wrote ${\mathrm{card}\ \mathbb{N} = \aleph_0}$ . Since every real number can be expressed as an infinite sequence of natural numbers (for example, via its decimal expansion), the real numbers may be put in one-to-one correspondence with the power set of the natural numbers so that ${\mathfrak{c} = \mathrm{card}\ \mathbb{R} = 2^{\aleph_0}}$ . Then Cantor’s theorem implies that

$\displaystyle \mathrm{card}\ \mathbb{R} > \aleph_0 \,.$

so the real numbers are uncountable.

The Proof

An injection of ${A}$ into ${B}$ is a ${1:1}$ mapping from ${A}$ into ${B}$ . It may not cover ${B}$ entirely. A surjection of ${A}$ onto ${B}$ is a mapping with range ${B}$ . A bijection is a map that is both an injection and a surjection. It is ${1:1}$ and has an inverse that is also ${1:1}$ .

Cantor’s theorem states that, for any set ${A}$ , there is no surjection from ${A}$ to its power set ${\mathscr{P}(A)}$ . Clearly, there is an injection, namely ${S:x\in A \mapsto \{x\}\in\mathscr{P}(A)}$ . Therefore, ${\mathrm{card}\,A \le \mathrm{card}\,\mathscr{P}(A)}$ .

A map from a set to its power set. Element ${x}$ maps to ${S_x}$ with ${x\in S_x}$ . Element ${y}$ maps to ${S_y}$ but ${y\notin S_y}$ .

The figure illustrates a map from a set ${A}$ to its power set ${\mathscr{P}(A)}$ . Element ${x\in A}$ maps to ${S_x\in \mathscr{P}}$ and ${x\in S_x}$ . Element ${y}$ maps to ${S_y}$ but ${y\notin S_y}$ . To eliminate the possibility of equality, we must show that no map ${S}$ from ${A}$ to its power set can reach every subset of ${A}$ . There is always some subset ${B}$ such that ${B}$ is not the image under ${S}$ of any element of ${A}$ . We show this by directly constructing such a subset ${B}$ :

$\displaystyle B = \{ x\in A : x\notin S(x) \} \,.$

This is sometimes called Cantor’s diagonal set for ${S}$ .

Let us assume that ${B}$ is the image of some element of ${A}$ . That is, for some ${\xi\in A}$ we have ${S(\xi) = B}$ . Now we note the following two-way implication

$\mbox{For any}\ \xi \in A \qquad \xi \notin S(\xi) \iff \xi \in B \qquad \mbox{by definition of}\ B$

But we also have the implication

$\mbox{For any}\ \xi \in A \qquad \xi \in B \iff \xi \in S(\xi) \qquad \mbox{because}\ S(x) = B \,.$

But these two conclusions cannot both be true: they contradict each other. This reducio ad absurdum argument forces us to the conclusion that ${B}$ cannot be the image under ${S}$ of any element of ${A}$ . That is, the map ${S}$ is not surjective. Therefore,

$\displaystyle \mathrm{card}\ A < \mathrm{card}\ \mathscr{P}(A) \,.$

Q.E.D.

The Unending Hierarchy

If ${A}$ has cardinality ${\mathfrak{n}}$ then ${\mathscr{P}(A)}$ has cardinality ${2^{\mathfrak{n}}}$ . Cantor introduced the beth-numbers

$\displaystyle \beth_0 = \mathrm{card}\ \mathbb{N} \,,\quad \beth_1 = \mathrm{card}\ \mathscr{P}(\mathbb{N}) \,, \quad \beth_2 = \mathrm{card}\ \mathscr{P}(\mathscr{P}(\mathbb{N})) \,,\ \dots$

These numbers can also be expressed as follows:

$\displaystyle \beth_0 = \aleph_0 \,,\quad \beth_1 = 2^{\beth_0} \,, \quad \beth_2 = 2^{\beth_1} \,,\ \dots$

The relationship between the aleph and beth numbers involves the continuum hypothesis. See an earlier post, “Aleph, Beth, Continuum”.

Sources

${\bullet}$ That’s Maths Post: Aleph, Beth, Continuum.

${\bullet}$ Wikipedia article Cantor’s Theorem.

ThatsMaths