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

Aus Wikiversity



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 ) in einer freien Variablen soll die Eigenschaft haben, dass für jeden Satz die Ableitungsbeziehung genau dann gilt, wenn gilt. Man sagt, dass die Ableitungseigenschaft schwach repräsentiert. Ein solches Ableitungsprädikat muss es im Allgemeinen nicht geben. Anders formuliert bedeutet diese Eigenschaft, dass die einstellige Relation

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

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



Lemma  Lemma 23.1 ändern

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

Dann gibt es einen arithmetischen Satz derart, dass weder noch seine Negation aus ableitbar ist.

Die Ableitungsmenge ist also nicht vollständig.

Beweis  

Aus der Repräsentierbarkeit von folgt, dass es einen arithmetischen Ausdruck in einer freien Variablen gibt, sagen wir , mit der Eigenschaft, dass

genau dann gilt, wenn

gilt. Wir betrachten die Negation . Nach Satz 22.8 gibt es für einen Fixpunkt, also einen Satz mit

bzw.

Sowohl aus als auch aus ergibt sich dann direkt ein ableitbarer Widerspruch, was der Widerspruchsfreiheit des Systems widerspricht.


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 selbst oder rekursiv ist.

Bemerkung   Referenznummer erstellen

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


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


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


Satz  Satz 23.3 ändern

Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und aufzählbar sei und Repräsentierungen erlaube.

Dann ist unvollständig.

Es gibt also einen arithmetischen Satz, für den weder noch gilt.

Beweis  

 Wir nehmen an, dass vollständig ist. Da aufzählbar ist, ist nach Lemma 21.9 aufzählbar und nach Satz 21.10 auch entscheidbar. Da Repräsentierungen erlaubt, ist insbesondere repräsentierbar. Daher sind die Voraussetzungen von Lemma 23.1 erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.



Korollar  Referenznummer erstellen

Es sei eine arithmetische korrekte Ausdrucksmenge, die aufzählbar sei und Repräsentierungen erlaube.

Dann gibt es einen in (der Standardinterpretation) wahren Satz, der nicht zu gehört, der also nicht aus formal ableitbar ist.

Beweis  

