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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



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 soll die Eigenschaft haben, dass genau dann gilt, wenn 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 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 12.7 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  

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

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 11.9 aufzählbar und nach Satz 11.10 auch entscheidbar. Da Repräsentierungen erlaubt, ist insbesondere repräsentierbar. Daher sind die Voraussetzungen von Lemma 13.1 erfüllt und es ergibt sich ein Widerspruch zur angenommenen Vollständigkeit.




Korollar  

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 13.2 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 13.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 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

(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 dieses Prädikat von abhängt), der für jede Belegung genau dann aus ableitbar ist, wenn einen Beweis für die Aussage zu kodiert.

Wie formuliert man die Eigenschaft, dass es einen prädikatenlogischen Beweis aus für die Aussage zu gibt? Innerhalb der natürlichen Zahlen ist dies äquivalent dazu, dass es ein gibt mit . Dies muss aber nicht äquivalent zu sein. Wir setzen

Wenn Repräsentierungen erlaubt, so gibt es aufgrund des Fixpunktsatzes, angewendet auf den negierten Ausdruck , einen Ausdruck mit

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

da ja das zweistellige Ableitungsprädikat repräsentiert. Daher ist auch

also . Die Negation der Fixpunkteigenschaft ergibt somit

so dass ein Widerspruch vorliegt.

Das Beweisprädikat besitzt, zumindest, 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 weiter oben 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



Satz

Es sei eine arithmetische Ausdrucksmenge, die widerspruchsfrei und entscheidbar sei und die Peano-Arithmetik umfasse.

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

Beweis

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 obiger Überlegung nicht sein kann.



<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)