Überabzählbare Mengen

Unsere Diskussion lässt offen, ob nicht jede unendliche Menge abzählbar ist, sodass es, wie man vielleicht erwarten würde, im Unendlichen keine Größenunterschiede gibt. Dies ist aber nicht der Fall. Das fundamentale Ergebnis, das wie die Irrationalität der Quadratwurzel aus 2 Eingang in den Grundkreis der mathematischen Bildung gefunden hat, ist, dass die reellen Zahlen ℝ im Gegensatz zu ℕ, ℤ, ℚ, 𝔸, Seq, … nicht mehr abzählbar sind. Wir definieren hierzu:

Definition (überabzählbar)

Eine Menge A heißt überabzählbar, falls A nicht abzählbar ist.

Das Herz der Theorie der überabzählbaren Mengen ist:

Satz (Diagonalkonstruktion von Georg Cantor)

Sei (x_n)_n ∈ ℕ eine Folge in ℝ. Dann gibt es ein x*  ∈  ℝ mit der Eigenschaft:

x* ≠ x_n für alle n ≥ 0.

Der folgende Beweis ist konstruktiv: Wir können x* konkret angeben, wenn die Folgenglieder x_n bekannt sind. Die Idee ist, x* schrittweise so zu lokalisieren, dass im n-ten Schritt x* ≠ x_n sichergestellt wird. Wir weichen der Folge in diesem Sinne aus (um nicht zu sagen, dass wir sie austricksen).

Beweis

Wir schreiben in Dezimaldarstellung

x₀	= ± m₀, a_{0, 0} a_{0, 1} a_{0, 2} …
x₁	= ± m₁, a_{1, 0} a_{1, 1} a_{1, 2} …
x₂	= ± m₂, a_{2, 0} a_{2, 1} a_{2, 2} …
…
x_n	= ± m_n, a_{n, 0} a_{n, 1} a_{n, 2} …
…

mit Dezimalziffern a_{n, m}  ∈  { 0, …, 9 }. (Dabei können wir im zweideutigen Fall irgendeine der beiden Dezimaldarstellungen von x_n verwenden.)

Für alle n  ∈  ℕ definieren wir nun

$d_{n} = { \begin{matrix} 1 & falls d_{n, n} \neq 1, \\ 2 & falls d_{n, n} = 1. \end{matrix}$

Schließlich setzen wir, wieder in Dezimaldarstellung

x* = 0, d₀ d₁ d₂ … d_n …

Dann ist x* eine reelle Zahl, die eine eindeutige Dezimaldarstellung besitzt (da die Ziffern d_n nicht in 0 oder 9 terminieren). Nach Konstruktion ist die Darstellung von x* für jedes n von der Darstellung von x_n verschieden. Aufgrund der Eindeutigkeit der Darstellung von x* ist also x* ≠ x_n für alle n.

Ein wichtiges Detail des Beweises ist die Definition der Nachkommaziffern von x*. Wir können statt 1, 2 zum Beispiel auch 3, 7 verwenden. Nicht geeignet sind dagegen 0 und 1. Denn für d_n  ∈  { 0, 1 } ist nicht mehr garantiert, dass die Darstellung von x* eindeutig ist.

Wir erhalten:

Korollar (Überabzählbarkeit der reellen Zahlen)

ℝ ist überabzählbar.

Beweis

Annahme, ℝ ist abzählbar. Dann gibt es eine Aufzählung (x_n)_n ∈ ℕ von ℝ. Ist nun x* wie in der Diagonalkonstruktion, so ist x* kein Element der Aufzählung, Widerspruch.

Wir können das Ergebnis kurz und ohne jede Verwendung von philosophisch belasteten Begriffen so zusammenfassen:

Jede Folge x₀, x₁, …, x_n, … reeller Zahlen lässt eine reelle Zahl aus.

Der Rest ist Interpretation. Und diese Interpretation hängt vom gewählten Rahmen ab, der letztendlich durch die Axiome der Mengenlehre gegeben wird. In diesem Rahmen lautet die Interpretation:

Es gibt Größenunterschiede im Unendlichen.

Untermauert wird diese Interpretation durch den folgenden bestechend allgemeinen Satz:

Satz (Satz von Cantor)

Sei A eine Menge, und sei f : A → ℘(A). Dann ist f nicht surjektiv.

Beweis

Wir definieren D  ∈  ℘(A) durch

D = { a  ∈  A | a  ∉  f (a) }.

Dann ist D kein Element des Wertebereichs von f.

Beweis hierzu

Für alle a  ∈  A gilt nach Definition von D:

(+) a  ∈  D genau dann, wenn a  ∉  f (a).

Annahme, es gibt ein a*  ∈  A mit D = f (a*). Dann gilt nach (+) mit a = a*:

a*  ∈  D genau dann, wenn a*  ∉  D,

Widerspruch.

Nach dem Satz markieren die wiederholten Potenzmengenbildungen

ℕ, ℘(ℕ), ℘(℘(ℕ)), …, ℘ⁿ(ℕ), …

verschiedene Stufen des Unendlichen. Sie illustrieren auch die Bedeutung des axiomatischen Rahmens: Dieser Rahmen garantiert (oder genauer: postuliert), dass wir die sehr großen überabzählbaren Mengen ℘ⁿ(ℕ) für alle natürlichen Zahlen n ≥ 1 bilden können. Wir werden am Ende des Kapitels auf die Unendlichkeitsstufen dieser Folge noch einmal zurückkommen.

Der Beweis des Satzes zeigt die Idee der Diagonalisierung in ihrer vielleicht klarsten Form. Identifizieren wir Teilmengen von A mit 0-1-Folgen auf A, so definiert f : A → ℘(A) eine (abstrakte) 0-1-Matrix. Der Austausch von 0 und 1 auf der Diagonale liefert die Menge D. Anders formuliert: Jede quadratische 0-1-Matrix liefert durch Diagonalisierung eine 0-1-Folge, die keine Zeile (und keine Spalte) der Matrix ist. Das funktioniert auch im Unendlichen.

Der Satz von Cantor enthält die Überabzählbarkeit der reellen Zahlen als Spezialfall. Denn man kann, was keineswegs trivial ist, zeigen, dass es eine Bijektion zwischen ℝ und der Potenzmenge der natürlichen Zahlen gibt. Da nach dem Satz von Cantor keine Surjektion von ℕ nach ℘(ℕ) existiert, gibt es auch keine Surjektion von ℕ nach ℝ. Diese Argumentation benötigt keine Dezimaldarstellung reeller Zahlen.