## Online Encylopedia and Dictionary Research Site

Online Encyclopedia Search    Online Encyclopedia Browse

# Cantor's theorem

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 un-countably infinite. To illustrate the validity of Cantor's theorem for infinite sets, just test an infinite set in the proof below.

## 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

$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 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 yB, then yf(y) and therefore yB. Either way, we get a contradiction.

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

## A detailed explanation of the proof when X is countably infinite

To get a handle on the proof, let's examine it for the specific case when X is countably infinite. Without loss of generality, we may take X = N = {1, 2, 3,...}, the set of natural numbers.

Suppose that N is bijective with its power set P(N). Let us see a sample of what P(N) looks like:

$P(\mathbb{N})=\{\emptyset,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,...\},...\}$

Note that P(N) contains infinite subsets of N, e.g. the set of all even numbers {2, 4, 6,...}, as well as the empty set.

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

$X\begin{Bmatrix} 1 & \Longleftrightarrow & \{4, 5\}\\ 2 & \Longleftrightarrow & \{1, 2, 3\} \\ 3 & \Longleftrightarrow & \{4, 5, 6\} \\ 4 & \Longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}P(\mathbb{N})$

Take note that some natural numbers are paired with subsets that do not contain them. For instance, in our example the number 1 is paired with the subset {4, 5}. Other natural numbers are paired with subsets that do contain them. For instance, the number 2 is paired with the subset {1, 2, 3}.

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

Through this proof by contradiction we have proven that the cardinality of N and P(N) cannot be equal. We also know that the cardinality of P(N) cannot be less than the cardinality of N because P(N) contains all singletons, by definition, and these singletons form a "copy" of N inside of P(N). Therefore, only one possibility remains, and that is the cardinality of P(N) is strictly greater than the cardinality of N, 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.

Last updated: 10-24-2004 05:10:45