Dieser Artikel skizziert Beweise der Gödelschen Unvollständigkeitssätze. Dabei handelt es sich um zwei mathematische Sätze, die zu den wichtigsten Ergebnissen der Logik gezählt werden und die von Kurt Gödel 1930 bewiesen wurden.

Der erste Unvollständigkeitssatz besagt, dass kein konsistentes Axiomensystem, dessen Theoreme von einem Algorithmus aufgezählt werden können, alle wahren Aussagen über natürliche Zahlen mit Addition und Multiplikation beweisen kann. Der zweite Unvollständigkeitssatz besagt, dass ein solches System die eigene Widerspruchsfreiheit nicht beweisen kann.

Erster Unvollständigkeitssatz

Der erste Unvollständigkeitssatz lässt sich wie folgt allgemein formulieren:

Sei ein rekursiv aufzählbares und widerspruchsfreies formales System, in dem die Robinson-Arithmetik interpretierbar ist. Dann ist unvollständig. (Es gibt also arithmetische Formeln, die in weder beweisbar noch widerlegbar sind.)

Dabei ist die Robinson-Arithmetik (auch ) eine schwache Form der Arithmetik in Prädikatenlogik erster Stufe. Diese verfügt über die Konstante „null“, die Nachfolgerfunktion , welche intuitiv zu einer gegebenen Zahl eins addiert, sowie die Funktionen für Addition und für Multiplikation. Sie hat folgende Axiome, die elementare Eigenschaften der natürlichen Zahlen und der arithmetischen Operationen formalisieren:

Null hat keinen Vorgänger: Wenn x+1 = y+1 gilt, dann ist x=y: Jede Zahl ist gleich Null oder hat einen Vorgänger: Axiomatische Definition von Addition und Multiplikation:

Die Punkte über den Ausdrücken deuten hier und im weiteren Verlauf des Artikels an, dass diese Ausdrücke zu der betrachteten Sprache gehören. So ist (s. u.) eine Formel des betrachteten formalen Systems, während eine Relation zwischen natürlichen Zahlen ist. Das "Numeral" einer natürlichen Zahl , die Repräsentierung der natürlichen Zahl im System, wird mit bezeichnet, das Numeral von 4 ist z. B. der Term .

Im Folgenden wird angenommen, dass die Robinson-Arithmetik selbst ist. Der Beweis lässt sich genauso für jedes andere System durchführen, in dem sich die Arithmetik so interpretieren lässt, dass sich alle Funktionen aus der Robinson-Arithmetik so durch Ausdrücke des neuen Systems definieren lassen, dass alle Theoreme der Robinson-Arithmetik in Theoreme des anderen Systems übergehen. Insbesondere wird davon ausgegangen, dass das Axiomensystem entscheidbar ist. Gödel bewies den Satz ursprünglich für das viel stärkere System der Principia Mathematica. Ebenso lässt sich der Beweis für die Zermelo-Fraenkel-Mengenlehre durchführen, die als einziges nichtlogisches Zeichen die Elementrelation hat, in der Zahlen aber als Mengen interpretiert werden können, sodass alle Theoreme der Robinson-Arithmetik als Theoreme der Mengenlehre interpretierbar sind. Der Beweis lässt sich ebenfalls für ein lediglich aufzählbares Axiomensystem adaptieren.

Der Beweis zerfällt in vier Teile:

Arithmetisierung der Syntax: Jedem Ausdruck der Theorie wird eine Zahl, die sogenannte Gödelnummer, zugewiesen, aus der sich die Formel wieder effektiv rekonstruieren lässt. Diese Nummerierung wird auf endliche Folgen von Formeln erweitert. Arithmetisierung der Beweisbarkeitsrelation: Eine Formel wird konstruiert, sodass für jedes Paar von Zahlen und , genau dann beweisbar ist, wenn die Gödelnummer eines Beweises einer Formel ist, deren Gödelnummer ist. Konstruktion des Gödelsatzes: Es wird eine Formel konstruiert, die informell besagt „Ich bin nicht beweisbar.“, der sogenannte Gödelsatz. Nachweis der Unbeweisbarkeit: Es wird gezeigt, dass der Gödelsatz weder bewiesen noch widerlegt werden kann.

Arithmetisierung der Syntax

Das Hauptproblem bei der Ausführung des oben beschriebenen Beweises scheint zunächst darin zu liegen, dass bei der Konstruktion einer Aussage , die äquivalent zu „ ist unbeweisbar“, eine Referenz auf enthalten muss. Gödels Lösung ist, zu zeigen, dass Aussagen auf eine solche Weise Zahlen zugewiesen werden können, dass das Beweisen einer Aussage dadurch ersetzt werden kann, dass überprüft wird, ob die der Aussage zugewiesene Zahl eine gewisse arithmetische Eigenschaft hat. Dies ermöglicht die Konstruktion einer selbstbezüglichen Formel, die unendlichen Regress vermeidet.

