Cantor's Theorem

The Cantor's theorem states that a lot less powerful than their power set (the set of all subsets is) so that applies. It comes from the mathematician Georg Cantor and is a generalization of Cantor's second diagonal argument . The theorem is valid in all models that satisfy the axiom of disposal . ${\displaystyle \,A}$ ${\displaystyle {\mathcal {P}}(A)}$ ${\displaystyle |A|<|{\mathcal {P}}(A)|}$

Comment: The theorem applies to all sets, especially also to the empty set, because it is one-element. In general, for finite sets, the power set of a -element set has elements. Cantor's theorem is always clear for finite sets, but it also applies to infinite sets. ${\displaystyle {\mathcal {P}}(\emptyset )=\{\emptyset \}}$ ${\displaystyle n}$ ${\displaystyle 2^{n}}$ ${\displaystyle n<2^{n}}$

proof

Obviously , since is an injective mapping . ${\displaystyle |A|\leq |{\mathcal {P}}(A)|}$ ${\displaystyle x\mapsto \{x\}}$ ${\displaystyle A\to {\mathcal {P}}(A)}$

We now want to show that there can be no surjective mapping . ${\displaystyle A\to {\mathcal {P}}(A)}$

To get a contradiction, we assume that there is a surjective mapping after all . ${\displaystyle f\colon A\to {\mathcal {P}}(A)}$

We define now . Because of the axiom of exclusion, there is a lot and thus . Because of the assumption that is surjective, there is an with . Then, according to the definition of : ${\displaystyle M:=\{x\in A\mid x\not \in f(x)\}}$ ${\displaystyle M}$ ${\displaystyle M\in {\mathcal {P}}(A)}$ ${\displaystyle f}$ ${\displaystyle a\in A}$ ${\displaystyle f(a)=M}$ ${\displaystyle M}$

${\displaystyle a\in f(a)=M\,\iff a\notin f(a)}$

This contradiction shows that the assumption is wrong and there can be no surjective mapping - but then there can certainly be no bijective mapping, which excludes the case , and we know . ${\displaystyle A\to {\mathcal {P}}(A)}$ ${\displaystyle |A|=|{\mathcal {P}}(A)|}$ ${\displaystyle |A|<|{\mathcal {P}}(A)|}$

Historical

Cantor provided the first proof in his treatise On an Elementary Question in the Theory of Manifolds from 1890. For this he showed that the set of all functions is more powerful than itself, with the set of functions having the same power as the power set of (see power set # Characteristic Functions ). Further evidence comes from Felix Hausdorff in Basics of Set Theory (1914) and from Ernst Zermelo in Studies on the Fundamentals of Set Theory (1908). ${\displaystyle g\colon A\to {\mathcal {\{}}0,1\}}$ ${\displaystyle A}$ ${\displaystyle g}$ ${\displaystyle A}$

Related to Cantor's other work

One can also prove Cantor's second diagonal argument using Cantor's Theorem if we know that . Because then is . ${\displaystyle |\mathbb {R} |=|{\mathcal {P}}(\mathbb {N} )|}$ ${\displaystyle |\mathbb {N} |<|\mathbb {R} |=|{\mathcal {P}}(\mathbb {N} )|}$

Furthermore, Cantor's theorem shows Cantor's second antinomy . This says that the all-class is not a set, but a real class . Because by definition the power set of the universal class would be a subset of the same, which contradicts Cantor's theorem. ${\displaystyle \{x\mid x=x\}}$

swell

• Introduction to set theory by Oliver Deiser. Springer, Berlin Heidelberg 2004, 2nd edition. ISBN 978-3-540-20401-5