Der Satz von Cantor
Satz (Satz von Cantor über die Potenzmengenoperation)
Sei M eine Menge, ℘(M) = { X | X ⊆ M } die Potenzmenge von M.
Dann gilt |M| < |℘(M)|.
Beweis
Zunächst gilt |M| ≤ |℘(M)|, denn die Funktion F : M → ℘(M) mit F(x) = { x } für alle x ∈ M ist injektiv.
Sei nun f : M → ℘(M) beliebig. Es genügt zu zeigen: f ist nicht surjektiv.
Wir setzen:
D = { x ∈ M | x ∉ f (x) }.
Dann ist D ∈ ℘(M). Annahme, D ∈ rng(f). Sei also y ∈ M mit f (y) = D. Dann gilt:
y ∈ D gdw y ∉ f (y) gdw y ∉ D,
ersteres nach Definition von D, letzteres wegen f (y) = D. Widerspruch!
Wegen |ℝ| = |℘(ℕ)| und |𝔉| = |℘(ℝ)| liefert der Satz von Cantor auch einen neuen Beweis für die Überabzählbarkeit von ℝ und für |ℝ| < |𝔉|.
Im zweiten Teil des Beweises wird rng(f) ⊆ ℘(M) nicht gebraucht. Der Beweis zeigt allgemein, dass wir für jede Menge M und jede Funktion f auf M eine Menge D ⊆ M definieren können, die nicht im Wertebereich von f liegt:
Korollar (Lücken im Wertebereich)
Sei M eine Menge, und sei f eine Funktion mit dom(f) = M.
Dann gilt { x ∈ M | x ∉ f (x) } ∉ rng(f).
Wie kommt man auf die Menge D = { x ∈ M | x ∉ f (x) }? Bei genauerem Hinsehen erweist sich die Konstruktion von D als eine Diagonalisierung, wie sie uns in den Beweisen der Überabzählbarkeit von ℝ und von |ℝ| < |𝔉| bereits begegnet ist: Wir identifizieren eine Teilmenge A von M mit ihrer Indikatorfunktion indA, M : M → { 0, 1 } , wobei wieder indA, M(x) = 1 gdw x ∈ A. Die Potenzmenge von M wird dann zu M{ 0, 1 } , der Menge aller Indikatorfunktionen auf M.
Sei nun f : M → M{ 0, 1 }. Wir suchen ein d ∈ M{ 0, 1 } mit f (x) ≠ d für alle x ∈ M. Wir können aber d verschieden von allen f (x) konstruieren durch:
für alle x ∈ M. Dann gilt d(x) ≠ f (x)(x) für alle x ∈ M, also ist d ∉ rng(f).
Die Senkrechte des Diagramms repräsentiert M. Die Waagrechten seitlich der Senkrechten stehen für Funktionen f (x) ∈ M{0, 1} , die man sich als 0-1-Folgen vorstellen kann. Die oberste Waagrechte ist der Definitionsbereich dieser Funktionen.
Die Diagonale steht für die konstruierte Funktion d ∈ M{ 0, 1 } − ebenfalls eine 0-1-Folge. d ist in jedem x ∈ M verschieden von f (x), d. h. es gilt f (x)(x) ≠ d(x). f (x)(x) ist der Wert der 0-1-Folge f (x) an der Stelle x, d. h. der Wert der Waagrechten f (x) an ihrem Schnittpunkt mit d. d ist dort gerade verschieden von diesem Wert, also ist d sicher nicht gleich f (x). Und dies gilt für alle x ∈ M.
Übung
Sei M = { 0, 1, 2, 3 }. Bestimmen Sie D ⊆ M wie im obigem Beweis für die Funktion f : M → ℘(M) mit f (0) = { 1, 3 } , f (1) = { 0, 2 } , f (2) = { 1, 2 } , f (3) = { 0, 1, 2 }. Zeichnen Sie zudem obiges Diagramm für diese Situation mit 0-1-Folgen für f (x) und bestimmen Sie d.
Durch iterierte Anwendung der Potenzmengenoperation können wir nun, ausgehend von einer beliebigen Menge, Mengen mit immer größerer Mächtigkeit erzeugen:
Sei M eine Menge. Wir definieren ℘n(M) für n ∈ ℕ rekursiv durch
℘0(M) = M,
℘n + 1(M) = ℘(℘n(M)) für n ∈ ℕ.
Dann gilt |℘n(M)| < |℘n + 1(M)| für alle n ∈ ℕ. Sei weiter
M* = ⋃n ∈ ℕ ℘n(M).
Dann gilt |℘n(M)| < |℘n + 1(M)| ≤ |M*| für alle n ∈ ℕ. Durch die Vereinigung der Mengen
M, ℘(M), ℘2(M), …
finden wir also eine Menge M* von noch größerer Mächtigkeit. Wir können nun wieder ℘(M*) bilden und haben |M*| < |℘(M*)|, usw. usf. Was hier genau „usw. usf.“ bedeutet, wird erst später klar werden, wenn wir die transfiniten Zahlen zur Verfügung haben.