Nachlesen

Satz von Cantor

Beim Satz von Cantor handelt es sich um einen Lehrsatz aus der Mengentheorie, der besagt, dass eine Menge stets weniger mächtig als ihre Potenzmenge ist. Er wurde am Ende des 19. Jahrhunderts vom deutschen Mathematiker Georg Cantor aufgestellt.

Inhalt

Definition
Beweis

Definition

Sei \(A\) eine Menge und \(\mathcal{P}(A) = \bigl\{ X \mid X \subseteq A \bigr\}\) die Potenzmenge von \(A\). Dann ist \(A\) stets weniger mächtig als \(\mathcal{P}(A)\), d. h., es gilt

|A| \lt |\mathcal{P}(A)|.

Beweis

Beweis für die leere Menge

Für die leere Menge gilt \(|\emptyset| = 0\). Für die Potenzmenge der leeren Menge gilt \(\mathcal{P}(\emptyset) = \bigl\{ \emptyset \bigr\}\) und somit \(|\mathcal{P}(\emptyset)| = 1\), woraus sofort \(|\emptyset| \lt |\mathcal{P}(\emptyset)|\) folgt.

Beweis für (nichtleere) endliche Mengen

Sei \(A\) eine nichtleere endliche Menge mit \(n \in \N\) Elementen, d. h., es gelte \(|A|=n\). Die Potenzmenge \(\mathcal{P}(A)\) besitzt dann genau \(|\mathcal{P}(A)| = 2^n\) Elemente. Da für alle natürlichen Zahlen \(n\) stets \(n \lt 2^n\) gilt (dies kann unter anderem mittels vollständiger Induktion gezeigt werden), folgt hieraus unmittelbar der Satz von Cantor (für endliche Mengen).

Beweis für (nichtleere) allgemeine Mengen

Sei \(A\) eine nichtleere Menge und sei \(\mathcal{P}(A)\) die zugehörige Potenzmenge. Um zu zeigen, dass die Potenzmenge \(\mathcal{P}(A)\) mächtiger als die Menge \(A\) ist, müssen zwei Eigenschaften gezeigt werden:

Es existieren injektive Abbildungen \(A \rightarrow \mathcal{P}(A)\).
Es existieren keine surjektiven Abbildungen \(A \rightarrow \mathcal{P}(A)\).

Aus der Existenz injektiver Abbildungen folgt \(|A| \leq |\mathcal{P}(A)|\). Aus der Nichtexistenz surjektiver Abbildungen folgt, dass auch keine bijektiven Abbildungen existieren, und dass somit nicht \(|A| = |\mathcal{P}(A)|\) gelten kann. Aus diesen beiden Aussagen folgt unmittelbar die Kernaussage \(|A| \lt |\mathcal{P}(A)|\) des Satzes von Cantor.

Nachweis der Existenz injektiver Abbildungen

Für eine nichtleere Menge \(A\) ist die Abbildung \(A \rightarrow \mathcal{P}(A)\) mit \(a \mapsto \bigl\{ a \bigr\}\) eine injektive Abbildung, da für \(a_1,a_2 \in A\) mit \(a_1 \neq a_2\) stets \(\bigl\{ a_1 \bigr\} \neq \bigl\{ a_2 \bigr\}\) folgt.

Nachweis der Nichtexistenz surjektiver Abbildungen

Der Nachweis der Nichtexistenz surjektiver Abbildungen wird mithilfe eines Widerspruchsbeweises geführt. Angenommen, \(f: A \rightarrow \mathcal{P}(A)\) sei eine surjektive Abbildung. Dann muss für jede beliebige Menge \(M \in \mathcal{P}(A)\) (dies ist gleichbedeutend mit \(M \subseteq A\)) ein Urbild in der Menge \(A\) existieren, das auf \(M\) abgebildet wird. Dies muss insbesondere auch für die Menge

M = \Bigl\{ a \in A \mid a \notin f(a) \Bigr\}

gelten, also für die Menge derjenigen Elemente \(a \in A\), die auf eine Menge \(f(a) \in \mathcal{P}(A)\) abgebildet werden, in der sie selbst nicht enthalten sind.

Sei \(\alpha \in A\) ein Urbild von \(M\), das aufgrund der Surjektivität von \(f\) garantiert existiert, d. h., es gelte \(f(\alpha) = M\). Hieraus ergeben sich zwei Möglichkeiten:

\(\alpha \in f(\alpha) = M\); aufgrund der Konstruktion der Menge \(M\) müsste dann aber \(\alpha \notin M\) gelten, was einen Widerspruch darstellt.
\(\alpha \notin f(\alpha) = M\); aufgrund der Konstruktion der Menge \(M\) müsste dann aber \(\alpha \in M\) gelten, was ebenfalls einen Widerspruch darstellt.

Zusammengefasst lässt sich dieser Widerspruch auch wie folgt darstellen:

\alpha \in f(\alpha) = M \quad\Leftrightarrow\quad \alpha \notin f(\alpha).

Dieser Widerspruch zeigt, dass ein Urbild \(\alpha \in A\) von \(M\) nicht existieren kann – und dass die Abbildung \(f\) somit nicht surjektiv sein kann.