Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Vorlesung 13

Der erste Gödelsche Unvollständigkeitssatz

Wir haben gesehen, dass die Unentscheidbarkeit des Halteproblems über die arithmetische Repräsentierbarkeit von Registerprogrammen zur Unentscheidbarkeit der Arithmetik führt. Beim Beweis des ersten Gödelschen Unvollständigkeitssatzes arbeitet man mit einem Fixpunkt zu einem negierten Ableitungsprädikat, um eine „paradoxe“ Situation zu erhalten. Ein Ableitungsprädikat ${}a(x)$ soll die Eigenschaft haben, dass ${}\Gamma \vdash s$ genau dann gilt, wenn ${}\Gamma \vdash a(GN(s))$ gilt. Ein solches Ableitungsprädikat muss es im Allgemeinen nicht geben. Im folgenden Unvollständigkeitslemma gehört die Existenz eines Ableitungsprädikates zur Voraussetzung.

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 Satz 12.7 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 Lemma 13.1, 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.

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 Lemma 11.9 aufzählbar und nach Satz 11.10 auch entscheidbar. Da ${}\Gamma$ Repräsentierungen erlaubt, ist insbesondere ${}\Gamma ^{\vdash }$ repräsentierbar. Daher sind die Voraussetzungen von Lemma 13.1 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äß Satz 13.2 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.

Der zweite Gödelsche Unvollständigkeitssatz

Wenn die Ableitungsrelation ${}\Gamma ^{\vdash }$ repräsentierbar ist und der zugehörige repräsentierende arithmetische Ausdruck ${}a$ bekannt ist, so ist auch der im Beweis zu Lemma 13.1 verwendete Ausdruck ${}q$ , (also der Fixpunkt zu $\neg a(x)$ ) prinzipiell bekannt, da der Fixpunktsatz konstruktiv ist. Im Beweis des ersten Gödelschen Unvollständigkeitssatz war ein solches Ableitungsprädikat ${}a$ aber nur aufgrund der angenommenen Vollständigkeit vorhanden, die dann zum Widerspruch geführt wurde. Aus diesen Überlegungen ergibt sich weder die Existenz eines Ableitungsprädikates noch die eines Fixpunktes zum negierten Ableitungsprädikat.

Der zweite Gödelsche Unvollständigkeitssatz gibt hingegen explizit einen Satz an, der weder selbst noch seine Negation beweisbar ist, und zwar einen Satz von großer inhaltlicher Bedeutung: Es geht um den Satz, der die Widerspruchsfreiheit des gegebenen Systems behauptet.

Betrachten wir zunächst eine beliebige korrekte arithmetische Theorie ${}T\subseteq L^{\rm {Ar}}$ , also eine deduktiv abgeschlossene Satzmenge, die bei der Standardinterpretation in ${}\mathbb {N}$ nur wahre Sätze ergibt (dazu genügt es wegen der Korrektheit des Ableitungskalküls, dass sämtliche Sätze aus einem Axiomensystem ${}\Gamma$ für ${}T$ (also $T=\Gamma ^{\vdash }$ ) in ${}\mathbb {N}$ wahr sind). Da ${}\mathbb {N} ^{\vDash }$ , wie jede Gültigkeitsmenge eines Modells, vollständig und widerspruchsfrei ist, ist auch ${}T$ (als Teilmenge von ${}\mathbb {N} ^{\vDash }$ ) widerspruchsfrei. Daher gehört zu ${}T$ kein Satz der Form ${}p\wedge \neg p$ und auch nicht der Satz ${}\neg (0=0)$ (da ja die Identität ${}0=0$ dazugehört). Eine andere Frage ist es, ob das System bzw. die Theorie oder das Axiomensystem diese Unableitbarkeit eines widersprüchlichen Satzes auch „weiß“.

Schon im Unvollständigkeitslemma und im ersten Gödelschen Unvollständigkeitssatz kam wesentlich ein Ableitungsprädikat ${}a$ vor. Dieses hatte die Eigenschaft

\Gamma \vdash s{\text{ genau dann, wenn }}\Gamma \vdash a(GN(s)),

allerdings unter der Bedingung, dass ${}\Gamma ^{\vdash }$ entscheidbar und damit in ${}\Gamma$ (das Repräsentierungen erlaube) repräsentierbar ist. Aus der Entscheidbarkeit von ${}\Gamma$ folgt zwar die Aufzählbarkeit von ${}\Gamma ^{\vdash }$ , und daraus, wenn ${}\Gamma ^{\vdash }$ zusätzlich vollständig ist, auch die Entscheidbarkeit von ${}\Gamma ^{\vdash }$ , sonst aber nicht. Diese Überlegung haben wir schon in umgekehrter Richtung angewendet, indem wir aus der Unentscheidbarkeit der Arithmetik auf die Unvollständigkeit der Peano-Arithmetik geschlossen haben (siehe Korollar 11.13). Es ist also keineswegs selbstverständlich, dass es ein sinnvolles entscheidbares Ableitungsprädikat gibt.

Allerdings ist ein schwächeres Ableitungsprädikat entscheidbar und damit repräsentierbar, nämlich die folgende zweistellige Ableitungsrelation. Dazu sei die Gödelisierung auf endliche Folgen von Ausdrücken (die mögliche Ableitungsketten repräsentieren möge) ausgedehnt. Wir betrachten dann das zweistellige Prädikat

A\subseteq \mathbb {N} \times \mathbb {N}

