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

Das 2. Cantorsche Diagonalverfahren

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], [math]a_{ij}\in\mathbb{N}[/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.

Eine Skizze des Beweises in "Diagonalform":

[math]x_1[/math]	0,5437...
[math]x_2[/math]	2,4536...
[math]x_3[/math]	1,1149...
[math]x_4[/math]	7,0075...
[math]...[/math]	...
[math]z[/math]	0,4454...

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:

Beweis:

Sei [math]X[/math] eine beliebige Menge und nehme an, [math]f: X\rightarrow\mathcal{P}(X)[/math] sei 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. [math]f[/math] 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 / Hilberts Hotel

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 werden wir den Übergang zum Überabzählbaren suchen. Dazu werden wir 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]

Ein Element dieser Mengen hat dann genau die Form (Sitzplatz, Bus, Fähre, Herkunftsland,...). 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, das einem Gast seine Zimmernummer zuordnen soll, divergiert (der Grenzwert der Partialprodukte ist unendlich). Somit kann auf die Weise, die für endlich viele Stufen funktioniert hat, den Gästen nicht ihre Zimmernummer zugeordnet werden. Im Folgenden werden wir sehen, dass es auch keine andere Methode geben kann.

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, identifizierbar mit der Binärdarstellung der reellen Zahlen zwischen 0 und 1, ist schon überabzählbar.

Diagonalargumente in der theoretischen Informatik / Halteproblem

In der theoretischen Informatik nutzt man Diagonalargumente häufiger in Beweisen. Ein typisches Beispiel ist das Halteproblem, wobei es um folgende Frage geht: gibt es einen Algorithmus [math]C(A′,I)[/math], der für alle Algorithmen [math]A′[/math] und alle möglichen Eingaben [math]I[/math] entscheiden kann, ob dieser Algorithmus [math]A′[/math] für die Eingabe [math]I[/math] hält, also zu einem Ergebnis kommt? Alan Turing zeigte anhand von Turingmaschinen, die unter bestimmten Annahmen Computern ähnlich sind, dass es solch einen Algorithmus [math]C[/math] nicht geben kann. Wir vereinfachen die Beweisidee im Folgenden, indem wir auf einige Begriffe verzichten und sie durch anschaulichere Begriffe wie "Algorithmus", der auf einem "Computer" ausgeführt wird, ersetzen.

Notation und Begriffe

Ein Algorithmus [math]A[/math] sei im folgenden eine codierte endliche Zeichenkette über [math]\{0,1\}[/math]. Der Operator [math]A(...)[/math] meint den Algorithmus, der für bestimmte endliche Eingaben auf einem Computer ausgeführt wird. Ein Algorithmus kann somit Operation und Eingabe zugleich sein.

Eine Eingabe ist eine endliche Zeichenkette [math]I[/math], gebildet über [math]\{0,1\}[/math].

Schreiben wir im Folgenden [math]undefined[/math] für die von einem Algorithmus berechnete Funktion zu einer Eingabe, dann bedeutet das, dass der Algorithmus für die Eingabe nicht hält — also zu keinem Ergebnis kommt. Dies könnte der Fall sein, wenn sich das Programm in einer Endlosschleife befindet.

Beispiel für einen Algorithmus

Ein Algorithmus [math]A[/math] sei durch folgenden Pseudocode, eine endliche Zeichenkette, gegeben

def A(int I): 
    if I==1: 
        return 1;
    else:
        while True: // Endlosschleife

[math]A[/math] berechnet die Funktion:

[math]A(I) = \begin{cases}1& I==1\\ undefined& \mathrm{sonst}\end{cases}[/math]

[math]A[/math] hält also nur, wenn der Algorithmus 1 als Eingabe erhält. Dann berechnet er 1. In jedem anderen Fall kommt er zu keinem Ergebnis, das der Algorithmus nie hält - wir schreiben [math]undefined[/math].

Wie kommt das Diagonalargument zum Einsatz?

