Wie Gödels Beweis funktioniert

Seine Unvollständigkeitssätze besiegten die Suche nach einer mathematischen Theorie von allem. Fast hundert Jahre später versuchen wir immer noch, die Konsequenzen zu verstehen.

1931 machte der österreichische Logiker Kurt Gödel einen der wohl erstaunlichsten intellektuellen Tricks der Geschichte.



Die Mathematiker dieser Zeit suchten nach den unerschütterlichen Grundlagen der Mathematik: einer Reihe grundlegender Fakten, Axiome, die konsistent und vollständig sind und die Rolle der Bausteine ​​aller mathematischen Wahrheiten spielen. Gödels



schockierende Unvollständigkeitssätze, von ihm erst im Alter von 25 Jahren veröffentlicht, zerschmetterte diesen Traum. Er hat bewiesen, dass alle Axiome, die Sie als Grundlage der Mathematik vorschlagen können, unweigerlich unvollständig sein werden. Es wird immer wahre Aussagen über Zahlen geben, die mit diesen Axiomen nicht bewiesen werden können. Er zeigte auch, dass kein Satz von Axiomen verwendet werden kann, um ihre eigene Konsistenz zu beweisen.



Seine Unvollständigkeitssätze bedeuten, dass es nicht für alles eine mathematische Theorie geben kann und es unmöglich ist, die Menge der beweisbaren Aussagen mit der Menge der wahren Aussagen zu kombinieren. Was Mathematiker beweisen können, hängt von anfänglichen Annahmen ab, nicht von einer fundamentalen Wahrheit, aus der alle Antworten stammen.



In den 89 Jahren seit Gödels Entdeckung sind Mathematiker auf ähnliche unbeantwortete Fragen gestoßen, deren Existenz seine Theoreme vorausgesagt haben. Zum Beispiel Gödel selbst dazu beigetragen , festzustellen , dass die Kontinuumshypothese , die über Mächtigkeiten von Unendlichkeiten unentscheidbar ist - genau wie das Anhalten Problem, in dem festgestellt werden muss, ob die Ausführung eines Computerprogramms jemals mit bestimmten Eingabedaten beendet wird oder für immer ausgeführt wird. Selbst in der Physik stellten sich unlösbare Fragen , was darauf hindeutet, dass Gödels Unvollständigkeit nicht nur die Mathematik, sondern in einem (nicht ganz klaren) Sinne die Realität betrifft.



Was folgt, ist eine kurze, vereinfachte und informelle Zusammenfassung, wie Gödel seine Theoreme bewiesen hat.

Gödel-Nummerierung

Gödels Hauptschritt war der Vergleich von Aussagen über das Axiomensystem mit Aussagen innerhalb dieses Systems - mit Aussagen über Zahlen. Diese Gegenüberstellung ermöglicht es dem Axiomensystem, ruhig über sich selbst zu argumentieren.



Der erste Schritt besteht darin, jede mögliche mathematische Aussage oder Folge von Aussagen mit einer eindeutigen Nummer abzugleichen, die als Gödel-Nummer bezeichnet wird .



Eine leicht überarbeitete Version von Gödels Nummerierung, wie sie in dem 1958 erschienenen Buch Gödels Proof von Ernest Nagel und James Newman vorgestellt wurdebeginnt mit 12 elementaren Symbolen, die als Wörterbuch zum Ausdrücken einer Reihe grundlegender Axiome dienen. Zum Beispiel kann eine Aussage über die Existenz von etwas durch das Symbol ∃ und die Addition durch das Symbol + ausgedrückt werden. Das s, das für "nächstes Element" steht, ermöglicht die Bezeichnung von Zahlen: ss0 steht beispielsweise für zwei.



Diesen zwölf Zeichen werden dann die Gödel-Nummern 1 bis 12 zugewiesen.







Dann werden Buchstaben, die Variablen bezeichnen, beginnend mit x, y und z, mit Primzahlen größer als 12 (13, 17, 19, ..) abgeglichen.



Dann erhält jede der Kombinationen dieser Symbole und Variablen - dh jede arithmetische Formel oder Folge von Formeln, die gebildet werden können - ihre eigene Gödel-Nummer.