(eigentlich $A_{\Gamma }(x,y)$ , da diese Teilmenge von ${}\Gamma$ abhängt), mit der Eigenschaft, dass ${}(m,n)\in A$ genau dann gilt, wenn ${}m$ die Gödelnummer einer korrekten Ableitung im Prädikatenkalkül aus ${}\Gamma$ ist, deren letzter Ausdruck (also der in der Ableitung bewiesene Ausdruck) die Gödelnummer ${}n$ besitzt. Diese Relation ist unter der Voraussetzung, dass ${}\Gamma$ entscheidbar ist, selbst entscheidbar. Man kann ja zum ersten Eintrag ${}m$ die Ableitung rekonstruieren, ihre Korrektheit im Prädikatenkalkül überprüfen und aufgrund der Entscheidbarkeit von ${}\Gamma$ feststellen, ob nur Ausdrücke aus ${}\Gamma$ als Voraussetzungen verwendet wurden. Wenn ${}\Gamma$ Repräsentierungen erlaubt, so gibt es einen arithmetischen Ausdruck mit zwei freien Variablen, sagen wir ${}\delta (x,y)$ (eigentlich $\delta _{\Gamma }(x,y)$ , da dieses Prädikat von ${}\Gamma$ abhängt), der für jede Belegung ${}(m,n)\in \mathbb {N} ^{2}$ genau dann aus ${}\Gamma$ ableitbar ist, wenn ${}m$ einen Beweis für die Aussage zu ${}n$ kodiert.

Wie formuliert man die Eigenschaft, dass es einen prädikatenlogischen Beweis aus

{}\Gamma

für die Aussage zu

{}n

gibt? Innerhalb der natürlichen Zahlen ist dies äquivalent dazu, dass es ein

{}m\in \mathbb {N}

gibt mit

{}A(m,n)

. Dies muss aber nicht äquivalent zu

{}\Gamma \vdash \exists x\delta (x,y)

sein. Wir setzen

\alpha (y)=\exists x\delta (x,y).

Wenn ${}\Gamma$ Repräsentierungen erlaubt, so gibt es aufgrund des Fixpunktsatzes, angewendet auf den negierten Ausdruck ${}\neg \alpha (y)$ , einen Ausdruck ${}q\in L^{\rm {Ar}}$ mit

\Gamma \vdash q\longrightarrow \neg \alpha (GN(q)).

Dieser Satz ${}q$ kann nun aus ${}\Gamma$ nicht ableitbar sein, es sei denn, dass ${}\Gamma$ widersprüchlich ist. Wenn nämlich ${}\Gamma \vdash q$ gilt, so bedeutet dies, dass es eine korrekte Ableitung von ${}q$ aus ${}\Gamma$ gibt. Diese Ableitung wird durch eine Zahl ${}m$ kodiert und daher gilt

\Gamma \vdash \delta (m,GN(q)),

da ja ${}\delta$ das zweistellige Ableitungsprädikat repräsentiert. Daher ist auch

\Gamma \vdash \exists x\delta (x,GN(q)),

also ${}\Gamma \vdash \alpha (GN(q))$ . Die Negation der Fixpunkteigenschaft ergibt somit

\Gamma \vdash \neg q,

so dass ein Widerspruch vorliegt.

Das Beweisprädikat ${}\alpha (y)$ besitzt, zumindest, wenn ${}\Gamma$ die Peano-Arithmetik umfasst, einige ausdruckstarke Eigenschaften, die auch in ${}\Gamma$ ableitbar sind. Der Beweis von diesen Eigenschaften ist aufwändig, da sie nicht abstrakt aus der Repräsentierbarkeit folgen, sondern im Beweiskalkül erarbeitet werden müssen. Wichtige Eigenschaften sind ( ${}\Gamma$ sei entscheidbar und enthalte die Peano-Arithmetik)

Wenn ${}\Gamma \vdash s$ , so ist ${}\Gamma \vdash \alpha (GN(s))$ für jeden Ausdruck ${}s\in L^{\rm {Ar}}$ .

Für je zwei Ausdrücke ${}s,t\in L^{\rm {Ar}}$ ist ${}\Gamma \vdash \alpha (GN(s\rightarrow t))\rightarrow (\alpha (GN(s))\rightarrow \alpha (GN(t)))$ .

Für jeden Ausdruck ${}s\in L^{\rm {Ar}}$ ist ${}\Gamma \vdash \alpha (GN(s))\rightarrow \alpha (GN(\alpha (GN(s))))$ .

Diese und ähnliche Gesetzmäßigkeiten sind der Ausgangspunkt der Beweisbarkeitslogik, die in der Sprache der Modallogik beweistheoretische Fragestellungen untersucht.

Die aufgelisteten Eigenschaften sind für ein Ableitungsprädikat natürlich wünschenswert; der naive Wunsch ${}\vdash s\longleftrightarrow \alpha (GN(s))$ ist nicht realisierbar, da er in Verbindung mit dem Satz ${}q$ von oben (der Fixpunkt zur Negation ${}\neg \alpha (GN(s))$ ) sofort einen internen Widerspruch ergibt. Die Verbindung der „positiven“ Eigenschaften des Ableitungsprädikates mit dem „paradoxen“ ${}q$ aus dem Fixpunktsatz liefert einen Beweis für den zweiten Unvollständigkeitssatz. Dazu braucht man nicht die volle Liste von oben, sondern es genügt zu wissen, dass die weiter oben auf Grundlage der Widerspruchsfreiheit von ${}\Gamma$ gezeigte Unableitbarkeit von ${}q$ aus ${}\Gamma$ sich in der Peano-Arithmetik selbst nachvollziehen lässt. D.h. es gilt

PA\vdash WF(\Gamma )\longrightarrow \neg \alpha (GN(q))

Dabei realisieren wir die Widerspruchsfreiheit ${}WF(\Gamma )$ intern durch die Unableitbarkeit des weiter oben schon erwähnten widersprüchlichen Satzes ${}r=\neg (0=0)$ , also durch