Cantor's theorem

Cantor's theorem For other theorems bearing Cantor's name, see Cantor's theorem (disambiguation). The cardinality of the set {x, y, z}, is three, while there are eight elements in its power set (3 < 23 = 8), here ordered by inclusion. This article contains special characters. Without proper rendering support, you may see question marks, boxes, or other symbols. In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set {displaystyle A} , the set of all subsets of {displaystyle A,} the power set of {displaystyle A,} has a strictly greater cardinality than {displaystyle A} 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 {displaystyle n} elements has a total of {displaystyle 2^{n}} subsets, and the theorem holds because {displaystyle 2^{n}>n} 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 German mathematician 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").

Contents 1 Proof 2 When A is countably infinite 3 Related paradoxes 4 History 5 Generalizations 6 See also 7 References 8 External links Proof Cantor's argument is elegant and remarkably simple. The complete proof is presented below, with detailed explanations to follow.

Theorem (Cantor) — Let {displaystyle f} be a map from set {displaystyle A} to its power set {displaystyle {mathcal {P}}(A)} . Then {displaystyle f:Ato {mathcal {P}}(A)} is not surjective. As a consequence, {displaystyle operatorname {card} (A)|X|} for any set {displaystyle X} . On the other hand, all elements of {displaystyle {mathcal {P}}(V)} are sets, and thus contained in {displaystyle V} , therefore {displaystyle |{mathcal {P}}(V)|leq |V|} .[1] Another paradox can be derived from the proof of Cantor's theorem by instantiating the function f with the identity function; this turns Cantor's diagonal set into what is sometimes called the Russell set of a given set A:[1] {displaystyle R_{A}=left{,xin A:xnot in x,right}.} The proof of Cantor's theorem is straightforwardly adapted to show that assuming a set of all sets U exists, then considering its Russell set RU leads to the contradiction: {displaystyle R_{U}in R_{U}iff R_{U}notin R_{U}.} This argument is known as Russell's paradox.[1] As a point of subtlety, the version of Russell's paradox we have presented here is actually a theorem of Zermelo;[4] we can conclude from the contradiction obtained that we must reject the hypothesis that RU∈U, thus disproving the existence of a set containing all sets. This was possible because we have used restricted comprehension (as featured in ZFC) in the definition of RA above, which in turn entailed that {displaystyle R_{U}in R_{U}iff (R_{U}in Uwedge R_{U}notin R_{U}).} Had we used unrestricted comprehension (as in Frege's system for instance) by defining the Russell set simply as {displaystyle R=left{,x:xnot in x,right}} , then the axiom system itself would have entailed the contradiction, with no further hypotheses needed.[4] 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.[5] History Cantor gave essentially this proof in a paper published in 1891 "Über eine elementare Frage der Mannigfaltigkeitslehre",[6] 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.

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 Cantor's theorem has been generalized to any category with products.[7] See also Schröder–Bernstein theorem Cantor's first uncountability proof Controversy over Cantor's theory References ^ Jump up to: a b c d Abhijit Dasgupta (2013). Set Theory: With an Introduction to Real Point Sets. Springer Science & Business Media. pp. 362–363. ISBN 978-1-4614-8854-5. ^ Jump up to: a b Lawrence Paulson (1992). Set Theory as a Computational Logic (PDF). University of Cambridge Computer Laboratory. p. 14. ^ Jump up to: a b Graham Priest (2002). Beyond the Limits of Thought. Oxford University Press. pp. 118–119. ISBN 978-0-19-925405-7. ^ Jump up to: a b Heinz-Dieter Ebbinghaus (2007). Ernst Zermelo: An Approach to His Life and Work. Springer Science & Business Media. pp. 86–87. ISBN 978-3-540-49553-6. ^ Church, A. [1974] "Set theory with a universal set." in Proceedings of the Tarski Symposium. Proceedings of Symposia in Pure Mathematics XXV, ed. L. Henkin, Providence RI, Second printing with additions 1979, pp. 297−308. ISBN 978-0-8218-7360-1. Also published in International Logic Review 15 pp. 11−23. ^ Cantor, Georg (1891), "Über eine elementare Frage der Mannigfaltigskeitslehre", Jahresbericht der Deutschen Mathematiker-Vereinigung (in German), 1: 75–78, also in Georg Cantor, Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, E. Zermelo, 1932. ^ F. William Lawvere; Stephen H. Schanuel (2009). Conceptual Mathematics: A First Introduction to Categories. Cambridge University Press. Session 29. ISBN 978-0-521-89485-2. Halmos, Paul, 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). Reprinted by Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (Paperback edition). Jech, Thomas (2002), Set Theory, Springer Monographs in Mathematics (3rd millennium ed.), Springer, ISBN 3-540-44085-2 External links "Cantor theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994] Weisstein, Eric W. "Cantor's Theorem". MathWorld. show vte Metalogic and metamathematics show vte Set theory show vte Mathematical logic Categories: 1891 introductions1891 in scienceSet theoryTheorems in the foundations of mathematicsCardinal numbersGeorg Cantor