Stellen Sie sich zum Beispiel die Aussage 0 = 0 vor. Die drei Symbole entsprechen den Gödel-Zahlen 6, 5 und 6. Gödel muss diese Folge von drei Zahlen durch eine eindeutige ersetzen - eine Zahl, die keine andere Folge von Symbolen erzeugt. Dazu nimmt er die ersten drei Primzahlen (2, 3 und 5), erhöht jede auf die Potenz, die der entsprechenden Zahl in der Sequenz entspricht, und multipliziert sie. Aus 0 = 0 wird also 2 ⁶ × 3 ⁵ × 5⁶ oder 243.000.000.



Dieses Markup funktioniert, weil keine zwei Formeln dieselbe Gödel-Nummer ergeben. Gödel-Zahlen sind ganze Zahlen, und Zahlen können auf einzigartige Weise in Primfaktoren zerlegt werden. Daher ist der einzige Weg, 243.000.000 in Faktoren zu faktorisieren, 2 ⁶ × 3 ⁵ × 5 ⁶ , dh es gibt nur einen Weg, diese Gödel-Zahl zu entschlüsseln: durch Schreiben der Formel 0 = 0.



Dann ging Gödel noch weiter. Ein mathematischer Beweis besteht aus einer Folge von Formeln. Daher hat Gödel jeder Folge von Formeln eine eigene Gödel-Nummer zugewiesen. In diesem Fall beginnt er auch mit einer Folge von Primzahlen - 2, 3, 5 usw. Dann erhöht er jeden von ihnen auf die Potenz, die der Gödel-Zahl für die Formel an derselben Ordnungsposition in der Sequenz entspricht (z. B. ^{2.243.000.000} , wenn die Formel 0 = 0 an erster Stelle steht) und multipliziert alles miteinander.

Arithmetische Mathematik

Es ist bemerkenswert, dass sogar Aussagen über arithmetische Formeln, die sogenannten. metamathematische Aussagen können in Formeln übersetzt und mit eigenen Gödel-Nummern versehen werden.



Betrachten Sie zuerst die Formel ~ (0 = 0), was bedeutet, dass „Null nicht Null ist“. Es ist eindeutig falsch. Es hat jedoch eine Gödel-Zahl: 2 hoch 1 (Gödel-Zahl für das ~ -Zeichen), multipliziert mit 3 hoch 8 (Gödel-Zahl für das linke Klammerzeichen) usw., was 2 ¹ × ergibt 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ .



Da wir Gödel-Zahlen für alle Formeln generieren können, auch für falsche, können wir sie mit ihren Gödel-Zahlen sinnvoll begründen.



Betrachten Sie die Aussage „Das erste Zeichen der Formel ~ (0 = 0) ist eine Tilde“. Diese wahre metamathematische Aussage über ~ (0 = 0) wird zu einer Aussage über die Gödel-Zahl einer bestimmten Formel - nämlich dass ihr erster Grad 1 ist, dh die Gödel-Zahl für die Tilde. Mit anderen Worten, unsere Aussage besagt, dass es in 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ⁹ nur einen Faktor "2" gibt. Wenn ~ (0 = 0) mit einem anderen Zeichen als einer Tilde beginnen würde, würde es mindestens zwei Faktoren in seiner -Zahl geben. Genauer gesagt ist 2 ein Faktor von 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵× 11 ⁶ × 13 ⁹ , 2 ² jedoch nicht.



Wir können den letzten Satz in eine exakte mathematische Formel umwandeln und ihn mit elementaren Symbolen aufschreiben. Diese Formel hat natürlich eine eigene Gödel-Zahl, die wir berechnen können, indem wir ihre Symbole mit Potenzen von Primzahlen abgleichen.



Wenn Sie interessiert sind, stellt sich die Formulierung folgendermaßen heraus: Es gibt eine ganze Zahl x, so dass x, multipliziert mit 2, gleich 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × 11 ⁶ × 13 ^{9 ist} , aber es gibt keine solche ganze Zahl x, die es ist multipliziert mit 4 ergab 2 ¹ × 3 ⁸ × 5 ⁶× 7 ⁵ × 11 ⁶ × 13 ⁹ . Die entsprechende Formel sieht folgendermaßen aus:



