Cantor's theorem
From Wikipedia, the free encyclopedia
- 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 elementary 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. The theorem is named for Georg Cantor, who first stated and proved it.
Contents |
[edit] The proof
Let f be any function from A into the power set of A. To establish Cantor's theorem it must be shown that f is necessarily not surjective. To do that, it is enough to exhibit an element of the power set of A, that is, a subset of A, that is not in the image of f. Such a subset can be constructed as follows. Take subset B of A defined by:
This means, by definition, that for all x in A, x ∈ B if and only if x ∉ f(x), so for all x the sets B and f(x) are different. There is no x such that f(x) = B; in other words, B is not in the image of f.
Because of the double occurrence of x in the expression "x ∉ f(x)", this is a diagonal argument.
[edit] 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(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:
Given such a pairing, some natural numbers are paired with subsets that contain the very same number. For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a member. Let us call such numbers selfish. Other 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}, which does not contain the number 1. Call these numbers non-selfish. Likewise, 3 and 4 are non-selfish.
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 non-selfish natural numbers. By definition, the power set P(N) contains all sets of natural numbers, and so it contains this set D as an element. Therefore, D must be paired off with some natural number, say d. However, this causes a problem. If d is selfish, then number d cannot be a member of D, since D was defined to contain only non-selfish numbers. But then d is non-selfish, because it is not a member of D. On the other hand, if d is non-selfish, then . . . well, then it must be contained in D, 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.
Note that the set D may be empty. This would mean that every natural number x maps to a set of natural numbers that contains x. Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of P(N), so the mapping still does not cover P(N).
[edit] History
Cantor gave essentially this proof in a paper published in 1891 Über 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, 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.
[edit] See also
[edit] References
- Paul Halmos, Naive set theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. ISBN 0-387-90092-6 (Springer-Verlag edition).
- Jech, Thomas, 2003. Set Theory: The Third Millennium Edition, Revised and Expanded. Springer. ISBN 3-540-44085-2.
