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

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

Si quieres conocer otros artículos parecidos a **Cantor's theorem** puedes visitar la categoría **1891 in science**.

Deja una respuesta