2. Cantorsches Diagonalverfahren

Wir wollen im Folgenden mit Cantors 2. Diagonalverfahren zeigen, dass die reellen Zahlen überabzählbar sind und einige Folgerungen daraus beleuchten.

Beweis der Überabzählbarkeit der reellen Zahlen

Wir betrachten die positiven reellen Zahlen und nehmen an, diese seien abzählbar.

Dann können wir [math]\mathbb{R}^+ [/math] aufzählen als [math]\mathbb{R}^+ = \{x_1, x_2, x_3, ...\}[/math] mit [math]x_i=a_{i0},a_{i1}a_{i2}a_{i3} ...[/math].

Definiere jetzt [math]z[/math] als [math]z=0, b_1b_2b_3...[/math] mit [math]b_j=5[/math] für [math]a_{jj}\ne{5}[/math] und [math]b_j=4[/math] für [math]a_{jj}=5[/math].

[math]z[/math] ist also etwa von der Form [math]z=0,45445... \Rightarrow z\in \mathbb{R}^+[/math].

Jedoch unterscheidet sich [math]z[/math] nach Definition von jedem [math]x_i\in\mathbb{R}^+[/math] an der [math]i[/math]-ten Nachkommastelle. Damit ist z ungleich jedem [math]x_i[/math] aus [math]\mathbb{R}^+[/math] [math]\Rightarrow z\notin\mathbb{R}^+[/math].

Es liegt offensichtlich ein Widerspruch vor, unsere Annahme ist also falsch. Folglich ist [math]\mathbb{R}^+[/math], und dadurch sicherlich auch [math]\mathbb{R}[/math], überabzählbar.

Was lässt sich daraus Ableiten?

• Es existiert keine Bijektion von [math]\mathbb{N}[/math] nach [math]\mathbb{R}[/math].

• Ist [math]M[/math] eine Menge mit mindestens 2 Elementen, so ist [math]Abb(\mathbb{N},M)[/math] überabzählbar (Beweis wieder mit 2. Cantorschen Diagonalverfahren).

• Es existiert keine Surjektion einer Menge auf ihre Potenzmenge (Satz von Cantor), Beweis dazu:

Sei [math]X[/math] eine beliebige Menge und [math]f: X\rightarrow\mathcal{P}(X)[/math] surjektiv.

Definiere [math]B=\{x\in X: x\notin f(x)\}\in\mathcal{P}(X)[/math]

Da [math]f[/math] surjektiv ist, existiert ein [math]a\in X[/math] mit [math]f(a)=B[/math].

[math]\Rightarrow[/math] wenn [math]a\in B\Rightarrow a\notin f(a)=B[/math].

    wenn [math]a\notin B \Rightarrow a\in f(a)=B[/math].

Wir kommen zu einem Widerspruch, also muss die Annahme falsch sein. f kann also nicht surjektiv sein.

Die Potenzmenge einer Menge ist also stets mächtiger als die Menge selbst. Dies gilt intuitiverweise für endliche Mengen, der Satz von Cantor gilt aber für alle Mengen, also insbesondere auch für unendliche Mengen. Auch für die leere Menge gilt der Satz von Cantor, da [math]\mathcal P(\emptyset)=\{\emptyset \}[/math].

Von Abzählbarkeit zu Überabzählbarkeit

Das Resultat der Überabzählbarkeit der reellen Zahlen ist erst wirklich Wertzuschätzen, mit der Tatsache, dass die Rationalen Zahlen abzählbar sind. Siehe dazu den Artikel Hilberts Hotel. Im Folgenden werde ich den Übergang zum Überabzählbaren suchen. Dazu möchte ich die Idee von Hilberts Hotel erweitern. Diese ging dort bis hin zu unendlich Gästen aus unendlich vielen Bussen, was den (positiven) rationalen Zahlen entspricht. Nun könnte man sich überlegen, dass jeweils unendlich Busse von k Fähren kommen, oder von unendlich Fähren. Und jeweils unendlich dieser Fähren aus unendlich verschiedenen Ländern. Um den Überblick zu behalten, nummerieren wir die Sitzplätze in den Bussen, die Busse, die Fähren, die Herkunftsländer etc. Eine Person kann dann beschrieben werden durch ein Schema: (Sitzplatz, Bus, Fähre, Herkunftsland,...). Wegen unserer Nummerierung können wir nun modellieren: Eine Person entspricht gerade einem Element folgender Mengen