(∃x) (x × ss0 = sss… sss0) ⋅ ~ (∃x) (x × ssss0 = sss… sss0)



Wobei sss… sss0 2 ¹ × 3 ⁸ × 5 ⁶ × 7 ⁵ × bedeutet 11 ⁶ × 13 ⁹ Kopien des Zeichens des nächsten Elements s. Das Symbol ⋅ steht für „und“ und ist eine kürzere Notation für das Grundvokabular: p ⋅ q bedeutet ~ (~ p ∨ ~ q).



Dieses Beispiel, wie Nagel und Newman geschrieben haben, „veranschaulicht eine allgemeine und tiefgreifende Idee, die Gödels Entdeckung zugrunde liegt: Wir können sehr genau über die typografischen Eigenschaften langer Zeichenfolgen sprechen, jedoch nicht direkt, sondern durch die Eigenschaften der Faktorisierung großer Ganzzahlen.



Metamathematische Aussagen können auch in Symbole umgewandelt werden. "Es gibt eine bestimmte Folge von Formeln mit der Gödel-Zahl x, die eine Formel mit der Gödel-Zahl k beweist" - oder kurz gesagt, "eine Formel mit der Gödel-Zahl k ist beweisbar". Es war die Fähigkeit, solche Aussagen zu "rechnen", die den Grundstein für den Putsch legte.

G für sich

Außerdem erkannte Gödel, dass es möglich war, Gödels eigene Zahl, die eine Formel bezeichnet, durch die Formel selbst zu ersetzen - und dies führt bereits zu endlosen Problemen.



Um zu verstehen, wie diese Substitution funktioniert, betrachten Sie die Formel (∃x) (x = sy). Es bedeutet "es gibt eine Variable x, die das nächste Element für y ist" oder einfacher "y '' '' hat das nächste Element". Wie alle Formeln hat es eine eigene Gödel-Zahl - eine große ganze Zahl, nennen wir es m.



Geben Sie nun anstelle des Symbols y die Zahl m in die Formel ein. Das Ergebnis ist eine neue Formel (∃x) (x = sm), was bedeutet, dass „m das nächste Element hat“. Wie lautet die Gödel-Zahl für diese Formel? Wir müssen drei Merkmale vermitteln: Wir haben mit einer Formel begonnen, die Gödels Zahl m hat. Darin haben wir das y-Symbol durch das m-Symbol ersetzt. Und gemäß dem zuvor beschriebenen Übereinstimmungsschema ist die Gödel-Zahl des Symbols y 17. Wir bezeichnen dann die Gödel-Zahl der neuen Formel sub (m, m, 17).



Die Substitution bildet die Grundlage für Gödels Beweis.





Student Kurt Gödel in Wien. Er veröffentlichte 1931, ein Jahr nach Erhalt seines Diploms, Unvollständigkeitssätze.



Er betrachtete die folgende mathematische Aussage: "Die Formel mit der Gödel-Zahl sub (y, y, 17) kann nicht bewiesen werden." Wenn wir uns an die Notation erinnern, die wir gerade übernommen haben, wissen wir, dass wir die Formel mit der Gödel-Zahl sub (y, y, 17) erhalten, indem wir die Formel mit der Gödel-Zahl y (eine unbekannte Variable) nehmen und diese Variable y überall dort einsetzen, wo das Symbol mit steht Gödel Nummer 17 (dh wo immer y vorkommt).



Der Kopf beginnt sich bereits zu drehen, aber wir können unsere metamathematische Aussage „Eine Formel mit Gödels Zahlensub (y, y, 17) kann nicht bewiesen werden“ definitiv in eine Formel mit einer eindeutigen Gödel-Zahl übersetzen. Nennen wir es n.



Und die letzte Stufe der Substitutionen: Gödel erstellt eine neue Formel, die die Zahl n ersetzt, wo immer y in der vorherigen Formel erscheint. Seine neue Formel lautet wie folgt: „Die Formel mit Gödels Nummer sub (n, n, 17) kann nicht bewiesen werden“. Nennen wir diese Formel G.



