Cantor's theorem

In set theory, Cantor's theorem states that the set of all subsets of any set A has a strictly greater cardinality than that of A. In particular, the set of all subsets of a countably infinite set is uncountably infinite.

The proof

The proof is a quick diagonal argument. Let f be any one-to-one function from A into the set of all subsets of A. It must be shown that f is necessarily not surjective. To do that, it is enough to exhibit a subset of A that is not in the image of f. That subset is

${\displaystyle B=\left\{\,x\in A:x\not \in f(x)\,\right\}.}$ 

To show that B is not in the image of f, suppose that B is in the image of f. Then for some y in A, we have f(y) = B. Now consider whether y ε B or not. If y ε B, then y ε f(y), but that implies, by definition of B, that y not ε B. On the other hand if it is y not ε B, then y not ε f(y) and therefore y ε B. Either way, we get a contradiction.

History

Though it is called "Cantor's Theorem", Cantor never gave a proof in precisely this form. His first proof of the non-denumerability of the reals was was written in 1873 and published in 1874 (see Cantor's first uncountability proof). This does not resemble the theorem at all.

In a famous paper published in 1891 ("Ueber eine elementare Frage der Mannigfaltigkeitslehre"), where the diagonal proof first appears, there is a another proof later in this paper, where he notes that if f is a function defined on X whose values are 2-valued functions on X, then the 2-valued function G(x) = 1−f(x)(x) is not in the range of f.

Russell has a very similar proof in Principles of Mathematics (1903, section 348, where he shows that that there are more propositional functions than objects. "For suppose a correlation of all objects and some propositional functions to have been affected [sic], and let phi-x be the correlate of x. Then "not-phi-x(x)," i.e. "phi-x does not hold of x" is a propositional function not contained in this correlation; for it is true or false of x according as phi-x is false or true of x, and therefore it differs from phi-x for every value of x." He attributes the idea behind the proof to Cantor.

Ernst Zermelo has a theorem (which he calls "Cantor's Theorem") that is identical to the form above in the paper that became the foundation of modern set theory ("Untersuchungen über die Grundlagen der Mengenlehre I"), published in 1908. See Zermelo set theory.

Consequences

Most mathematicians are aware that the Hebrew letter ${\displaystyle \aleph }$  (aleph) with various subscripts represents various infinite cardinal numbers, but fewer are aware that the second Hebrew letter ${\displaystyle \beth }$  (beth) also occurs and has significance. Let

${\displaystyle \beth _{0}=\aleph _{0}}$ 

be the cardinality of countably infinite sets; for concreteness, take the set N of natural numbers to be the typical case. Denote by P(A) the power set of A, i.e., the set of all subsets of A. Then define

${\displaystyle \beth _{\kappa +1}=2^{\beth _{\kappa }}}$ 

= the cardinality of the power set of A if ${\displaystyle \beth _{\kappa }}$  is the cardinality of A.

Thus

${\displaystyle \beth _{0},\ \beth _{1},\ \beth _{2},\ \beth _{3},\ \dots }$ 

are respectively the cardinalities of

${\displaystyle \mathbb {N} ,\ P(\mathbb {N} ),\ P(P(\mathbb {N} )),\ P(P(P(\mathbb {N} ))),\ \dots .}$ 

Each set in this sequence has cardinality strictly greater than the one preceding it.

More generally, for limit ordinals κ, we define

${\displaystyle \beth _{\kappa }=\sup\{\,\beth _{\lambda }:\lambda <\kappa \,\}.}$ 

If we assume the axiom of choice, then infinite cardinalities are linearly ordered; no two cardinalities can fail to be comparable, and so, since no infinite cardinalities are between ${\displaystyle \aleph _{0}}$  and ${\displaystyle \aleph _{1}}$ , the celebrated continuum hypothesis can be stated in this notation by saying

${\displaystyle \beth _{1}=\aleph _{1}.}$ 

The generalized continuum hypothesis says the sequence of "beth numbers" thus defined is the same as the sequence of aleph numbers.