View source for Cantor theorem

The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202601.png" /> of all subsets of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202602.png" /> is not equipotent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202603.png" /> or to any subset of it. The idea behind the proof of this theorem, due to G. Cantor (1878), is called  "Cantor diagonalization process03E2003ExxCantor's diagonalization process"  and plays a significant role in set theory (and elsewhere). Cantor's theorem implies that no two of the sets

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202604.png" /></td> </tr></table>

are equipotent. In this way one obtains infinitely many distinct cardinal numbers (cf. [[Cardinal number|Cardinal number]]). Cantor's theorem also implies that the set of all sets does not exist. This means that one must not include among the axioms of set theory the assertion that for each propositional function (or predicate) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202605.png" /> there exists a set consisting of all elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202606.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202607.png" /> (see , , , ).

''B.A. Efimov''

Any decreasing sequence of non-empty bounded closed sets of real numbers has a non-empty intersection. This generalizes to compact subsets of a metric space. The property: If the diameters of a decreasing sequence of non-empty closed sets in a metric space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202608.png" /> tend to zero then the sets have non-empty intersection, is one of the definitions of completeness of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c0202609.png" />. The property that every totally ordered decreasing family of non-empty closed sets of a topological space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026010.png" /> has a non-empty intersection, is one of the definitions of compactness of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026011.png" /> (see , , , , ).

Every set of real numbers is the union of the perfect set of its condensation points (cf. [[Condensation point of a set|Condensation point of a set]]) and a countable set. This sometimes called the Cantor–Bendixson theorem. It generalizes to the case of a subset of a metric space with a countable basis (Lindelöf theorem, see , , , , , ).

If each of two sets is equipotent to a subset of the other, then these two sets are equipotent. A similar statement holds for two well-ordered sets. This is sometimes called the [[Cantor–Bernstein theorem]] or simply Bernstein's theorem (F. Bernshtein gave a correct proof of this theorem, see , , , , , ).

If

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026012.png" /></td> </tr></table>

for all but a finite number of points of interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026013.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026014.png" />. This generalizes to the case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026015.png" /> on a set of positive measure (Lebesgue's theorem), when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026016.png" /> on a set of the second category (Young's theorem), as well as to other situations. Important corollaries are various theorems on sets of uniqueness of trigonometric series (see , , , , , ).

A continuous function on a closed bounded interval of the real line is uniformly continuous on it. This generalizes to continuous mappings from a compact space to a [[Uniform space|uniform space]]. This is sometimes called the Heine–Cantor theorem (see [[#References|[1]]], [[#References|[4]]], [[#References|[5]]], [[#References|[13]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G. Cantor,   E. Zermelo (ed.) , ''Gesammelte Abhandlungen'' , Springer  (1932)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  F. Hausdorff,   "Grundzüge der Mengenlehre" , Leipzig  (1914)  (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  K. Kuratowski,   A. Mostowski,   "Set theory" , North-Holland  (1968)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  P.S. Aleksandrov,   "Einführung in die Mengenlehre und in die allgemeine Topologie" , Deutsch. Verlag Wissenschaft.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  N. Bourbaki,   "Elements of mathematics. General topology" , Addison-Wesley  (1966)  (Translated from French)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  N.K. [N.K. Bari] Bary,   "A treatise on trigonometric series" , Pergamon  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  E.T. Whittaker,   G.N. Watson,   "A course of modern analysis" , Cambridge Univ. Press  (1952)  pp. Chapt. 6</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  G. Cantor,   "Ein Beitrag zur Mannigfaltigkeitslehre"  ''J. Reine Angew. Math.'' , '''84'''  (1878)  pp. 242–258</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  G. Cantor,   "Über trigonometrische Reihen"  ''Math. Ann.'' , '''4'''  (1871)  pp. 139–143</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  G. Cantor,   "Beiträge zur Begründung des transfiniten Mengenlehre"  ''Math. Ann.'' , '''49'''  (1897)  pp. 207–246</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  G. Cantor,   "Über unendliche lineare Punktmannigfaltigkeiten"  ''Math. Ann.'' , '''17'''  (1880)  pp. 355–358</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  E. Borel,   "Leçons sur la théorie des fonctions" , Gauthier-Villars  (1928)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  E. Heine,   "Die Elemente der Funktionenlehre"  ''J. Reine Angew. Math.'' , '''74'''  (1872)  pp. 172–188</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  E. Lindelöf,   "Remarque sur une théorème fondamental de la théorie des ensembles"  ''Acta Math.'' , '''29'''  (1905)  pp. 183–190</TD></TR><TR><TD valign="top">[15a]</TD> <TD valign="top">  G. Cantor,   "Über eine die trigonometrischen Reihen betreffenden Lehrsatz"  ''J. Reine Angew. Math.'' , '''72'''  (1870)  pp. 130–138</TD></TR><TR><TD valign="top">[15b]</TD> <TD valign="top">  G. Cantor,   "Beweis, dass eine für jeden reellen Wert von <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026017.png" /> durch eine trigonometrische Reihe gegebene Funktion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026018.png" /> sich nur auf eine einzige Weise in dieser Form darstellen lässt"  ''J. Reine Angew. Math.'' , '''72'''  (1870)  pp. 139–142</TD></TR><TR><TD valign="top">[16]</TD> <TD valign="top">  G. Cantor,   "Über unendliche lineare Punktmannigfaltigkeiten"  ''Math. Ann.'' , '''21'''  (1883)  pp. 51–58</TD></TR><TR><TD valign="top">[17]</TD> <TD valign="top">  L. Bendixson,   "Quelques théorèmes de la théorie des ensembles de points"  ''Acta Math.'' , '''2'''  (1883)  pp. 415–429</TD></TR><TR><TD valign="top">[18]</TD> <TD valign="top">  H. Lebesgue,   "Leçons sur les séries trigonométriques" , Gauthier-Villars  (1906)</TD></TR><TR><TD valign="top">[19]</TD> <TD valign="top">  W.H. Young,   ''Proc. Roy. Soc.'' , '''87'''  (1912)  pp. 331–339</TD></TR><TR><TD valign="top">[20]</TD> <TD valign="top">  N. Bourbaki,   "Eléments d'histoire des mathématiques" , Hermann  (1960)</TD></TR></table>

''M.I. Voitsekhovskii''

====Comments====


1) Two sets are [[Equipotent sets|equipotent]] (equivalent) if there is a [[Bijection|bijection]] (a one-to-one onto mapping) between them. Intuitively this means that they have the same number of elements; in other words: They have (or are of) the same [[Cardinality|cardinality]]. Cantor's proof is as follows: Assume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026019.png" /> is a mapping; to show that it is not onto, consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026020.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026021.png" /> is not in the range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026022.png" />.

In an analogous way he showed that the set of real numbers is not [[Countable set|countable]]: Assume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026023.png" /> is a mapping and write <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026024.png" /> in decimal expansion. Define <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026025.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026026.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026028.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026029.png" />. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026030.png" /> is not in the range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026031.png" />. This last proof best explains the name  "diagonalization processdiagonalization process"  or  "diagonal argumentdiagonal argument" .

4) This theorem is also called the Schroeder–Bernstein theorem. A similar statement does not hold for totally ordered sets, consider <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c020/c020260/c02026033.png" />.

For general historical information see [[#References|[20]]]. For set of the second category cf. [[Category of a set|Category of a set]].