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

besteht. Beides sind Meisterstücke, sie zusammenzufügen war ein Geniestreich. Müßte ich indessen entscheiden, welche der beiden Schlüsselideen die tiefschürfendere ist, so würde ich ohne Zögern die erste wählen, also die der Gödelisierung, denn diese Idee hängt mit all den Vorstellungen von dem zusammen, was Bedeutung und Bezüglichkeit in symbolmanipulierenden Systemen sind. Das ist eine Idee, die weit über die Grenzen der mathematischen Logik hinausführt, während Cantors Trick, so reich seine mathematischen Folgen sind, wenn überhaupt, wenig Beziehungen zu Dingen des wirklichen Lebens aufweist.
Die erste Idee: Beweispaare
    Schreiten wir also ohne weitere Umstände zu der Erklärung des Beweises selbst. In Kapitel IX haben wir bereits eine recht sorgfältige Darstellung davon gegeben, worum es sich bei Gödels Isomorphie handelt. Wir werden nun einen mathematischen Begriff beschreiben, der es uns gestattet, Aussagen wie „die Kette 0=0 ist ein S ATZ von TNT“in eine zahlentheoretische Aussage zu übersetzen. Dazu brauchen wir den Begriff der Beweispaare. Ein Beweispaar ist ein Paar von natürlichen Zahlen, die auf eine besondere Weise miteinander verbunden sind, also:
    Zwei natürliche Zahlen, m und n , bilden ein TNT-Beweispaar, dann und nur dann, wenn m die Gödel-Nummer einer TNT-Ableitung ist, deren unterste Zeile die Kette mit der Gödel-Nummer n ist.
    Einen entsprechenden Begriff gibt es im Hinblick auf das MIU-System, und es ist aus Gründen der Anschaulichkeit leichter, diesen Fall zuerst zu betrachten. Lassen wir also für den Augenblick die TNT-Beweispaare auf sich beruhen und betrachten wir MIU-Beweispaare. Ihre Definition läuft der obigen parallel:
    Zwei natürliche Zahlen, m und n, bilden ein MIU-Beweispaar, dann und nur dann, wenn m die Gödel-Nummer einer Ableitung des MIU-Systems ist, deren unterste Zeile die Kette mit der Gödel-Nummer n ist.
    Betrachten wir ein paar Beispiele von MIU-Beweispaaren. Setzen wir zuerst m = 3131131111301, n = 301. Diese Werte von m und n bilden in der Tat ein MIU-Beweispaar, da m die Gödel-Nummer der folgenden MIU-Ableitung ist:
MI
MII
MIIII
MUI
    deren letzte Zeile MUI mit der Gödel-Nummer 301 ist, und das gleich n. Im Gegensatz dazu setzen wir m = 31311311130, und n = 30. Warum bilden diese zwei Werte kein MIU-Beweispaar? Um die Antwort zu erhalten, schreiben wir die angebliche Ableitung, die m codiert:
MI
MII
MIII
MU
    In dieser angeblichen Ableitung ist ein ungültiger Schritt! Der von der zweiten zur dritten Zeile: von MII zu MIII . Es gibt im MIU-System keine Folgerungsregel, die einen solchen typographischen Schritt gestattet. Entsprechend, und das ist von außerordentlicher Wichtigkeit, gibt es keine arithmetische Folgerungsregel, die von 311 zu 3111 führt. Betrachtet unter dem Gesichtspunkt unserer Ausführungen in Kapitel IX ist das vielleicht eine triviale Beobachtung. Aber sie ist das Kernstück der Gödel-Isomorphie. Was wir in einem beliebigen formalen System tun, findet seine Entsprechung in arithmetischen Manipulationen.
    Auf jeden Fall bilden die Werte m = 31311311130, n = 30 mit Sicherheit kein MIU-Beweispaar. Diese Tatsache als solche bedeutet nicht, daß 30 keine MIU-Zahl ist. Es könnte einen anderen Wert für m geben, der mit 30 ein MIU-Beweispaar bildet. (In Wirklichkeit wissen wir aus früherem folgerichtigem Denken, daß MU kein MIU-S ATZ ist und daß deshalb überhaupt keine Zahl mit 30 ein MIU-Beweispaar bilden kann.)
    Und wie steht es nun mit TNT-Beweispaaren? Hier zwei parallele Beispiele — das eine einfach ein angebliches TNT-Beweispaar, das andere ein wirkliches TNT-Beweispaar. Können Sie feststellen, welches welches ist? (Hier tritt übrigens das „611"-Codon auf. Seine Aufgabe ist es, die Gödel-Nummern von aufeinanderfolgenden Zeilen in einer TNT-Ableitung zu trennen. In diesem Sinn dient „611“ als Trennungszeichen. Im MIU-System genügt die „3“ am Anfang aller Zeilen — es bedarf keiner gesonderten Interpunktion.)
1)
m = 626,262,636,223,123,262,111,666,611,223,123,666,111,666
n = 123,666,111,666
2)
m = 626,262,636,223,123,262,111,666,611,223,333,262,636,123,262,111,666
n = 223,333,262,636,123,262,111,666
    Es ist ganz einfach festzustellen, welches die richtige ist, indem man einfach wieder in die alte Notation übersetzt und nachprüft,
1)
ob die angebliche Ableitung, in m codiert, tatsächlich eine zulässige Ableitung ist;
2)
wenn ja, ob die letzte Zeile der Ableitung mit der Kette übereinstimmt, die