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

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

Cantor gave essentially this proof in a paper published in 1891 ("Ueber eine elementare Frage der Mannigfaltigkeitslehre"), where the diagonal argument for the uncountability of the reals also first appears. The version of this argument he gave in that paper was phrase in terms of indicator functions on a set rather than subsets of a set. He showed 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.

For one consequence of Cantor's theorem, see beth numbers.