Content deleted Content added
m →Proof |
No edit summary |
||
Line 6:
In elementary [[set theory]], '''Cantor's theorem''' is a fundamental result which states that, for any [[Set (mathematics)|set]] <math>A</math>, the set of all [[subset]]s of <math>A</math> (the [[power set]] of <math>A</math>, denoted by <math>\mathcal{P}(A)</math>) has a strictly greater [[cardinality]] than <math>A</math> itself. For [[finite set]]s, 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> members has a total of <math>2^n</math> subsets, so that if <math>{\rm card}(A) = n,</math> then <math>{\rm card}(\mathcal{P}(A)) = 2^n</math>, 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, which showed that the theorem holds for [[infinite set|infinite]] sets, countable or uncountable, as well as finite ones. As a particularly important consequence, the power set of the set of [[natural number]]s, a [[countably infinite]] set with cardinality ℵ<sub>0</sub> = card(
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").
Line 38:
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 (theorem prover)|Otter]] could not do it, whereas [[Isabelle (proof assistant)|Isabelle]] could, albeit with a certain amount of direction in terms of tactics that might perhaps be considered cheating.<ref name="Paulson1992"/>
==When
Let us examine the proof for the specific case when <math>A</math> is [[countably infinite]]. [[Without loss of generality]], we may take
Suppose that
:<math>\mathcal{P}(\mathbb{N})=\{\varnothing,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,\dots\},\dots\}.</math>
𝒫('''
Now that we have an idea of what the elements of 𝒫('''
:<math>\mathbb{N}\begin{Bmatrix} 1 & \longleftrightarrow & \{4, 5\}\\ 2 & \longleftrightarrow & \{1, 2, 3\} \\ 3 & \longleftrightarrow & \{4, 5, 6\} \\ 4 & \longleftrightarrow & \{1, 3, 5\} \\ \vdots & \vdots & \vdots \end{Bmatrix}\mathcal{P}(\mathbb{N}).</math>
Line 53:
Given such a pairing, some natural numbers are paired with [[subset]]s that contain the very same number. For instance, in our example the number 2 is paired with the subset {1, 2, 3}, which contains 2 as a member. Let us call such numbers ''selfish''. Other natural numbers are paired with [[subset]]s that do not contain them. For instance, in our example the number 1 is paired with the subset {4, 5}, which does not contain the number 1. Call these numbers ''non-selfish''. Likewise, 3 and 4 are non-selfish.
Using this idea, let us build a special set of natural numbers. This set will provide the [[proof by contradiction|contradiction]] we seek. Let ''B'' be the set of ''all'' non-selfish natural numbers. By definition, the [[power set]] 𝒫('''
Since there is no natural number which can be paired with ''B'', we have contradicted our original supposition, that there is a [[bijection]] between '''
Note that the set ''B'' may be empty. This would mean that every natural number ''x'' maps to a subset of natural numbers that contains ''x''. Then, every number maps to a nonempty set and no number maps to the empty set. But the empty set is a member of 𝒫('''
Through this [[proof by contradiction]] we have proven that the [[cardinality]] of '''
==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)| \
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"/>
Line 71:
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
| |||