Editing Cantor's theorem (section)

==Related paradoxes==
Cantor's theorem and its proof are closely related to two [[paradoxes of set theory]].

[[Cantor's paradox]] is the name given to a contradiction following from Cantor's theorem together with the assumption that there is a set containing all sets, the [[universal set]] <math>V</math>. In order to distinguish this paradox from the next one discussed below, it is important to note what this contradiction is. By Cantor's theorem <math>|\mathcal{P}(X)| > |X|</math> for any set <math>X</math>. On the other hand, all elements of <math>\mathcal{P}(V)</math> are sets, and thus contained in <math>V</math>, therefore <math>|\mathcal{P}(V)| \leq |V|</math>.<ref name="Dasgupta2013"/>

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'':<ref name="Dasgupta2013"/>

:<math>R_A=\left\{\,x\in A : x\not\in x\,\right\}.</math>

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 ''R''<sub>''U''</sub> leads to the contradiction:
:<math>R_U \in R_U \iff R_U \notin R_U.</math>

This argument is known as [[Russell's paradox]].<ref name="Dasgupta2013"/> As a point of subtlety, the version of Russell's paradox we have presented here is actually a theorem of [[Zermelo]];<ref name="Ebbinghaus2007"/> we can conclude from the contradiction obtained that we must reject the hypothesis that ''R''<sub>''U''</sub>∈''U'', thus disproving the existence of a set containing all sets. This was possible because we have used [[Axiom schema of specification|restricted comprehension]] (as featured in [[ZFC]]) in the definition of ''R''<sub>''A''</sub> above, which in turn entailed that

:<math>R_U \in R_U \iff (R_U \in U \wedge R_U \notin R_U). </math>

Had we used [[unrestricted comprehension]] (as in [[Frege]]'s system for instance) by defining the Russell set simply as <math>R=\left\{\,x : x\not\in x\,\right\}</math>, then the axiom system itself would have entailed the contradiction, with no further hypotheses needed.<ref name="Ebbinghaus2007">{{cite book|author=Heinz-Dieter Ebbinghaus|title=Ernst Zermelo: An Approach to His Life and Work|url=https://archive.org/details/ernstzermeloappr00ebbi_571|url-access=limited|year=2007|publisher=Springer Science & Business Media|isbn=978-3-540-49553-6|pages=[https://archive.org/details/ernstzermeloappr00ebbi_571/page/n97 86]–87}}</ref>

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.<ref>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.</ref>