Im Jahr 1931 gelang dem österreichischen Logiker Kurt Gödel eine der wohl erstaunlichsten intellektuellen Leistungen der Geschichte.
Die Mathematiker jener Zeit suchten nach einem soliden Fundament für die Mathematik: eine Menge grundlegender mathematischer Fakten oder Axiome, die sowohl konsistent – niemals zu Widersprüchen führend – als auch vollständig waren und als Bausteine aller mathematischen Wahrheiten dienten.
Aber Gödels schockierende Unvollständigkeitssätze, die er im Alter von nur 25 Jahren veröffentlichte, zerstörten diesen Traum. Er bewies, dass jeder Satz von Axiomen, den man als mögliche Grundlage für die Mathematik aufstellen könnte, unweigerlich unvollständig sein wird; es wird immer wahre Fakten über Zahlen geben, die nicht durch diese Axiome bewiesen werden können. Er zeigte auch, dass kein Kandidatensatz von Axiomen jemals seine eigene Konsistenz beweisen kann.
Seine Unvollständigkeitstheoreme bedeuteten, dass es keine mathematische Theorie von allem geben kann, keine Vereinigung dessen, was beweisbar ist und was wahr ist. Was Mathematiker beweisen können, hängt von ihren Ausgangsannahmen ab, nicht von einer fundamentalen Grundwahrheit, aus der alle Antworten entspringen.
In den 89 Jahren seit Gödels Entdeckung sind Mathematiker über genau die Art von unbeantwortbaren Fragen gestolpert, die seine Theoreme voraussagten. So hat Gödel selbst dazu beigetragen, dass die Kontinuumshypothese, die die Größen der Unendlichkeit betrifft, unentscheidbar ist, ebenso wie das Halteproblem, das die Frage stellt, ob ein Computerprogramm, das mit einer zufälligen Eingabe gefüttert wird, ewig läuft oder irgendwann stehen bleibt. Unentscheidbare Fragen sind sogar in der Physik aufgetaucht, was darauf hindeutet, dass die Gödelsche Unvollständigkeit nicht nur die Mathematik betrifft, sondern – auf eine unverstandene Weise – auch die Realität.
Hier ist eine vereinfachte, informelle Übersicht darüber, wie Gödel seine Theoreme bewiesen hat.
Gödelsche Nummerierung
Gödels Hauptmanöver war es, Aussagen über ein System von Axiomen auf Aussagen innerhalb des Systems abzubilden – das heißt, auf Aussagen über Zahlen. Diese Abbildung erlaubt es einem System von Axiomen, schlüssig über sich selbst zu sprechen.
Der erste Schritt in diesem Prozess besteht darin, jede mögliche mathematische Aussage oder Reihe von Aussagen auf eine eindeutige Zahl abzubilden, die Gödel-Zahl genannt wird.
Die leicht modifizierte Version von Gödels Schema, die von Ernest Nagel und James Newman in ihrem Buch „Gödel’s Proof“ von 1958 vorgestellt wurde, beginnt mit 12 elementaren Symbolen, die als Vokabular für den Ausdruck eines Satzes von Grundaxiomen dienen. Zum Beispiel kann die Aussage, dass etwas existiert, durch das Symbol ∃ ausgedrückt werden, während die Addition durch + ausgedrückt wird. Wichtig ist, dass das Symbol s, das für „Nachfolger von“ steht, eine Möglichkeit bietet, Zahlen zu spezifizieren; ss0 bezieht sich zum Beispiel auf 2.
Diesen zwölf Symbolen werden dann die Gödel-Zahlen 1 bis 12 zugeordnet.
| Konstantenzeichen | Gödel-Nummer | Usere Bedeutung |
| ~ | 1 | nicht |
| ∨ | 2 | oder |
| ⊃ | 3 | wenn…dann… |
| ∃ | 4 | Es gibt ist ein… |
| = | 5 | gleich | 0 | 6 | Null |
| s | 7 | der Nachfolger von |
| ( | 8 | Satzzeichen |
| ) | 9 | Satzzeichen |
| , | 10 | Satzzeichen |
| + | 11 | plus |
| × | 12 | Zeiten |
Nächste, Buchstaben, die Variablen darstellen, beginnend mit x, y und z, auf Primzahlen größer als 12 abbilden (also 13, 17, 19, …).
Dann erhält jede Kombination dieser Symbole und Variablen – das heißt, jede arithmetische Formel oder Folge von Formeln, die konstruiert werden kann – ihre eigene Gödel-Zahl.
Betrachten wir zum Beispiel 0 = 0. Die drei Symbole der Formel entsprechen den Gödel-Zahlen 6, 5 und 6. Gödel muss diese Drei-Zahlen-Folge in eine einzige, eindeutige Zahl umwandeln – eine Zahl, die keine andere Folge von Symbolen erzeugen kann. Dazu nimmt er die ersten drei Primzahlen (2, 3 und 5), erhöht jede auf die Gödel-Zahl des Symbols an der gleichen Position in der Folge und multipliziert sie miteinander. So wird aus 0 = 0 26 × 35 × 56, also 243.000.000.
Die Abbildung funktioniert, weil keine zwei Formeln jemals mit der gleichen Gödel-Zahl enden werden. Gödel-Zahlen sind ganze Zahlen, und ganze Zahlen lassen sich nur auf eine einzige Weise in Primzahlen faktorisieren. So ist die einzige Primfaktorzerlegung von 243.000.000 26 × 35 × 56, was bedeutet, dass es nur einen möglichen Weg gibt, die Gödel-Zahl zu entschlüsseln: die Formel 0 = 0.
Gödel ging dann noch einen Schritt weiter. Ein mathematischer Beweis besteht aus einer Folge von Formeln. Also gab Gödel jeder Folge von Formeln auch eine eindeutige Gödel-Zahl. In diesem Fall beginnt er mit der Liste der Primzahlen wie zuvor – 2, 3, 5 und so weiter. Dann erhöht er jede Primzahl auf die Gödel-Zahl der Formel an der gleichen Position in der Folge (2243.000.000 × …, wenn z. B. 0 = 0 an erster Stelle steht) und multipliziert alles miteinander.
Metamathematik arithmetisieren
Der eigentliche Segen ist, dass sich auch Aussagen über arithmetische Formeln, sogenannte metamathematische Aussagen, selbst in Formeln mit eigenen Gödel-Zahlen übersetzen lassen.
Betrachten wir zunächst die Formel ~(0 = 0), also „Null ist nicht gleich Null.“ Diese Formel ist eindeutig falsch. Trotzdem hat sie eine Gödel-Zahl: 2 hoch 1 (die Gödel-Zahl des Symbols ~), multipliziert mit 3 hoch 8 (die Gödel-Zahl des Symbols „offene Klammer“), und so weiter, was 2¹ × 38 × 56 × 75 × 116 × 139 ergibt.
Da wir Gödel-Zahlen für alle Formeln erzeugen können, auch für falsche, können wir sinnvoll über diese Formeln sprechen, indem wir über ihre Gödel-Zahlen sprechen.
Betrachten Sie die Aussage: „Das erste Symbol der Formel ~(0 = 0) ist eine Tilde.“ Diese (wahre) metamathematische Aussage über ~(0 = 0) übersetzt sich in eine Aussage über die Gödel-Zahl der Formel – nämlich, dass ihr erster Exponent 1 ist, die Gödel-Zahl für eine Tilde. Mit anderen Worten: Unsere Aussage besagt, dass 2¹ × 38 × 56 × 75 × 116 × 139 nur einen einzigen Faktor von 2 hat. Hätte ~(0 = 0) mit einem anderen Symbol als einer Tilde begonnen, hätte die Gödel-Zahl mindestens zwei Faktoren von 2. Genauer gesagt, ist 2 ein Faktor von 2¹ × 38 × 56 × 75 × 116 × 139, aber 22 ist kein Faktor.
Wir können den letzten Satz in eine präzise arithmetische Formel umwandeln, die wir mit elementaren Symbolen aufschreiben* können. Diese Formel hat natürlich eine Gödel-Zahl, die wir berechnen können, indem wir ihre Symbole auf Potenzen von Primzahlen abbilden.
Dieses Beispiel, so schreiben Nagel und Newman, „veranschaulicht eine sehr allgemeine und tiefe Einsicht, die im Herzen von Gödels Entdeckung liegt: über die typographischen Eigenschaften langer Ketten von Symbolen kann auf indirekte, aber vollkommen genaue Weise gesprochen werden, indem man stattdessen über die Eigenschaften von Primfaktorzerlegungen großer ganzer Zahlen spricht.“
Die Umwandlung in Symbole ist auch für die metamathematische Aussage möglich: „Es gibt irgendeine Folge von Formeln mit der Gödel-Zahl x, die die Formel mit der Gödel-Zahl k beweist“ – oder kurz gesagt: „Die Formel mit der Gödel-Zahl k kann bewiesen werden.“ Die Fähigkeit, diese Art von Aussage zu „arithmetisieren“, legte den Grundstein für den Coup.
G selbst
Gödels zusätzliche Einsicht war, dass er die eigene Gödel-Zahl einer Formel in der Formel selbst ersetzen konnte, was zu unendlichem Ärger führte.
Um zu sehen, wie die Substitution funktioniert, betrachten Sie die Formel (∃x)(x = sy). (Sie lautet: „Es gibt eine Variable x, die der Nachfolger von y ist“, oder, kurz gesagt, „y hat einen Nachfolger.“) Wie alle Formeln hat sie eine Gödel-Zahl – eine große ganze Zahl, die wir einfach m nennen.
Lassen Sie uns nun m anstelle des Symbols y in die Formel einführen. Dies bildet eine neue Formel, (∃x)(x = sm), was bedeutet: „m hat einen Nachfolger“. Wie sollen wir die Gödel-Zahl dieser Formel nennen? Es gibt drei Informationen zu vermitteln: Wir haben mit der Formel begonnen, die die Gödel-Zahl m hat. In ihr haben wir m durch das Symbol y ersetzt. Und nach dem zuvor eingeführten Abbildungsschema hat das Symbol y die Gödel-Zahl 17. Nennen wir also die Gödel-Zahl der neuen Formel sub(m, m, 17).
Die Substitution bildet den Kern von Gödels Beweis.
Er überlegte sich eine metamathematische Aussage nach dem Muster: „Die Formel mit der Gödel-Zahl sub(y, y, 17) kann nicht bewiesen werden.“ In Anlehnung an die Notation, die wir gerade gelernt haben, ist die Formel mit der Gödel-Zahl sub(y, y, 17) diejenige, die man erhält, wenn man die Formel mit der Gödel-Zahl y (eine unbekannte Variable) nimmt und diese Variable y überall dort ersetzt, wo es ein Symbol gibt, dessen Gödel-Zahl 17 ist (also überall dort, wo es ein y gibt).
Die Sache wird jetzt etwas trippy, aber nichtsdestotrotz ist unsere metamathematische Aussage – „Die Formel mit der Gödel-Zahl sub(y, y, 17) kann nicht bewiesen werden“ – sicher in eine Formel mit einer eindeutigen Gödel-Zahl zu übersetzen. Nennen wir sie n.
Nun, eine letzte Runde der Substitution: Gödel erstellt eine neue Formel, indem er die Zahl n überall dort einsetzt, wo in der bisherigen Formel ein y steht. Seine neue Formel lautet: „Die Formel mit der Gödelschen Zahl sub(n, n, 17) kann nicht bewiesen werden.“ Nennen wir diese neue Formel G.
Natürlich hat G eine Gödel-Zahl. Wie hoch ist sie? Und siehe da, sie muss sub(n, n, 17) sein. Per Definition ist sub(n, n, 17) die Gödel-Zahl der Formel, die sich ergibt, wenn man die Formel mit der Gödel-Zahl n nimmt und n überall dort ersetzt, wo es ein Symbol mit der Gödel-Zahl 17 gibt. Und G ist genau diese Formel! Wegen der Eindeutigkeit der Primfaktorzerlegung sehen wir nun, dass die Formel, von der G spricht, keine andere ist als G selbst.
G behauptet von sich selbst, dass es nicht bewiesen werden kann.
Aber kann G bewiesen werden? Wenn ja, würde das bedeuten, dass es eine Folge von Formeln gibt, die die Formel mit der Gödel-Zahl sub(n, n, 17) beweist. Aber das ist das Gegenteil von G, das besagt, dass es keinen solchen Beweis gibt. Gegensätzliche Aussagen, G und ~G, können in einem konsistenten axiomatischen System nicht beide wahr sein. Also muss die Wahrheit von G unentscheidbar sein.
Aber obwohl G unentscheidbar ist, ist es eindeutig wahr. G sagt: „Die Formel mit der Gödel-Zahl sub(n, n, 17) kann nicht bewiesen werden“, und genau das ist der Fall! Da G wahr, aber innerhalb des axiomatischen Systems, das zu seiner Konstruktion verwendet wurde, unentscheidbar ist, ist dieses System unvollständig.
Man könnte meinen, man könne einfach irgendein zusätzliches Axiom aufstellen, es zum Beweis von G verwenden und das Paradoxon auflösen. Aber das kann man nicht. Gödel zeigte, dass das erweiterte axiomatische System die Konstruktion einer neuen, wahren Formel Gʹ erlaubt (nach einem ähnlichen Bauplan wie zuvor), die innerhalb des neuen, erweiterten Systems nicht bewiesen werden kann. Wenn man ein vollständiges mathematisches System anstrebt, kann man nie seinen eigenen Schwanz fangen.
Kein Beweis der Konsistenz
Wir haben gelernt, dass eine Menge von Axiomen, wenn sie konsistent ist, unvollständig ist. Das ist der erste Gödelsche Unvollständigkeitssatz. Der zweite – dass keine Menge von Axiomen ihre eigene Konsistenz beweisen kann – folgt leicht.
Was würde es bedeuten, wenn eine Menge von Axiomen beweisen könnte, dass sie niemals einen Widerspruch ergibt? Es würde bedeuten, dass es eine Folge von Formeln gibt, die aus diesen Axiomen gebildet wird und die die Formel beweist, die metamathematisch bedeutet: „Dieser Satz von Axiomen ist konsistent.“ Nach dem ersten Satz wäre diese Axiomenmenge dann notwendigerweise unvollständig.
Aber „Die Axiomenmenge ist unvollständig“ ist dasselbe wie die Aussage: „Es gibt eine wahre Formel, die nicht bewiesen werden kann.“ Diese Aussage ist äquivalent zu unserer Formel G. Und wir wissen, dass die Axiome G nicht beweisen können.
So hat Gödel einen Beweis durch Widerspruch geschaffen: Wenn eine Menge von Axiomen ihre eigene Konsistenz beweisen könnte, dann wären wir in der Lage, G zu beweisen. Aber wir können es nicht. Daher kann kein Satz von Axiomen seine eigene Konsistenz beweisen.
Gödels Beweis hat die Suche nach einem konsistenten, vollständigen mathematischen System beendet. Die Bedeutung der Unvollständigkeit „ist nicht vollständig ergründet worden“, schrieben Nagel und Newman 1958. Das gilt auch heute noch.
*Für Neugierige: Die Aussage lautet: „Es existiert irgendeine ganze Zahl x, so dass x multipliziert mit 2 gleich 2¹ × 38 × 56 × 75 × 116 × 139 ist, und es existiert keine ganze Zahl x, so dass x multipliziert mit 4 gleich 2¹ × 38 × 56 × 75 × 116 × 139 ist.“ Die entsprechende Formel lautet:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
wobei sss … sss0 für 2¹ × 38 × 56 × 75 × 116 × 139 Kopien des Nachfolgesymbols s steht. Das Symbol ⋅ bedeutet „und“ und ist eine Kurzform für einen längeren Ausdruck im Grundwortschatz: p ⋅ q steht für ~(~p ∨ ~q).
Dieser Artikel wurde auf Wired.com nachgedruckt.