Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 23/kontrolle

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 (zu einer Ausdrucksmenge ${}\Gamma$) ${}a(x)$ in einer freien Variablen soll die Eigenschaft haben, dass für jeden Satz ${}s\in L_{0}^{\rm {Ar}}$ die Ableitungsbeziehung ${}\Gamma \vdash s$ genau dann gilt, wenn ${}\Gamma \vdash a(GN(s))$ gilt. Man sagt, dass ${}a(x)$ die Ableitungseigenschaft schwach repräsentiert. Ein solches Ableitungsprädikat muss es im Allgemeinen nicht geben. Anders formuliert bedeutet diese Eigenschaft, dass die einstellige Relation

${}{\left\{n\in \mathbb {N} \mid n{\text{ ist Gödelnummer eines aus }}\Gamma {\text{ ableitbaren Satzes}}\right\}}\subseteq \mathbb {N} \,$

in ${}\Gamma$ schwach repräsentiert wird. Dass diese Teilmenge (stark) repräsentierbar ist, ist, wenn man die Widerspruchsfreiheit von ${}\Gamma$ voraussetzt, stärker. Aus ${}\Gamma \vdash s$ ergibt sich nämlich direkt die Hinrichtung ${}\Gamma \vdash a(GN(s))$, und wenn ${}\Gamma \vdash s$ nicht wahr ist, so bedeutet dies im Falle der Repräsentierbarkeit, dass ${}\Gamma \vdash \neg a(GN(s))$ gilt, woraus bei widerspruchsfreiem ${}\Gamma$ die Nichtableitbarkeit von ${}a(GN(s))$ folgt.

Im folgenden Unvollständigkeitslemma gehört die Existenz eines (schwach) repräsentierenden Ableitungsprädikates zur Voraussetzung.

Lemma Lemma 23.1 ändern

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 22.8 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   Referenznummer erstellen

Was passiert mit den Voraussetzungen in Lemma 23.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.

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 Satz 23.3 ändern

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 21.9 aufzählbar und nach Satz 21.10 auch entscheidbar. Da ${}\Gamma$ Repräsentierungen erlaubt, ist insbesondere ${}\Gamma ^{\vdash }$ repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.

$\Box$

Korollar Referenznummer erstellen

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 23.3 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 23.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_{0}^{\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 21.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ögen) 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 dieser Ausdruck von ${}\Gamma$ abhängt), der für jede Belegung ${}(m,n)\in \mathbb {N} ^{2}$ genau dann aus ${}\Gamma$ ableitbar ist, wenn ${}(m,n)$ zu ${}A$ gehört, wenn also ${}m$ einen Beweis aus ${}\Gamma$ 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? Dies ist äquivalent dazu, dass es ein ${}m\in \mathbb {N}$ gibt, das einen Beweis dafür kodiert, dass es also ein ${}m\in \mathbb {N}$ mit ${}(m,n)\in A$ gibt, was aufgrund der Repräsentierbarkeit wiederum zu ${}\Gamma \vdash \delta (m,n)$ äquivalent ist. Dies impliziert ${}\Gamma \vdash \exists x\delta (x,n)$. Hierbei gilt sogar die Umkehrung, da ${}\Gamma \vdash \exists x\delta (x,n)$ die Gültigkeit ${}\mathbb {N} \vDash \exists x\delta (x,n)$ bedeutet, was die Existenz einer natürlichen Zahl ${}m$ mit ${}\mathbb {N} \vDash \delta (m,n)$ bedeutet. Wäre ${}(m,n)\notin A$, so würde sich über die starke Repräsentierbarkeit ${}\Gamma \vdash \neg \delta (m,n)$ ergeben und damit der Widerspruch ${}\mathbb {N} \vDash \neg \delta (m,n)$.

Wie formuliert man die Eigenschaft, dass es keinen prädikatenlogischen Beweis aus ${}\Gamma$ für die Aussage zu ${}n$ gibt? Innerhalb der natürlichen Zahlen ist dies äquivalent dazu, dass für alle ${}m\in \mathbb {N}$ die Beziehung ${}A(m,n)$ nicht gilt, was wiederum zu

$\mathbb {N} \vDash \forall x\neg \delta (x,n)$

äquivalent ist. Dies muss aber nicht zu ${}\Gamma \vdash \forall x\neg \delta (x,n)$ äquivalent sein.

Definition Referenznummer erstellen

Es sei ${}\Gamma$ eine korrekte aufzählbare arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Es sei ${}\delta _{\Gamma }(x,y)$ der ${}L^{\rm {Ar}}$-Ausdruck, der in ${}\Gamma$ die zweistellige Ableitungsrelation ${}A\subseteq \mathbb {N} ^{2}$ repräsentiert. Dann setzt man

${}\alpha (y)=\exists x(\delta _{\Gamma }(x,y))\,$

und nennt dies das (einstellige) Ableitungsprädikat.

Lemma Lemma 23.6 ändern

Es sei ${}\Gamma$ eine korrekte aufzählbare arithmetische Ausdrucksmenge, die Repräsentierungen erlaube, es sei ${}\alpha (x)$ das zugehörige (einstellige) Ableitungsprädikat und es sei ${}q$ ein Fixpunkt zum negierten Ableitungsprädikat, also

$\Gamma \vdash q\leftrightarrow \neg \alpha (GN(q)).$

Dann ist ${}q$ aus ${}\Gamma$ nicht ableitbar.

Beweis

Wir nehmen ${}\Gamma \vdash q$ an. Dies bedeutet, dass es eine korrekte Ableitung von ${}q$ aus ${}\Gamma$ gibt. Diese Ableitung wird durch eine Zahl ${}m$ kodiert und somit ist ${}(m,GN(q))\in A$. Daher gilt

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

da ja ${}\delta$ das zweistellige Ableitungsprädikat repräsentiert. Aufgrund der Existenzeinführung im Sukzedens ist auch

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

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

$\Gamma \vdash \neg q,$

sodass ein Widerspruch vorliegt.

$\Box$

Bemerkung   Bemerkung 23.7 ändern

Das Beweisprädikat ${}\alpha (y)$ besitzt, 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\leftrightarrow \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 in Lemma 23.6 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

${}WF(\Gamma )=\neg \alpha (GN(r))=\forall x\neg \delta (x,GN(r))\,.$

Die soeben erwähnte Aussage, dass die Widerspruchsfreiheit die Nichtableitbarkeit von ${}q$ impliziert, kann man auch aus den in Bemerkung 23.7 angeführten Eigenschaften des Ableitungsprädikats erhalten, siehe Aufgabe 23.17.

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

Satz

Es sei ${}\Gamma$ eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse.

Dann ist die Widerspruchsfreiheit ${}WF(\Gamma )$ nicht aus ${}\Gamma$ ableitbar, d.h. es ist

$\Gamma \not \vdash WF(\Gamma ).$

Beweis

Es sei ${}q$ ein Fixpunkt zum negierten Ableitungsprädikat. Aus der Annahme ${}\Gamma \vdash WF(\Gamma )$ folgt wegen

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

(was wir allerdings nicht bewiesen haben) direkt

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

Aus der Fixpunkteigenschaft von ${}q$ folgt somit ${}\Gamma \vdash q$, was aber in dem widerspruchsfreien System ${}\Gamma$ nach Lemma 23.6

nicht sein kann.

$\Box$

Fußnoten