The Cantor's theorem reference article from the English Wikipedia on 24-Jul-2004
(provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Cantor's theorem

You can make a difference by sponsoring a child

Note: in order to fully understand this article you may want to refer to the set theory portion of the Table of mathematical symbols.

In Zermelo-Fränkel set theory, Cantor's theorem states that the power set (set of all subsets) of any set A has a strictly greater cardinality than that of A. Cantor's theorem is obvious for finite sets, but surprisingly it holds true for infinite sets as well. In particular, the power set of a countably infinite set is uncountably infinite. To illustrate the validity of Cantor's theorem for infinite sets, just test an infinite set in the proof below.

Table of contents
1 The proof
2 A more concrete account of the same proof of Cantor's theorem
3 History

The proof

The proof is a quick diagonal argument. Let f be any one-to-one function from A into the power set 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 yA, we have f(y) = B. Now consider whether yB or not. If yB, then yf(y), but that implies, by definition of B, that yB. On the other hand if it is yB, then yf(y) and therefore yB. Either way, we get a contradiction.

Because of the double occurrence of x in the expression "xx", this is a diagonal argument.

A more concrete account of the same proof of Cantor's theorem

Here is a more concrete explanation of the proof of Cantor's theorem given above, which is perhaps easier to understand. This is merely an expanded version of the above proof. Once again this is a proof by contradiction, where we suppose something is true and then by contradiction prove that it is not. Let's suppose that an infinite set X is bijective with its power set P(X). By definition this means that the cardinality of X is equal to the cardinality of P(X).

Let us define X as the following infinite set:

Each letter represents an element of the infinite set X (note that the set does not stop at z, it continues on infinitely with letter and number combinations i.e. ...a2, b2,...).

Let us see a sample of what P(X) looks like:

Now that we know what we are dealing with let us attempt to pair off each element of X with each element of P(X) to show that these infinite sets are bijective. In other words we will attempt to pair off each element of the infinite set X with an element from the infinite set P(X) so that no element from either infinite set remains unpaired. Such an attempt to pair off each element would look like this:

Take note that some elements of X are paired with subsets that do not contain them. For instance, in our example the element is paired with the subset . Other elements of X are paired with subsets that do contain them. For instance, the element is paired with the subset .

Using this idea, let us build a special subset. Let us build a subset D which consists of all elements of X which are paired with subsets that do not contain them. By definition our power set P(X) must contain this subset D. Therefore, this subset \D must be placed in our column of subsets to be paired off. However, this causes a problem because with what element of X can D be paired with? If we pair an element of X off with D we must decide whether or not to place this element into D. If we decide to keep this element out of D we are immediately forced to place it into D by the very definition of D. Once we place the element into D we are immediately forced to remove the element from D, once again by the definition of D. This is a contradiction because the element cannot be both inside and outside of D at the same time. Therefore, there is no element of X which can be paired with D and we have contradicted our original supposition, that there is a bijection between X and P(X).

Through this proof by contradiction we have proven that the cardinality of X and P(X) can not be equal. We also know that the cardinality of P(X) can not be less than the cardinality of X because P(X) contains all of the singletons of X, by definition. Therefore, only one possibility remains and that is the cardinality of P(X) is greater than the cardinality of X, and this proves Cantor's theorem.

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 (he had earlier proved the uncountability of the reals by other methods). The version of this argument he gave in that paper was phrased 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.