thumb|The cardinality of the set {x, y, z}, is three, while there are eight elements in its power set (3 < 2<sup title="Order theory">3</sup> = 8), here [[order theory|ordered by inclusion.]]

In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set <math>A</math>, the set of all subsets of <math>A,</math> known as the power set of <math>A,</math> has a strictly greater cardinality than <math>A</math> itself.

For finite sets, Cantor's theorem can be seen to be true by simple enumeration of the number of subsets. Counting the empty set as a subset, a set with <math>n</math> elements has a total of <math>2^n</math> subsets, and the theorem holds because <math>2^n > n</math> for all non-negative integers.

Much more significant is Cantor's discovery of an argument that is applicable to any set, and shows that the theorem holds for infinite sets also. As a consequence, the cardinality of the real numbers, which is the same as that of the power set of the integers, is strictly larger than the cardinality of the integers; see Cardinality of the continuum for details.

The theorem is named for Georg Cantor, who first stated and proved it at the end of the 19th century. Cantor's theorem had immediate and important consequences for the philosophy of mathematics. For instance, by iteratively taking the power set of an infinite set and applying Cantor's theorem, we obtain an endless hierarchy of infinite cardinals, each strictly larger than the one before it. Consequently, the theorem implies that there is no largest cardinal number (colloquially, "there's no largest infinity").

Proof

Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.

By definition of cardinality, we have <math>\operatorname{card}(X) < \operatorname{card}(Y)</math> for any two sets <math>X</math> and <math>Y</math> if and only if there is an injective function but no bijective function from <math>X</math> It suffices to show that there is no surjection from <math>X</math> . This is the heart of Cantor's theorem: there is no surjective function from any set <math>A</math> to its power set. To establish this, it is enough to show that no function <math>f</math> (that maps elements in <math>A</math> to subsets of <math>A</math>) can reach every possible subset, i.e., we just need to demonstrate the existence of a subset of <math>A</math> that is not equal to <math>f(x)</math> for any <math>x \in A</math>. Recalling that each <math>f(x)</math> is a subset of <math>A</math>, such a subset is given by the following construction, sometimes called the Cantor diagonal set of <math>f</math>:

:<math>B=\{x\in A \mid x\not\in f(x)\}.</math>

This means, by definition, that for all <math>x\in A</math>, <math>x\in B</math> if and only if <math>x\notin f(x)</math>. For all <math>x</math> the sets <math>B</math> and <math>f(x)</math> cannot be equal because <math>B</math> was constructed from elements of <math>A</math> whose images under <math>f</math> did not include themselves. For all <math>x\in A</math> either <math>x\in f(x)</math> or <math>x\notin f(x)</math>. If <math>x\in f(x)</math> then <math>f(x)</math> cannot equal <math>B</math> because <math>x\in f(x)</math> by assumption and <math>x\notin B</math> by definition. If <math>x\notin f(x)</math> then <math>f(x)</math> cannot equal <math>B</math> because <math>x\notin f(x)</math> by assumption and <math>x\in B</math> by the definition of <math>B</math>.

Equivalently, and slightly more formally, we have just proved that the existence of <math>\xi \in A</math> such that <math>f(\xi )=B</math> implies the following contradiction:

:<math>\begin{aligned}

\xi\in B &\iff \xi\notin f(\xi) && \text{(by definition of }B\text{)}; \\

\xi \in B &\iff \xi \in f(\xi) && \text{(by assumption that }f(\xi)=B\text{)}. \\

\end{aligned}</math>

Therefore, by reductio ad absurdum, the assumption must be false. Each row records the values of the indicator function of the set corresponding to the column. The indicator function of <math>B</math> coincides with the logically negated (swap "true" and "false") entries of the main diagonal. Thus the indicator function of <math>B</math> does not agree with any column in at least one entry. Consequently, no column represents <math>B</math>.

Despite the simplicity of the above proof, it is rather difficult for an automated theorem prover to produce it. The main difficulty lies in an automated discovery of the Cantor diagonal set. Lawrence Paulson noted in 1992 that Otter could not do it, whereas Isabelle could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating.

Despite the syntactical similarities between the Russell set (in either variant) and the Cantor diagonal set, Alonzo Church emphasized that Russell's paradox is independent of considerations of cardinality and its underlying notions like one-to-one correspondence.

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 &minus; f(x)(x) is not in the range of f.

Bertrand Russell has a very similar proof in Principles of Mathematics (1903, section 348), where he shows 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.

Generalizations

Lawvere's fixed-point theorem provides for a broad generalization of Cantor's theorem to any category with finite products in the following way: let <math>\mathcal{C}</math> be such a category, and let <math>1</math> be a terminal object in <math>\mathcal{C}</math>. Suppose that <math>Y</math> is an object in <math>\mathcal{C}</math> and that there exists an endomorphism <math>\alpha : Y \to Y</math> that does not have any fixed points; that is, there is no morphism <math>y:1 \to Y</math> that satisfies <math>\alpha \circ y = y</math>. Then there is no object <math>T</math> of <math>\mathcal{C}</math> such that a morphism <math>f: T \times T \to Y</math> can parameterize all morphisms <math>T \to Y</math>. In other words, for every object <math>T</math> and every morphism <math>f : T \times T \to Y</math>, an attempt to write maps <math>T \to Y</math> as maps of the form <math>f(-,x) : T \to Y</math> must leave out at least one map <math>T \to Y</math>.

See also

  • Schröder–Bernstein theorem
  • Cantor's first uncountability proof
  • Controversy over Cantor's theory

References

  • Halmos, Paul, Naive Set Theory. Princeton, NJ: D. Van Nostrand Company, 1960. Reprinted by Springer-Verlag, New York, 1974. (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. (Paperback edition).