Gödel, Escher, Bach - ein Endloses Geflochtenes Band

r(1),
    ist d verschieden von r (2),
    ist d verschieden von r (3),
    ... usw.
    In anderen Worten: d steht nicht auf der Liste!
Was beweist das Diagonalargument?
    Nun kommt der entscheidende Unterschied zwischen Cantors Beweis und dem unseren — er liegt in der Frage, zu welcher Annahme wir zurückkehren wollen, um sie aufzuheben. In Cantors Argument war die auf nicht sehr sicheren Füßen stehende Annahme die, daß sich eine solche Tabelle herstellen lasse. Deshalb ist der Schluß, den die Konstruktion von d erlaubt, daß schließlich doch keine erschöpfende Tabelle von reellen Zahlen erstellt werden kann — was darauf hinausläuft, daß die Menge der ganzen Zahlen ganz einfach nicht groß genug ist, um die Menge der reellen Zahlen indizieren zu können. Andererseits wissen wir, daß das Adreßbuch von Blauen BlooP-Programmen niedergeschrieben werden kann — die Menge der ganzen Zahlen ist groß genug, um Blaue BlooP-Programme mit Indexzahlen zu versehen. Wir müssen noch einmal zurückgehen und einen weniger leicht aufrechtzuerhaltenden Gedanken, den wir verwendet haben, zurücknehmen. Und zwar ist es der, daß Blaudiag [ N ] durch ein Programm in BlooP berechenbar sei. Das ist ein subtiler Unterschied in der Anwendung der Diagonalmethode.

Abb. 73 . Georg Cantor.
    Das wird vielleicht klarer, wenn wir sie auf die angebliche „Liste Aller Großen Mathematiker“ anwenden — ein etwas konkreteres Beispiel. Die Diagonale selbst ist „Dboups“. Führen wir die gewünschte Diagonalsubtraktion durch, erhalten wir „Cantor“. Nun sind zwei Schlüsse möglich: wer unerschütterlich an die Vollständigkeit der Liste glaubt, muß schließen, daß Cantor kein großer Mathematiker ist, da sein Name von allen Namen aller großen Mathematiker verschieden ist. Wer aber unerschütterlich glaubt, daß Cantor ein großer Mathematiker ist, muß zum Schluß gelangen, daß die Liste aller großen Mathematiker unvollständig ist, denn Cantors Name figuriert nicht auf ihr. (Wehe denen, die unerschütterlich beides glauben!) Der erste Fall entspricht unserem Beweis, daß Blaudiag [ N ] nicht primitiv-rekursiv ist; der zweite entspricht Cantors Beweis, daß die Liste der reellen Zahlen unvollständig ist.
    Cantor verwendet in seinem Beweis eine Diagonale im wörtlichen Sinn. Andere „Diagonal“-Beweise fußen auf einem allgemeineren Begriff, der vom geometrischen Wortsinn abstrahiert. Das Wesentliche der Diagonalmethode liegt darin, daß man eine Ziffer auf zwei verschiedene Arten verwendet oder, wie man auch sagen könnte, eine ganze Zahl auf zwei verschiedenen Ebenen verwendet — was einen befähigt, eine Eintragung zu konstruieren, die außerhalb einer festgelegten Liste liegt. Die Zahl dient einmal als vertikaler Index und ein anderes Mal als horizontaler. In Cantors Konstruktion ist das sehr deutlich zu erkennen. Was die Funktion Blaudiag [ N ] betrifft, so verlangt sie, daß man eine ganze Zahl auf zwei verschiedenen Ebenen verwendet erstens als eine Blaues-Programm-Indexziffer und zweitens als Input-Parameter.
Die hinterhältige Wiederholbarkeit des Diagonalarguments
    Auf den ersten Blick scheint Cantors Argument nicht ganz überzeugend. Gibt es keine Möglichkeit, es zu umgehen? Vielleicht könnte man eine umfassendere Liste erhalten, wenn man die diagonal konstruierte Zahl d einbezöge. Bei näherer Prüfung wird man aber erkennen, daß es nichts hilft, die Zahl d dazuzunehmen, denn sobald man ihr einen bestimmten Ort in der Tabelle zuweist, läßt sich die Diagonalmethode auf die neue Tabelle anwenden, und eine neue, im Adreßbuch nicht vorhandene Zahl d' läßt sich konstruieren, die nicht in der neuen Tabelle steht. Wie oft man auch die Konstruktion einer Zahl vermittels der Diagonalmethode wiederholt und jene dann hinzufügt, um eine „vollständigere“ Tabelle zu erhalten, man hängt doch immer an dem nicht zu vermeidenden Haken von Cantors Methode. Man könnte sogar versuchen, eine Tabelle von reellen Zahlen aufzubauen, um Cantors Diagonalmethode zu überlisten, indem man den ganzen Kram und Krempel, so wie er ist, einschließlich seiner trügerischen Wiederholbarkeit, irgendwie berücksichtigen könnte. Es ist eine interessante Übung. Wenn Sie sie aber in Angriff nehmen, werden Sie sehen, daß Sie sich drehen und wenden können wie Sie wollen, um den Cantor-„Haken“ zu vermeiden — Sie werden doch immer an ihm hängen. Man könnte sagen, daß jede angebliche „Tabelle aller reellen Zahlen“ sich in der