Gödelscher Unvollständigkeitssatz

Der Gödelsche Unvollständigkeitssatz besagt, dass jedes Beweis system 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 Theorie alleine bewiesen werden kann, was heißt:

In jeder Theorie, welche mindestens so maechtig wie die Theorie der natuerlichen Zahlen (Peano-Arithmetik) ist, bleiben wahre (und falsche) arithmetische Formeln übrig, die nicht beweisbar (widerlegbar) sind.

Damit eine Theorie (in der Praedikatenlogik erster Stufe, PL1) die Vorraussetzungen fuer die Unvollstaendigkeit erfuellt, muss gelten:

Zu jeder durch einen Ausdruck G(x) beschriebenen Menge ist das Komplement beschreibbar
Zu jeder durch einen Ausdruck G(x) beschriebenen Menge M ist die Menge M*={n|d(x)∈M} beschreibbar; Dabei ist d(x) die Diagonalisierung von x.
Die Menge der beweisbaren Ausdruecke der Theorie ist durch einen Ausdruck der Form G(x) beschreibbar.

Nach dem Satz von Loewenheim-Skolem findet man zu jeder Theorie in PL1 ein Modell mit der Maechtigkeit der Signatur. Fuer "normale" Theorien existiert also ein abzaehlbares Modell, z.B. die natuerlichen Zahlen. Die Idee von Goedel war, Formeln der Theorie selbst zum Objekt derselben zu machen. Dazu wurden die Formeln goedelisiert, d.h. eine (umkehrbar eindeutige) Abbildung von Formeln auf natuerliche Zahlen gebildet. Das kann man z.B. 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 Goedelnummer der Formel (in dem Spezialfall, des Terms) 0=0 die 121. Die Verkettungsoperation ist einfach durch Exponentieren zu realisieren. Es lassen sich auch die syntaktisch wohlgeformten, und schliesslich die beweisbaren Formeln durch arithmetische Ausdruecke (Addition, Multiplikation, Exponentiation) beschreiben.

Die Diagonalisierung in Goedels Beweis ist nun eine Anwendung eines Ausdrucks P(x) auf die eigene Goedelnummer. Ist die Goedelnummer des Ausdrucks (und damit der Zeichenreihe) P(x) zum Beispiel 12345, so ist die Diagonalisierung der Zahl 12345 die Goedelnummer von P(12345) (selbstverstaendlich hat eine Zahl, hier 12345, auch eine Goedelnummer, die entsteht, indem man alle vorkommenden Ziffern goedelisiert).

"Besagt" der Ausdruck B(x) also, dass x beweisbar ist, und ist zum Beispiel 12345 die Goedelnummer von B(x), so ist ¬B(12345) eine unbeweisbare Aussage. Diese Aussage besagt dann naemlich: Die Formel mit der Goedelnummer 12345 ist nicht beweisbar. 12345 ist aber die Goedelnummer von B(x). Also sagt ¬B(12345): Ich bin nicht beweisbar. Wenn PA korrekt ist, so ist dieser Satz wahr, aber nicht beweisbar.

Goedels urspruenglicher Beweis ging noch weiter. Er wollte Rueckgriffe auf die Semantik, insbesondere die Korrektheit, vermeiden. Deswegen bewies er seinen Unvollstaendigkeitssatz unter der Vorraussetzung der ω-Konsistenz: Eine Theorie ist ω-inkonsistent, wenn ein Ausdruck mit einer einzigen freien Variable x existiert, fuer den $\exists xP(x)$ beweisbar ist, zugleich aber fuer alle $n<\omega$ $\neg P(n)$ beweisbar ist.

Rosser erweiterte das Goedelsche Resultat, indem er einen Unvollstaendigkeitsbeweis lieferte, fuer den nicht die Menge der Ausdruecke, deren Diagonalisierung beweisbar ist, beschrieben wird, sondern eine zu dieser Menge disjunkte Obermenge der Ausdruecke, deren Diagonalisierung widerlegbar ist. Dadurch ist auch der Bezug auf die ω-Konsistenz ueberfluessig.

Durch diesen erstaunlichen Satz ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder wahre mathematische Satz kann aus den wie auch immer gewählten Axiomen eines mathematischen Teilgebietes (z.B. Arithmetik, Geometrie, Algebra etc.) abgeleitet werden.