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

die Interpretation seiner Verneinung ~G falsch. Und wir wissen, daß in TNT keine falschen Aussagen ableitbar sind. So kann also weder G noch seine Verneinung ~G ein S ATZ von TNT sein. Wir haben ein „Loch“ in unserem System gefunden — eine unentscheidbare Behauptung. Das hat verschiedene Weiterungen. Nachstehend eine kuriose Tatsache, die aus der Unentscheidbarkeit von G folgt: obgleich weder G noch ~G S ÄTZE sind, ist die Formel ein S ATZ , da die Regeln der Aussagenlogik bestimmen, daß alle wohlgeformten Formeln der Form < P ∨~ P > S ÄTZE sind.
    Dies ist ein einfaches Beispiel dafür, daß eine innerhalb eines Systems gemachte Behauptung und eine Behauptung über das System miteinander in Konflikt zu liegenscheinen. Deshalb fragt man sich, ob sich das System tatsächlich korrekt widerspiegelt. Entspricht die „reflektierte Metamathematik“, die in TNT vorhanden ist, einigermaßen der Metamathematik, die wir treiben? Das war eine der Fragen, die Gödel beschäftigte, als er seine Ableitung schrieb. Insbesondere interessierte ihn die Frage, ob es möglich sei, in der „reflektierten Metamathematik“ die Widerspruchsfreiheit von TNT zu beweisen. Man erinnere sich daran, daß damals das Problem, Widerspruchsfreiheit zu beweisen, ein schwerwiegendes philosophisches Dilemma war. Gödel fand eine einfache Methode, die Aussage „TNT ist widerspruchsfrei“ in einer TNT-Formel auszudrücken, und dann zeigte er, daß diese Formel (und alle anderen, die die gleichen Gedanken ausdrücken) nur unter einer Bedingung S ÄTZE von TNT sind, nämlich wenn TNT widerspruchsvoll ist. Dieses aberwitzige Ergebnis war ein schwerer Schlag für Optimisten, die erwartet hatten, daß sich ein strenger Beweis für die Widerspruchsfreiheit der Mathematik finden lasse.
    Wie drückt man die Aussage „TNT ist widerspruchsfrei“ innerhalb von TNT aus? Die Antwort beruht auf einer einfachen Tatsache, nämlich daß Widerspruchsfreiheit bedeutet, daß x und ~x, die sich gegenseitig verneinen, beides S ÄTZE sind. Wenn aber sowohl x als auch ~x S ÄTZE sind, dann sind nach der Aussagenlogik alle wohlgeformten Formeln S ÄTZE . Um zu zeigen, daß TNT widerspruchsfrei ist, würde es genügen, eine einzige Formel von TNT vorzulegen, von der sich beweisen ließe, daß sie ein Nicht-S ATZ ist. Deshalb ist eine Möglichkeit, „TNT ist widerspruchsfrei“ auszudrücken, wenn man sagt: „Die Formel ~ 0 = 0 ist kein S ATZ von TNT.“ Das haben wir ein paar Seiten zuvor bereits als eine Übung aufgeführt. Die Übersetzung lautet:
∃a : TNT - BEWEISPAAR { a , SSSSS ..... SSSSS0 / a '}
∃a : TNT - BEWEISPAAR {a,
∃a : TNT - BEWEISPAAR {a, S 223 666 111 666 S
    Mit umständlicher, aber einigermaßen einfacher Argumentation läßt sich zeigen, daß, solange TNT widerspruchsfrei ist, dieser Schwur der Widerspruchsfreiheit kein S ATZ in TNT ist. So sind also die „introspektiven“ Fähigkeiten von TNT groß, wenn es sich darum handelt, Dinge auszudrücken, aber ziemlich schwach, wenn es um Beweise geht. Das ist ein recht provokantes Ergebnis, wenn man es metaphorisch auf das Problem der menschlichen Selbsterkenntnis anwendet.
TNT ist ω-unvollständig
    Welcher Art von Unvollständigkeit „erfreut“ sich TNT nun? Wir werden sehen, daß die Unvollständigkeit von TNT der „Omega“-Spielart angehört, wie in Kapitel VIII definiert. Das bedeutet, daß es eine unendliche, pyramidenförmig angeordnete Familie von Ketten gibt, die alle S ÄTZE sind, aber deren zugehörige „zusammenfassende“ Kette ein Nicht-S ATZ ist. Diese Kette läßt sich leicht angeben:
∀a :~ ∃a ':< TNT-BEWEISPAAR { a , a '} ∧ ARITHMOQUINE { SSS u S
∀a :~ ∃a ':< TNT-BEWEISPAAR { a , a '} ∧ ARITHMOQUINE {
∀a :~ ∃a ':< TNT-BEWEISPAAR { a , a '} ∧ ARITHMOQUINE { SSS ... SSS0 / a '', a '}
    Um zu verstehen, warum diese Kette ein Nicht-S ATZ ist, beachte man, daß sie G selbst außerordentlich ähnlich ist. Tatsächlich läßt sich G in einem Schritt, nämlich nach der TNT-Austauschregel, erzeugen. Wenn sie also ein S ATZ wäre, dann wäre auch G einer. Da aber G kein S ATZ ist, kann auch dieser keiner sein.
    Wir wollen nun zeigen, daß alle Ketten in der dazugehörigen pyramidenförmigen Familie S ÄTZE sind. Wir können sie leicht genug niederschreiben:
~ ∃a ':< TNT-BEWEISPAAR { 0 / a , a '} ∧ ARITHMOQUINE { SSS u S
~ ∃a ':< TNT-BEWEISPAAR { 0 / a , a '} ∧ ARITHMOQUINE {
~ ∃a ':< TNT-BEWEISPAAR { 0 / a , a '} ∧ ARITHMOQUINE { SSS ...