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 elements has subsets and, of course, . Thus, every finite set is smaller than its power set. The figure above shows the power set of the set of three elements. The power set has 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 and its power set **, the set of all subsets of . A bijection is a one-to-one mapping with a one-to-one inverse. Moreover, since is clearly smaller than its power set — just map each element to the set , an injection but not a surjection — we conclude that

where represents the cardinality of a set. Repeating the power set operation, we have

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 . 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 . Then Cantor’s theorem implies that

so the real numbers are uncountable.

**The Proof**

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

Cantor’s theorem states that, for any set , there is no surjection from to its power set . Clearly, there is an injection, namely . Therefore, .

The figure illustrates a map from a set to its power set . Element maps to and . Element maps to but . To eliminate the possibility of equality, we must show that no map from to its power set can reach every subset of . There is always some subset such that is not the image under of any element of . We show this by directly constructing such a subset :

This is sometimes called Cantor’s diagonal set for .

Let us assume that is the image of some element of . That is, for some we have . Now we note the following two-way implication

But we also have the implication

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

Q.E.D.

**The Unending Hierarchy**

If has cardinality then has cardinality . Cantor introduced the *beth*-numbers

These numbers can also be expressed as follows:

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

**Sources**

That’s Maths Post: Aleph, Beth, Continuum.

Wikipedia article *Cantor’s Theorem*.