Die Korrektheit bedeutet, dass gilt. Dies sichert zugleich die Widerspruchsfreiheit von . Gemäß Satz 23.3 gibt es einen Satz , der weder selbst noch seine Negation aus ableitbar ist. Da aber vollständig ist, muss entweder oder in wahr sein.


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 repräsentierbar ist und der zugehörige repräsentierende arithmetische Ausdruck bekannt ist, so ist auch der im Beweis zu Lemma 23.1 verwendete Ausdruck , (also der Fixpunkt zu ) prinzipiell bekannt, da der Fixpunktsatz konstruktiv ist. Im Beweis des ersten Gödelschen Unvollständigkeitssatz war ein solches Ableitungsprädikat 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 , also eine deduktiv abgeschlossene Satzmenge, die bei der Standardinterpretation in nur wahre Sätze ergibt (dazu genügt es wegen der Korrektheit des Ableitungskalküls, dass sämtliche Sätze aus einem Axiomensystem für (also ) in wahr sind). Da , wie jede Gültigkeitsmenge eines Modells, vollständig und widerspruchsfrei ist, ist auch (als Teilmenge von ) widerspruchsfrei. Daher gehört zu kein Satz der Form und auch nicht der Satz (da ja die Identität 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 vor. Dieses hatte die Eigenschaft

allerdings unter der Bedingung, dass entscheidbar und damit in (das Repräsentierungen erlaube) repräsentierbar ist. Aus der Entscheidbarkeit von folgt zwar die Aufzählbarkeit von , und daraus, wenn zusätzlich vollständig ist, auch die Entscheidbarkeit von , 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 (eigentlich , da diese Teilmenge von abhängt), mit der Eigenschaft, dass genau dann gilt, wenn die Gödelnummer einer korrekten Ableitung im Prädikatenkalkül aus ist, deren letzter Ausdruck (also der in der Ableitung bewiesene Ausdruck) die Gödelnummer besitzt. Diese Relation ist unter der Voraussetzung, dass entscheidbar ist, selbst entscheidbar. Man kann ja zum ersten Eintrag die Ableitung rekonstruieren, ihre Korrektheit im Prädikatenkalkül überprüfen und aufgrund der Entscheidbarkeit von feststellen, ob nur Ausdrücke aus als Voraussetzungen verwendet wurden. Wenn Repräsentierungen erlaubt, so gibt es einen arithmetischen Ausdruck mit zwei freien Variablen, sagen wir (eigentlich , da dieser Ausdruck von abhängt), der für jede Belegung genau dann aus ableitbar ist, wenn zu gehört, wenn also einen Beweis aus für die Aussage zu kodiert.

Wie formuliert man die Eigenschaft, dass es einen prädikatenlogischen Beweis aus für die Aussage zu gibt? Dies ist äquivalent dazu, dass es ein gibt, das einen Beweis dafür kodiert, dass es also ein mit gibt, was aufgrund der Repräsentierbarkeit wiederum zu äquivalent ist. Dies impliziert . Hierbei gilt sogar die Umkehrung, da die Gültigkeit bedeutet, was die Existenz einer natürlichen Zahl mit bedeutet. Wäre , so würde sich über die starke Repräsentierbarkeit ergeben und damit der Widerspruch .

Wie formuliert man die Eigenschaft, dass es keinen prädikatenlogischen Beweis aus für die Aussage zu gibt? Innerhalb der natürlichen Zahlen ist dies äquivalent dazu, dass für alle die Beziehung nicht gilt, was wiederum zu

äquivalent ist. Dies muss aber nicht zu äquivalent sein.


Definition  Referenznummer erstellen

Es sei eine korrekte aufzählbare arithmetische Ausdrucksmenge, die Repräsentierungen erlaube. Es sei der -Ausdruck, der in die zweistellige Ableitungsrelation repräsentiert. Dann setzt man

und nennt dies das (einstellige) Ableitungsprädikat.



Lemma  Lemma 23.6 ändern

Es sei eine korrekte aufzählbare arithmetische Ausdrucksmenge, die Repräsentierungen erlaube, es sei das zugehörige (einstellige) Ableitungsprädikat und es sei ein Fixpunkt zum negierten Ableitungsprädikat, also

Dann ist aus nicht ableitbar.

Beweis  

Wir nehmen an. Dies bedeutet, dass es eine korrekte Ableitung von aus gibt. Diese Ableitung wird durch eine Zahl kodiert und somit ist . Daher gilt

da ja das zweistellige Ableitungsprädikat repräsentiert. Aufgrund der Existenzeinführung im Sukzedens ist auch

also . Die Kontraposition der Fixpunkteigenschaft ergibt somit

so dass ein Widerspruch vorliegt.


Bemerkung   Bemerkung 23.7 ändern

Das Beweisprädikat besitzt, wenn die Peano-Arithmetik umfasst, einige ausdruckstarke Eigenschaften, die auch in 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 ( sei entscheidbar und enthalte die Peano-Arithmetik).

    • Wenn , so ist für jeden Ausdruck .
    • Für je zwei Ausdrücke ist .
    • Für jeden Ausdruck ist .


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 ist nicht realisierbar, da er in Verbindung mit dem Satz von oben (der Fixpunkt zur Negation ) sofort einen internen Widerspruch ergibt. Die Verbindung der „positiven“ Eigenschaften des Ableitungsprädikates mit dem „paradoxen“ 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 gezeigte Unableitbarkeit von aus sich in der Peano-Arithmetik selbst nachvollziehen lässt. D.h. es gilt

Dabei realisieren wir die Widerspruchsfreiheit intern durch die Unableitbarkeit des weiter oben schon erwähnten widersprüchlichen Satzes , also durch

Die soeben erwähnte Aussage, dass die Widerspruchsfreiheit die Nichtableitbarkeit von 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 eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei[1] und die Peano-Arithmetik umfasse.

Dann ist die Widerspruchsfreiheit nicht aus ableitbar, d.h. es ist

Beweis

Es sei ein Fixpunkt zum negierten Ableitungsprädikat. Aus der Annahme folgt wegen

(was wir allerdings nicht bewiesen haben) direkt

Aus der Fixpunkteigenschaft von folgt somit , was aber in dem widerspruchsfreien System nach Lemma 23.6

nicht sein kann.




Fußnoten
  1. D.h. ist entscheidbar, die Ableitungsmenge muss nicht entscheidbar sein.