2. Cantorsches Diagonalverfahren

Lorem Ipsum

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](Sitzplatz_a, Bus_a, Fähre_a, Herkunftsland_a, ...[/math]
2	[math](Sitzplatz_b, Bus_b, Fähre_b, Herkunftsland_b, ...[/math]
3	[math](Sitzplatz_c, Bus_c, Fähre_c, Herkunftsland_c, ...[/math]
4	[math](Sitzplatz_d, Bus_d, Fähre_d, 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ähre_c + 1, Herkunftsland_d + 1, ...)[/math]. 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.