Erster Gödelscher Unvollständigkeitssatz/Textabschnitt

Lemma

Es sei ${}\Gamma$ eine widerspruchsfreie, arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Die Ableitungsmenge ${}\Gamma ^{\vdash }$ (also die Menge der zugehörigen Gödelnummern) sei schwach repräsentierbar in ${}\Gamma$.

Dann gibt es einen arithmetischen Satz ${}q\in L_{0}^{\rm {Ar}}$ derart, dass weder ${}q$ noch seine Negation ${}\neg q$ aus ${}\Gamma$ ableitbar ist.

Die Ableitungsmenge ${}\Gamma ^{\vdash }$ ist also nicht vollständig.

Beweis

Aus der Repräsentierbarkeit von ${}\Gamma ^{\vdash }$ folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir ${}a(x)$, mit der Eigenschaft, dass

$\Gamma \vdash s$

genau dann gilt, wenn

$\Gamma \vdash a(GN(s))$

gilt. Wir betrachten die Negation ${}\beta =\neg a$. Nach Fakt gibt es für ${}\beta$ einen Fixpunkt, also einen Satz ${}q$ mit

$\Gamma \vdash q\longleftrightarrow \beta (GN(q))$

bzw.

$\Gamma \vdash q\longleftrightarrow \neg a(GN(q)).$

Sowohl aus ${}\Gamma \vdash q$ als auch aus ${}\Gamma \vdash \neg q$ ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.

$\Box$

Man beachte, dass die Repräsentierbarkeit der Ableitungsmenge hier eine explizite Voraussetzung ist, die nicht aus der allgemein vorausgesetzten Eigenschaft, Repräsentierungen zu erlauben, folgt. Letztere bezieht sich nur auf rekursive (entscheidbare) Relationen und Funktionen, es wird aber nicht vorausgesetzt, dass ${}\Gamma$ selbst oder ${}\Gamma ^{\vdash }$ rekursiv ist.

Bemerkung  

Was passiert mit den Voraussetzungen in Fakt, wenn man den Satz ${}q$ (oder seine Negation) einfach zu ${}\Gamma$ hinzunimmt? Zunächst führt die Hinzunahme von ${}q$ noch von ${}\neg q$ zu einem widersprüchlichen System. Im Beweis haben wir die Annahme ${}\Gamma \vdash q$ (bzw. $\Gamma \vdash \neg q$) zu einem Widerspruch geführt, das bedeutet aber nicht ${}\Gamma '=\Gamma \cup \{q\}\vdash p\wedge \neg p$. Ein Problem ist hierbei, dass die neue Ableitungsmenge ${}(\Gamma \cup \{q\})^{\vdash }$ nicht mehr repräsentierbar in ${}\Gamma \cup \{q\}$ sein muss. Vor allem aber ist sie keinesfalls mit dem alten Ableitungsausdruck ${}a(x)$ repräsentierbar, sondern, wenn überhaupt, mit einem neuen ${}a'(x)$. Für dieses gibt es dann wieder einen neuen Fixpunkt ${}q'$. Es gibt keine rekursive Strategie, ${}\Gamma$ zu einer vollständigen Theorie aufzufüllen.

Kurt Gödel (1906-1978) bewies im Alter von ${}24$ Jahren seine Unvollständigkeitssätze.

Die folgende Aussage heißt erster Gödelscher Unvollständigkeitssatz.

Satz

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube.

Dann ist ${}\Gamma ^{\vdash }$ unvollständig.

Es gibt also einen arithmetischen Satz, für den weder ${}\Gamma \vdash q$ noch ${}\Gamma \vdash \neg q$ gilt.

Beweis

 Wir nehmen an, dass ${}\Gamma ^{\vdash }$ vollständig ist. Da ${}\Gamma$ aufzählbar ist, ist ${}\Gamma ^{\vdash }$ nach Fakt aufzählbar und nach Fakt auch entscheidbar. Da ${}\Gamma$ Repräsentierungen erlaubt, ist insbesondere ${}\Gamma ^{\vdash }$ repräsentierbar. Daher sind die Voraussetzungen von Fakt erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.

$\Box$

Korollar

Es sei ${}\Gamma \subseteq L^{\rm {Ar}}$ eine arithmetische korrekte Ausdrucksmenge, die aufzählbar sei und Repräsentierungen erlaube.

Dann gibt es einen in (der Standardinterpretation) ${}\mathbb {N}$ wahren Satz, der nicht zu ${}\Gamma ^{\vdash }$ gehört, der also nicht aus ${}\Gamma$ formal ableitbar ist.

Beweis

Die Korrektheit bedeutet, dass ${}\Gamma ^{\vdash }\subseteq \mathbb {N} ^{\vDash }$ gilt. Dies sichert zugleich die Widerspruchsfreiheit von ${}\Gamma$. Gemäß Fakt gibt es einen Satz ${}q$, der weder selbst noch seine Negation ${}\neg q$ aus ${}\Gamma$ ableitbar ist. Da aber ${}\mathbb {N} ^{\vDash }$ vollständig ist, muss entweder ${}q$ oder ${}\neg q$ in ${}\mathbb {N}$ wahr sein.

$\Box$

Diese Aussage ist für die erststufige Peano-Arithmetik und jedes größere aufzählbare widerspruchsfreie System anwendbar, wobei wir aber die Eigenschaft der Peano-Arithmetik, Repräsentierungen zu erlauben, nicht bewiesen haben.