Der erste Schritt des Beweises besteht somit darin, Formeln und endliche Folgen von Formeln (injektiv) auf natürliche Zahlen abzubilden. Diese Zahlen heißen Gödelnummern der Formeln. Zunächst wird jedem Symbol der Sprache der Arithmetik eine Zahl zugeordnet, ähnlich dem ASCII-Code, der jedem Buchstaben eine eindeutige Zahl zuordnet. Es gibt verschiedene Möglichkeiten dazu, hier wird direkt jedem Zeichen eine Ziffernfolge zugeordnet.

Nummer Symbol Bedeutung 11 null 12 Nachfolgerfunktion 13 Gleichheit 14 Addition 15 Multiplikation 16 ( linke Klammer 17 ) rechte Klammer Nummer Symbol Bedeutung 18 eine Variable 19 Strich (für weitere Variablen x', x'', …) 21 Existenzquantor 22 Allquantor 23 logisches und 24 logisches oder 25 Negation

Man sieht hier, dass das im 2. Axiom benutzte Symbol für Implikation () fehlt; bekanntlich ist aber äquivalent zu (zumindest in der klassischen Logik).

Die Gödelnummer einer Formel erhält man durch Aneinanderreihung der Gödelnummern für jedes Symbol der Formel. Jede Formel kann eindeutig aus ihrer Gödelnummer rekonstruiert werden. Die Gödelnummer einer Formel wird mit bezeichnet.

Mit dieser Gödelnummerierung erhält beispielsweise der Satz, der das Kommutativgesetz der Addition ausdrückt, die Nummer: 22 18 22 19 16 18 14 19 13 19 14 18 17 (die Leerzeichen dienen nur der Lesbarkeit.) Nicht alle Zahlen repräsentieren Formeln, beispielsweise steht 13 22 14 18 für "", was keine korrekte Formel ist.

Im System wird jede natürliche Zahl n durch ihr Numeral repräsentiert. Umgekehrt hat auch jedes Numeral eine Gödelnummer, so ist die Gödelnummer für gleich: 12 12 12 12 11.

Die Zuweisung von Gödelnummern kann auf endliche Folgen von Formeln erweitert werden. Um die Gödelnummer einer endlichen Folge von Formeln zu erhalten, werden die Nummern der Formeln hintereinander geschrieben und jeweils durch eine Null getrennt. Da die Gödelnummer einer einzelnen Formel nie eine Null enthält, kann jede Formel der Folge eindeutig rekonstruiert werden.

Es ist wichtig, dass die formale Arithmetik einige einfache Tatsachen beweisen kann. Insbesondere muss sie beweisen können, dass jede Zahl eine Gödelnummer hat. Ebenso muss sie beweisen, dass es für die Gödelnummer einer Formel , die eine freie Variable besitzt, und für eine Zahl die Gödelnummer einer Formel , in der alle Vorkommen von durch die Gödelnummer von ersetzt wurden, gibt, und dass man diese Gödelnummer aus der ersten durch eine effektive Prozedur erhalten kann.

Die Beweisbarkeitsrelation

Das formale System besitzt Axiome und Schlussregeln, aus denen die Formeln des Systems bewiesen werden können. Ein formaler Beweis im System ist somit eine Kette von Formeln, in der jede entweder ein Axiom ist oder sich durch eine Schlussregel aus früheren Formeln gewinnen lässt.

Da das formale System entscheidbar ist, kann man effektiv entscheiden, ob eine gegebene Zahl Gödelnummer eines Axioms ist. Im Falle des endlich axiomatisierten Systems genügt es sogar, zu überprüfen, ob die Zahl zur Gödelnummer einer der sieben Axiome gleich ist.

Schlussregeln können als binäre Relationen zwischen Gödelnummern von Folgen von Formeln repräsentiert werden. So gibt es beispielsweise eine Schlussregel , durch die man aus den Formeln die Formel erhält. Dann besagt die Relation zu dieser Ableitungsregel, dass genau dann in Relation zu steht ( gilt), wenn die Gödelnummer einer Liste von Formeln ist, die und enthält, und die Gödelnummer einer Liste von Formeln ist, die aus den Formeln in der von kodierten Liste besteht und zusätzlich enthält. Da jede Ableitungsregel eine einfache formale Vorschrift ist, ist es möglich, effektiv zu entscheiden, ob zwei Zahlen und in Relation stehen.

Der zweite Schritt ist, zu zeigen, dass diese Gödelnummerierung benutzt werden kann, um den Begriff der Beweisbarkeit auszudrücken. Ein Beweis einer Formel ist eine Kette von Formeln, in denen jede ein Axiom ist oder aus früheren Aussagen durch eine Ableitungsregel entsteht, und in der die letzte Aussage ist. Damit lässt sich die Gödelnummer eines Beweises mit der oben angegebenen Methode zur Kodierung endlicher Folgen von Formeln definieren. Zudem lässt sich eine Relation definieren, die für zwei Zahlen and genau dann wahr (und beweisbar) ist, wenn die Gödelnummer eines Beweises von ist, und ist.

ist eine arithmetische Relation, ebenso wie etwa „“, nur viel komplizierter. Für alle spezifischen Zahlen und ist entweder die Formel oder ihre Negation beweisbar (aber nicht beide). Dies liegt daran, dass die Relation zwischen den Zahlen auf einfache Weise „überprüft“ werden kann. Die Konstruktion der Formel hängt entscheidend davon ab, dass das Axiomensystem entscheidbar ist; ohne diese Annahme wäre die Formel nicht konstruierbar.

Damit lässt sich nun eine Relation definieren, die die metasprachliche Aussage „ ist beweisbar“ repräsentiert: ist beweisbar, wenn es eine Zahl gibt, die einen Beweis für kodiert:

Dabei ist "" ebenso wie "" nur eine Abkürzung für eine bestimmte, sehr lange, arithmetische Formel; die Symbole "" und "" selbst gehören nicht zur Sprache des Systems.

Ein wichtiges Merkmal der Formel ist, dass beweisbar ist, wenn beweisbar ist. Denn wenn beweisbar ist, dann existiert ein Beweis mit Gödelnummer . Dann ist wahr und, wie oben dargelegt, beweisbar. Damit ist erst recht die schwächere Existenzaussage beweisbar.

Formalisiert lassen sich die Ergebnisse dieses Abschnitts mit Hilfe des Ableitbarkeitssymbols zusammenfassen:

Diagonalisierung

Der nächste Schritt besteht darin, eine Aussage zu konstruieren, die ihre eigene Unbeweisbarkeit behauptet. Hierzu lässt sich das Diagonallemma anwenden. Dieses besagt, dass es in der Arithmetik und stärkeren formalen Systemen für jede Formel mit freier Variable eine Aussage gibt, sodass das System die Äquivalenz

beweist. Man erhält also eine Formel mit der intuitiven Bedeutung „Ich habe die Eigenschaft .“ Wenn man für die Negation von einsetzt, erhält man die Aussage mit der Bedeutung „Meine Gödelnummer ist die Gödelnummer einer unbeweisbaren Formel“, also „Ich bin unbeweisbar“.

Die Formel ist nicht direkt gleich zu ; vielmehr besagt , dass man, wenn man eine gewisse Berechnung ausführt, die Nummer einer unbeweisbaren Aussage erhält. Wenn man nun diese Berechnung durchführt, zeigt sich aber, dass die entstehende Zahl die Gödelnummer von selbst ist. Diese Konstruktion ähnelt folgender natürlichsprachigen Aussage: "ist in Anführungszeichen und gefolgt von sich selbst unbeweisbar." ist in Anführungszeichen und gefolgt von sich selbst unbeweisbar. Dieser Satz bezieht sich nicht direkt auf sich selbst, aber man erhält die ursprüngliche Aussage, wenn man die angegebene Umformung durchführt, und damit behauptet der Satz seine eigene Unbeweisbarkeit. Der Beweis des Diagonallemmas benutzt eine ähnliche Methode.

Beweis der Unabhängigkeit des Gödelsatzes

Man nehme nun an, dass das formale System ω-konsistent, und damit konsistent, ist. Sei die Aussage, die im vorangehenden Abschnitt konstruiert wurde.

Wenn beweisbar wäre, dann wäre beweisbar. Aber ist äquivalent zur Negation von . Damit wäre das System inkonsistent, da es eine Aussage und ihre Negation beweisen würde. Also kann nicht beweisbar sein, da die Theorie nach Voraussetzung konsistent ist.

Wenn die Negation von beweisbar wäre, folgt aus der Konsistenz des Systems, dass nicht beweisbar ist. Daher kann keine natürliche Zahl die Gödelnummer eines Beweises von sein. Gleichzeitig ist die Negation von äquivalent zu . Damit beweist das System einerseits die Existenz einer Zahl mit einer bestimmten Eigenschaft, aber beweist andererseits für jede Ziffer , dass sie diese Eigenschaft nicht hat. Dies ist in einem -konsistenten System unmöglich. Damit ist die Negation von nicht beweisbar.