k Gäste	[math]\{1,...,k\}[/math]
unendlich Gäste	[math]\mathbb{N}[/math]
je unendlich Gäste von k Bussen	[math]\mathbb{N} \times \{1,...,k\}[/math]
je unendlich Gäste von je unendlich Bussen	[math]\mathbb{N} \times \mathbb{N} = \mathbb{N}^2[/math]
je unendlich Gäste von je unendlich Bussen von k Fähren	[math]\mathbb{N}^2 \times \{1,...,k\}[/math]
je unendlich Gäste von je unendlich Bussen von unendlich Fähren	[math]\mathbb{N}^3[/math]
[math]\cdot\cdot\cdot[/math]	[math]\cdot\cdot\cdot[/math]

Machen Sie sich klar, dass ein Element dieser Mengen dann die Form (Sitzplatz, Bus, Fähre, Herkunftsland,...) hat. Anstatt von Sitzplätzen, Bussen, Fähren und Herkunftsländern sprechen wir nun von Stufen 1, 2, 3, ... . Für endlich viele Stufen kann der Portier immer noch die Schlüssel von Hilberts Hotel der Reihe nach austeilen, sodass jeder Gast nur endlich lannge warten muss. Diese Mengen sind abzählbar. Das können wir uns folgendermaßen schnell klarmachen:

Wir ordnen jeder Person der Form [math](n_1,n_2,n_3,...,n_k)[/math] die Zimmernummer $$2^{n_1}\cdot3^{n_2}\cdot5^{n_3}\cdot \cdot \cdot p_k^{n_k}$$ zu, wobei [math]p_k[/math] die k-te Primzahl ist. Die Zimmerschlüssel werden von der kleinsten beginnend ausgeteilt. Da die Primzahlzerlegung einer Zimmernummer eindeutig ist, gibt es kein Zimmer das doppelt belegt wird. Da es unendlich viele Primzahlen gibt, ist die Menge [math]\mathbb{N}^k[/math] somit für beliebiges [math]k \in \mathbb{N}[/math] abzählbar.

Doch was ist, wenn es unendlich Stufen gibt?

Frage: Warum funktioniert das Primzahlargument nicht mehr?

Antwort

Das Produkt divergiert.

Hier können wir ein Werkzeug verwenden, welches wir oben bei der Überabzählbarkeit der reellen Zahlen schon gesehen haben, Cantors 2. Diagonalargument. Nehmen wir an, wir hätten eine Abzählung gefunden, sodass jeder Gast nach endlich vielen Vorgängern seinen Schlüssel erhält:

Zimmernummer	Gast (a,b,c...)
1	[math](\boldsymbol{Sitzplatz_a}, Bus_a, F\ddot{a}hre_a, Herkunftsland_a, ...[/math]
2	[math](Sitzplatz_b, \boldsymbol{Bus_b}, F\ddot{a}hre_b, Herkunftsland_b, ...[/math]
3	[math](Sitzplatz_c, Bus_c, \boldsymbol{F\ddot{a}hre_c}, Herkunftsland_c, ...[/math]
4	[math](Sitzplatz_d, Bus_d, F\ddot{a}hre_d, \boldsymbol{Herkunftsland_d}, ...[/math]
[math]\vdots[/math]	[math]\vdots[/math]

Egal welche Abzählung wir wählen, wir finden immer folgenden Gast, der kein Zimmer bekommen hat: [math](Sitzplatz_a + 1, Bus_b + 1, F\ddot{a}hre_c + 1, Herkunftsland_d + 1, ...)[/math], denn für jede Zimmernummer ist der Zimmernummer-te Diagonaleintrag verschieden von diesem.

Für unendlich Stufen gilt somit die Überabzählbarkeit.

Unendlich Stufen entsprechen der Menge aller Folgen natürlicher Zahlen. Auch die Menge aller binären Folgen ist schon überabzählbar - Binärdarstellung der reellen Zahlen zwischen 0 und 1.