Gödelscher Unvollständigkeitssatz
Der Gödelsche Unvollständigkeitssatz beschäftigt sich mit der Beweisbarkeit von Aussagen in formalen Theorien.
Table of contents |
2 Gödels Satz 3 Bedeutung des Unvollständigkeitssatzes 4 Genauere Formulierung 5 Interessantes 6 Literatur |
Aussagen sind dabei Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen und die mittels einer Semantik eine Bedeutung erhalten und sich dadurch in wahre und falsche Aussagen unterteilen lassen (wobei zu einer gegebenen Aussage nicht notwendigerweise sofort klar ist, ob sie wahr oder falsch ist). Für gewöhnlich lassen sich dabei zu einer Aussage auch leicht komplementäre Aussagen derart konstruieren, dass entweder die Aussage selbst oder die komplementäre Aussage wahr ist, aber niemals beide zugleich.
Die Aufgabe einer formalen Theorie ist es dann, aus bestimmten Grundaussagen, die generell als wahr angenommen werden über allgemein akzeptierte Ableitungsregeln weitere wahre Aussagen abzuleiten. Eine Folge solcher Ableitungen nennt man dann Beweis der entsprechenden abgeleiteten Aussage. Im Idealfall wünscht man sich, dass aus der Menge der Grundaussagen und den Ableitungsregeln alle wahren Aussagen abgeleitet, also bewiesen werden können. Ein derartiges System nennt man dann vollständig (andernfalls unvollständig). Eine formale Theorie sollte zudem auch widerspruchsfrei sein, das heißt es lassen sich keine falschen Aussagen ableiten. Genauer formuliert lassen sich nicht gleichzeitig eine Aussage und eine dazu (im obigen Sinne) komplementäre Aussage ableiten. Eine formale Theorie, die dem nicht genügt nennt man widersprüchlich.
Der Mathematiker Kurt Gödel wies im Jahre 1930 nach, dass man in Systemen wie der Arithmetik nicht alle Aussagen beweisen oder widerlegen kann. Sein Satz besagt:
Damit dieser Ansatz funktioniert, muss das zugrundegelegte formale System also mindestens Zählungen erlauben. Für einfache Systeme gilt der Unvollständigkeitssatz daher nicht. Die Möglichkeit von Zählungen ist aber die einzige wesentliche Eigenschaft einer formalen Theorie, für die der Satz gilt. Dies ist für relativ viele mathematische Theorien erfüllt.
Normalerweise könnte man sich dadurch behelfen, dass man für alle Sätze, die weder bewiesen noch widerlegt werden können, einfach definiert, ob sie als wahr oder falsch gelten und die Definition dem formalen System hinzufügt. Im neuen, erweiterten System existiert dann für diese Sätze ein Beweis, nämlich einfach die hinzugefügte Definition. Gödel zeigte jedoch, dass auch das erweiterte System unvollständig bleibt, da stets unbeweisbare Sätze übrigbleiben.
Eine streng formalisierte Prädikatenlogik erster Stufe war eines von Hilberts Konzepten. Am Ende seines Programms sollte die gesamte Mathematik auf die einfache Arithmetik zurückgeführt und auf ein axiomatisches System gestellt werden, aus dem alle mathematischen Sätze streng ableitbar sind.
Gödels Arbeit war durch Hilberts Programm motiviert. Er verwendete die von Hilbert vorgeschlagenen Methoden, um seinen Unvollständigkeitssatz zu zeigen. Gödel bewies auch den folgenden Satz
Die Folge daraus ist, dass man an die Korrektheit von formalen Systemen glauben muss, sie lassen sich nicht beweisen.
Ein anderer Ansatz, der unüberbrückbare Lücken in Hilberts Programm nachweist, stammt von dem Mathematiker Alan Turing. Er erfand die Turingmaschine und formulierte deren Halteproblem.
Der Gödelsche Satz besagt genauer, dass jedes Beweissystem für die Menge der wahren arithmetischen Formeln unvollständig ist (sofern man voraussetzt, dass die Arithmetik widerspruchsfrei ist - was, wie Gödel auch zeigt, nicht mit Mitteln der untersuchten Theorie allein bewiesen werden kann). Das heißt:
In jeder formalen Theorie, welche mindestens so mächtig wie die Theorie der natürlichen Zahlen (Peano-Arithmetik) ist, bleiben wahre (und falsche) arithmetische Formeln übrig, die nicht innerhalb der Theorie beweisbar (widerlegbar) sind.
Damit eine Theorie (in der Prädikatenlogik erster Stufe, PL1) die Voraussetzungen für die Unvollständigkeit erfüllt, muss gelten:
Die Diagonalisierung in Gödels Beweis ist nun eine Anwendung eines Ausdruckss P(x) auf die eigene Gödelnummer. Ist die Gödelnummer des Ausdrucks (und damit der Zeichenreihe) P(x) zum Beispiel 12345, so ist die Diagonalisierung der Zahl 12345 die Gödelnummer von P(12345) (selbstverständlich hat eine Zahl, hier 12345, auch eine Gödelnummer, die entsteht, indem man alle vorkommenden Ziffern gödelisiert).
"Besagt" der Ausdruck B(x) also, dass x beweisbar ist, und ist zum Beispiel 12345 die Gödelnummer von B(x), so ist ¬B(12345) eine unbeweisbare Aussage. Diese Aussage besagt dann nämlich: Die Formel mit der Gödelnummer 12345 ist nicht beweisbar. 12345 ist aber die Gödelnummer von B(x). Also sagt ¬B(12345): Ich bin nicht beweisbar. Wenn PA korrekt ist, so ist dieser Satz wahr, aber nicht beweisbar.
Gödels ursprünglicher Beweis ging noch weiter. Er wollte Rückgriffe auf die Semantik, insbesondere die Korrektheit, vermeiden. Deswegen bewies er seinen Unvollständigkeitssatz unter der Voraussetzung der ω-Konsistenz: Eine Theorie ist ω-inkonsistent, wenn ein Ausdruck mit einer einzigen freien Variable x existiert, für den beweisbar ist, zugleich aber für alle beweisbar ist.
Rosser erweiterte das Gödelsche Resultat, indem er einen Unvollständigkeitsbeweis lieferte, für den nicht die Menge der Ausdrücke, deren Diagonalisierung beweisbar ist, beschrieben wird, sondern eine zu dieser Menge disjunkte Obermenge der Ausdrücke, deren Diagonalisierung widerlegbar ist. Dadurch ist auch der Bezug auf die ω-Konsistenz überflüssig.
Gödels zweiter Unvollständigkeitssatz ist eine leicht zu sehende Konsequenz aus dem ersten. Da Gödel beweisbare Aussagen innerhalb der Prädikatenlogik formalisierte (beispielsweise durch das Prädikat ), lässt sich auch folgende Aussage bilden: , wobei die Gödelnummer von einer beliebigen Kontradiktion, zum Beispiel , ist. Die Aussage "behauptet" die Nichtbeweisbarkeit einer Kontradiktion, und damit die Widerspruchsfreiheit der gesamten Theorie (der Peano-Arithmetik). ist in PA nicht beweisbar. Um die Nicht-Beweisbarkeit zu zeigen, wird eine Fixpunktkonstruktion verwendet. Sei die Gödelisierungsfunktion, eine Aussage, ein Prädikat. heißt Fixpunkt für , wenn beweisbar ist. Über einfache aussagenlogische Konstruktionen lässt sich beweisen, dass beweisbar ist, wenn Fixpunkt von ist. Außerdem kann leicht gezeigt werden, dass, wenn Fixpunkt von ist, nicht beweisbar ist, falls PA konsistent ist. Daraus folgt dann, dass nicht beweisbar ist.
Durch diese erstaunlichen Sätze ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder wahre mathematische Satz kann aus den wie auch immer gewählten Axiomen eines mathematischen Teilgebietes (zum Beispiel Arithmetik, Geometrie, Algebra etcetera) formal abgeleitet werden.
Viel Verwirrung entsteht aus dem Zusammenhang der Gödelschen Unvollständigkeitssätze mit dem Gödelschen Vollständigkeitssatz. Der Gödelsche Vollständigkeitssatz besagt, dass in der Prädikatenlogik erster Stufe (PL1) alle beweisbaren Sätze wahr, und umgekehrt alle wahren Sätze beweisbar sind, und damit, dass Syntax und Semantik für die PL1 zusammenfallen.
Im Gegensatz dazu wird in den Unvollständigkeitssätzen bereits ein Modell betrachtet, die Struktur der natürlichen Zahlen, die Peano-Arithmetik. Die Unvollständigkeitssätze sagen dann aus, dass in diesem Modell wahre Sätze existieren, die in der Prädikatenlogik erster Stufe nicht bewiesen werden können. Da sie wahr sind in PA, zeigt dies auch, dass die Peano-Arithmetik nicht in PL1 (bis auf Isomorphie) formalisiert werden kann.
Konkret bezog sich Gödels Aufsatz auf die Principia Mathematica, ein großes formales System, das Bertrand Russell und Alfred North Whitehead zwischen 1910 und 1913 veröffentlichten. Gödel zeigte jedoch auf, dass jedes System mit der gleichen Mächtigkeit wie die P.M. ebenso anfällig ist.
Dieser Artikel befindet sich derzeit im Reviewprozess. Hilf mit, ihn zu verbessern!
Grundbegriffe
Gödels Satz
Gödels Argumentation läuft auf eine Abzählung aller Sätze innerhalb des formalen Systems hinaus, jeder Satz erhält eine eigene Nummer. Er konstruiert dann eine Aussage der Form: "Der Satz mit der Nummer x ist nicht beweisbar" und setzt für x die Nummer dieser Aussage ein. Insgesamt erhält er einen Satz der Form "Ich bin nicht beweisbar". Es gibt nun zwei Möglichkeiten: Entweder dieser "Satz x" ist wahr, dann ist er nicht beweisbar (was ja der Inhalt von Gödels Satz ist). Oder er ist falsch, dann muss ja das Gegenteil gelten, also muss der Satz beweisbar und demnach wahr sein. Das ist ein Widerspruch; also kann dieser Satz nur falsch sein, wenn das formale System widersprüchlich ist.Bedeutung des Unvollständigkeitssatzes
Gödel versetzte mit seinem Unvollständigkeitssatz einem Ansatz von David Hilbert zur vollständigen Begründung und Formalisierung der Mathematik einen schweren Schlag. Dieser Ansatz ist als Hilberts Programm bekannt geworden und wurde von ihm im Jahre 1921 veröffentlicht. Hilbert schlug vor, die Widerspruchsfreiheit von komplexeren Systemen durch einfachere Systeme nachzuweisen. HIntergrund ist der, dass einem Beweis zur Widerspruchsfreiheit eines Systems, der in diesem System selbst gegeben ist, nicht getraut werden kann. Der Grund ist, dass sich aus einem Widerspruch heraus alles beweisen lässt, also liesse sich aus einem Widerspruch im System auch die Widerspruchsfreiheit des Systems beweisen. Daher sollte die Widerspruchsfreiheit in einem einfacheren System bewiesen werden.
Gödel hatte damit gewissermaßen Hilbert mit seinen eigenen Methoden geschlagen.Genauere Formulierung
Nach dem Satz von Löwenheim-Skolem findet man zu jeder Theorie in PL1 ein Modell mit der Mächtigkeit der Signatur. Für "normale" Theorien existiert also ein abzählbares Modell, beispielsweise die natürlichen Zahlen (das heißt es lässt sich für jede Theorie in PL1 auch ein Modell finden, in dem die Objekte natürliche Zahlen sind). Die Idee von Gödel war, Formeln der Theorie selbst zum Objekt derselben zu machen. Dazu wurden die Formeln gödelisiert, das heißt eine (umkehrbar eindeutige) Abbildung von Formeln auf natürliche Zahlen gebildet. Das kann man zum Beispiel dadurch erreichen, dass jedem Symbol der Signatur eine Zahl zugeordnet wird, die dann verkettet werden. Ordnet man der 0 die 1 und = die 2 zu, so ist die Gödelnummer der Formel (in dem Spezialfall) 0=0 die 121. Die Verkettungsoperation ist einfach durch Exponentierenieren zu realisieren. Es lassen sich auch die syntaktisch wohlgeformten, und schließlich die beweisbaren Formeln durch arithmetische Ausdrücke (Addition, Multiplikation, Exponentiationiation) beschreiben.Interessantes
Gödel nannte seinen Aufsatz Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, weil er plante einen zweiten Aufsatz zu verfassen, in dem er den Beweis genauer erläutern wollte. Der erste Aufsatz fand jedoch bereits so große Anerkennung, dass der Bedarf für einen zweiten entfiel, und daher auch nie geschrieben wurde.Literatur
Siehe auch: Formales System (Logik)