G hat natürlich eine Gödel-Nummer. Was ist das für eine Nummer? Voila - es sollte sub sein (n, n, 17). Per Definition ist sub (n, n, 17) die Gödel-Zahl für die Formel, die erhalten wird, indem die Formel durch die Gödel-Zahl n genommen und n ersetzt wird, wo immer ein Symbol mit der Gödel-Zahl gleich 17 in der Formel vorkommt. Und G ist genau eine solche Formel und es gibt! Da ganze Zahlen auf einzigartige Weise in Primfaktoren zerlegt werden, wird uns klar, dass die Formel G nur über die Formel G selbst und nichts anderes aussagt.



G sagt, dass es selbst nicht bewiesen werden kann.



Aber kann G bewiesen werden? Wenn es möglich wäre, würde dies bedeuten, dass es eine Folge von Formeln gibt, die eine Formel mit der Gödel-Zahl sub (n, n, 17) beweisen. Dies ist jedoch das Gegenteil der Formel G, die besagt, dass es keinen solchen Beweis gibt. Entgegengesetzte Aussagen G und ~ G in einem konsistenten Axiomensystem können nicht gleichzeitig wahr sein. Daher muss G nicht beweisbar sein.



Obwohl G nicht bewiesen werden kann, ist es definitiv wahr. G sagt, dass „die Formel mit der Gödel-Zahl sub (n, n, 17) nicht bewiesen werden kann“, genau das haben wir festgelegt! Da G eine wahre, aber unbeweisbare Aussage ist, die innerhalb des axiomatischen Systems existiert, mit dem wir es konstruiert haben, ist dieses System unvollständig.



Sie könnten denken, wir könnten einfach ein zusätzliches Axiom hinzufügen, es verwenden, um G zu beweisen und dieses Paradoxon aufzulösen. Aber das ist unmöglich. Gödel hat gezeigt, dass das erweiterte Axiomensystem es ermöglichen wird, eine neue wahre Formel G 'nach dem gleichen Schema wie zuvor zu erstellen, die im Rahmen des neuen erweiterten Systems nicht bewiesen werden kann. Wenn Sie versuchen, ein vollständiges mathematisches System aufzubauen, werden Sie Ihren eigenen Schwanz nur erfolglos verfolgen.

Fehlender Konsistenznachweis

Wir wissen jetzt, dass eine Reihe von Axiomen unvollständig ist, wenn sie konsistent ist. Dies ist Gödels erster Unvollständigkeitssatz. Das zweite folgt leicht daraus - kein einziger Satz von Axiomen kann seine Konsistenz beweisen.



Was würde es bedeuten, wenn eine Reihe von Axiomen beweisen könnte, dass es niemals kontrovers sein würde? Dies würde bedeuten, dass auf diesen Axiomen eine Folge von Formeln aufgebaut ist, die eine Formel beweisen, die metamathematisch bedeutet, dass „diese Menge von Axiomen konsistent ist“. Aber dann wäre nach dem ersten Satz dieser Satz von Axiomen notwendigerweise unvollständig.



Zu sagen, dass „die Menge der Axiome unvollständig ist“, ist dasselbe wie zu sagen, dass es eine wahre Formel gibt, die nicht bewiesen werden kann. Und das entspricht unserer Formel G. Und wir wissen, dass die Axiome G nicht beweisen können.



Also konstruierte Gödel einen Beweis durch Widerspruch: Wenn eine Reihe von Axiomen ihre eigene Konsistenz beweisen könnte, dann könnten wir G beweisen. Aber wir können nicht. Folglich beweist kein Satz von Axiomen seine eigene Konsistenz.



Gödels Beweis tötete die Suche nach einem konsistenten und vollständigen mathematischen System. Mathematiker "versäumten es, die volle Tiefe der Unvollständigkeit zu erfassen", schrieben Nagel und Newman 1958. Diese Aussage gilt bis heute.

Siehe auch:

• " Warum Gödels Unvollständigkeitssatz schwer zu beweisen ist: Es geht um den Wortlaut, nicht nur um das Wesentliche. "
• " Gödels Unvollständigkeitssatz in 20 Minuten "
• " Geheimnisse des Bewusstseins und der Mathematik "