Die Beweisidee orientiert sich im Wesentlichen an dem Wikipedia-Artikel zum Halteproblem.

Um die Frage, gibt es einen Algorithmus [math]C[/math] der für jeden Algorithmus [math]A'[/math] und jede Eingabe [math]I[/math] entscheidet, ob [math]A(I)[/math] hält, mit Nein zu beantworten, muss gezeigt werden, dass es keinen Algorithmus [math]D[/math] gibt, der immer [math]D(A',I)=1[/math] berechnet, wenn [math]A'[/math] nicht für [math]I[/math] hält. (Die Äquivalenz der Behauptungen zeigen wir hier nicht.)

Im Wesentlichen führt man einen Widerspruchsbeweis: man nimmt an, es gibt einen solchen Algorithmus [math]D[/math] mit den oben genannten Eigenschaften, der folgende Funktion berechnet:

[math]D(A', I) = \begin{cases}1&A'\mathrm{\ hält\ nicht\ für\ Eingabe\ } I\\ undefined& \mathrm{sonst}\end{cases}[/math]

Wir konstruieren uns nun eine Funktion mit dem Diagonalargument über die aufzählbaren Eingaben [math]I[/math] und Algorithmen [math]A'[/math]:

Wir zählen die Funktionswerte von D(A, I) auf: vertikal den Algorithmus und horizontal die endl. Zeichenkette, die einen Algorithmus codiert; U = undefined; Beispielwerte

A'/I	A_1	A_2	A_3	...	// Eingaben werden aufgezählt wie/als Algorithmen (endl. Zeichenketten)
A_1	1	U	U	...
A_2	U	U	U	...
A_3	U	1	1	...
...	...	...	...	...
f(A')	1	U	1	...	// Werte ergeben sich aus der Diagonale

[math]f(A') = \begin{cases}1& A' \mathrm{\ hält\ nicht\ für\ Eingabe\ } I=A'\\ undefined& \mathrm{sonst.}\end{cases}[/math]

Sei [math]B[/math] nun ein Algorithmus, der [math]f[/math] berechnet. Also immer hält und [math]1[/math] berechnet, wenn die Bedingung zutrifft. Wir zeigen nun, dass [math]D(B,B)[/math] weder [math]1[/math], noch [math]undefined[/math] sein kann — ein Widerspruch zur Existenz eines solchen Algorithmus.

Angenommen [math]D(B,B)=1[/math], dann hält [math]B[/math] nicht für die Eingabe [math]I:= B[/math], also ist [math]f(B)=1[/math] nach Definition. [math]B[/math] kann aber nur 1 berechnen, wenn [math]B[/math] hält. Ein Widerspruch.

Angenommen [math]D(B,B)=undefined[/math], dann hält [math]B[/math] für die Eingabe [math]I:= B[/math], also ist [math]f(B)=undefined[/math] per Definition. Dies ist aber ein Widerspruch, da der Algorithmus [math]B[/math] aber eben [math]f[/math] berechnet, also zu einem Ergebnis kommt, und damit nicht undefiniert sein kann.

Bemerkung zur Beweisskizze

Wir haben bestmöglich versucht Begriffe und Definitionen aus der theoretischen Informatik weg zulassen, um den Fokus auf das Diagonalargument zu richten:

Entscheidend ist, dass wir durch das Diagonalargument eine Funktion angegebenen konnten, die durch einen Algorithmus berechenbar sein muss, der aber mit entsprechender Eingabe nicht akzeptiert wird von [math]D[/math].

In dem Buch "Theoretische Informatik, Eine umfassende Einführung", von Lutz Priese und Katrin Erk, 4. Auflage gibt es noch weitere Probleme, die auf das Diagonalargument zurückgreifen.

Für ein anschauliches Video, siehe: https://www.youtube.com/watch?v=pSUDZ7tUGCY

Ausblick

Ein weiteres schönes Diagonalargument von Cantor ist das Diagonalfolgenargument .