TIA: Gödel'scher Unvollständigkeitssatz (Lernziele KE6, 4/4)

Update: inhaltlich (noch) nichts, aber als Aufbau zu KE6 entsprechend verwurstelt.

Alle weiteren Beiträge findet Ihr hier:

• TIA: Rekursive und rekursiv-aufzählbare Mengen (Lernziele KE6, 1/4)
• TIA: Bild- und Projektionssatz (Lernziele KE6 2/4)
• TIA: Halte- Äquivalenz- und Korrektheitsproblem, Reduzierbarkeit, Satz von Rice (Lernziele KE6, 3/4)
• TIA: Gödel'scher Unvollständigkeitssatz (Lernziele KE6, 4/4)

Zwar sind dem Thema im Skript knapp vier Seiten gewidmet, ich finde aber dieser Satz hat einen eigenen Betrag verdient um nicht in den Lernzielen einfach so unterzugehen. Zunächst: was ist ein Beweissystem? Ein Beweissystem besteht aus Axiomen (Menge von Wörtern) und Schlussregeln, so dass man aus den Axiomen immer neue Wörter (Sätze) ableiten kann.

Ein Beispiel davon ist die Peano Arithmentik. Axiome sind in der Regel selbstverständlich und bedürfen keiner weiteren Begründung. Vor allem in der Peano Arithmetik (PA) sind diese aufgrund ihrer Einfachheit sofort einleuchtend (was diese Arithmetik vor dem 2. Unvollständigkeitssatz von Gödel rettet, aber dazu gleich mehr). Wir können aus diesen unsere Beweise ableiten.

Peano Axiome

Es gibt 5 Peano Axiome, die für sich genommen -wie gesagt- selbstverständlich sind:

1. $1$ ist eine natürliche Zahl

2. Jede natürliche Zahl $n$ hat genau einen Nachfolger $succ(n)$

3. $1$ ist kein Nachfolger einer natürlichen Zahl

4. Die Nachfolger zweier verschiedener natürlicher Zahlen sind verschieden

5. Enthält eine Teilmenge $M \subseteq \mathbb{n}$ die Zahl $1$ und zu jedem Element $n$ auch ihren Nachfolger $succ(n)$, so gilt $M = \mathbb{n}$.

Schlussregeln

Zu den Axiomen benötigen wir auch noch die Schlussregeln. Diese sind:

1. Modus ponens: $A , (A\Rightarrow B) \vdash B$. Wenn aus der Wahrheit von $A$ $B$ folgt und $A$ liegt vor, so gilt auch $B$.

2. Generalisierung: $A \Rightarrow C(x) \vdash A \Rightarrow\forall x_i C(x_i)$. Wenn aus $A$ folgt, dass $C$ für ein beliebiges $x$, dann gilt das auch für alle $x$.

Aus diesen Axiomen und Schlussregeln lassen sich dann Beweise und Operationen ableiten.

Beispiel: Addition $n+1$

Die Addition von $1$ zu einem Wert $n$ ist in der Peano Arithmetik nichts weiter als unsere Nachfolgefunktion: $n+1 = Succ(n)$.

Beispiel: Addition $m+n$, $n=4, m=5$

Auch das können wir uns mit den Peano Axiomen problemlos herleiten, der Ansatz ist aber rekursiver Natur: $(n+Succ(m)) = Succ(n+m)$

$\begin{array}{lcl}4+5&=&Suc(4+4)&\mbox{rekursiv}\\{4+4}&=&Suc(4+3)&\mbox{rekursiv}\\{4+3}&=&Suc(4+2)&\mbox{rekursiv}\\{4+2}&=&Suc(4+1)&\mbox{rekursiv}\\{4+1}&=&Suc(4)&\mbox{dank oben bewiesener Addition von } n+1\\{Suc(4)}&=&5&\mbox{Teilergebnis der letzten rekursion}\end{array}$

Nun setzen wir das rückwärts ein. Denn $4+1 = Suc(4) = 5$. Dass wissen wir ja, da wir das im vorherigen Beispiel bewiesen haben. Also können wir die $4+1$ durch $Suc(4) = 5$ oben in $Suc(4+1)$ ersetzen. Das führen wir dann weiter so fort. Unsere Gleichung sieht am Ende also so aus:

$4+5 = Suc(Suc(Suc(Suc(Suc(4)))))$

Das aufgelöst ergibt offensichtlich (das wollte ich immer schon einmal sagen):

$4+5 = Suc(8) = 9$.

Zusammenhang zum Unvollständigkeitssatz

Nun stellen sich bei so einem Beweissystem ja zwangsläufig folgende Fragen:

1. Widerspruchsfreiheit des Systems: ist es unmöglich einen Widerspruch abzuleiten?

2. Vollständigkeit des Systems: kann jeder wahre Satz der Zahlentheorie abgeleitet werden?

Das damals betrachtete System war die Principia Mathematica von Russel und Whitehead. Hilbert hatte den Wunsch diese beiden Punkte in diesem System zu beweisen. Dass dieser Wunsch nur ein Wunsch bleibt, bewies Hr. Gödel 1931 in seinem Unvollständigkeitssatz, einem der wichtigsten Sätze der Mathematik.

Wir definieren wieder zunächst den Unvollständigkeitssatz wortgetreu aus dem Skript:

1. Kein Beweissystem $V_i$ ist $n$-korrekt und $n$-vollständig.

2. Es gibt eine berechenbare Funktion $h:\subseteq \mathbb{N} \Rightarrow \mathbb{N}$, so dass für jedes $n$-korrekte Beweissystem $V_i$ gilt: $h(i) \notin K_\varphi$ und $"1^{h(i)} \notin K_\varphi" \notin V_i$.

Was bedeutet $n$-korrekt? $n$-korrekt heißt soviel wie, dass wenn der Satz "Eine Maschine mit der Gödelnummer $1 ^n$ auf sich selbst angewendet hält nicht, die Nummer liegt also nicht in $K_\varphi$" sich in dem Beweissystem $V_i$ befindet und wahr ist,  das auch wirklich stimmt. Die Möglichkeit unwahre Sätze in unserem Beweissystem zu haben, wäre ja nicht unbedingt Sinn der Sache.

Was heißt nun $n$-vollständig? $n$-vollständig bedeutet, dass wenn sich $n$ wirklich nicht in $K_\varphi$ befindet, wir den Satz "Eine Maschine mit der Gödelnummer $1 ^n$ auf sich selbst angewendet hält nicht, die Nummer liegt also nicht in $K_\varphi$" in unserem Beweissystem haben. Also genau die umgekehrte Richtung.

Dass beides gilt, wäre unsere Wunschvorstellung für unser Beweissystem. Durch die Codierung der Sätze mittels $1^n$ können zudem nun auch unsere Turingmaschinen drauf arbeiten und uns sagen ob sich ein Beweis $\omega$ in einem Satz $v$ unseres Beweissystems wiederfinden kann oder nicht. Man kann somit entscheiden ob ein Wort $\omega$ ein beweis eines Satzes $v$ ist oder nicht.

Damit gibt es auch eine Turing-Maschine, die das entscheiden kann. Die Kontrolle erfolgt rein syntaktisch, da hier die Bedeutung keine Rolle spielt. Formal ausgedrückt wird gefordert:

$U_X := \{(v,w) \in \Sigma^* \times \Sigma^*\mid \omega$ ist ein Beweis für den Satz $v\}$ ist rekursiv.

Damit ist mit dem Projektionssatz die Menge der im System $X$ beweisbaren Sätze $T_X$ rekursiv aufzählbar:

$T_X := \{v \in \Sigma^* \mid (\exists \omega)(v,\omega) \in U_X$\} ist rekursiv aufzählbar.

Was hat uns nun Gödel mit seinem Unvollständigkeitssatz zu dem ganzen Thema genau gesagt? Er hat uns den mathematischen Stinkefinger gezeigt. Ich bringe die umgangssprachliche Formulierung mit der Wortwahl im Skript in Verbindung um es deutlicher zu machen:

1. Jedes Beweissystem ist widersprüchlich oder unvollständig (umgangssprachlich) $\Rightarrow$ Kein Beweissystem $V_i$ ist $n$-korrekt und $n$-vollständig (Skript)

2. Jedes konsistente Beweissystem kann die eigene Konsistenz nicht beweisen (umgangssprachlich) $\Rightarrow$ Es gibt eine berechenbare Funktion $h:\subseteq \mathbb{N} \Rightarrow \mathbb{N}$, so dass für jedes $n$-korrekte Beweissystem $V_i$ gilt: $h(i) \notin K_\varphi$ und $"1^{h(i)} \notin K_\varphi" \notin V_i$

Wie beweisen wir Punkt 1? Angelehnt an den Artikel aus der Wikipedia zum Thema folgt nun die Skizzierung der Beweise beider Sätze.

Beweisidee zur Widersprüchlichkeit/Unvollständigkeit:

Wenn ein Beweissystem also nicht Widersprüchlich ist (es ist konsistent), dann ist es unvollständig. 

Um die Idee nachzuvollziehen, kann man Parallelen zum Paradox des Lügners ziehen. Aber fangen wir mal an:

a) Jedem Satz im System wird eine Gödelnummer zugeordnet, ähnlich unserer Nummerierung in $P^{(1)}$. Diese repräsentiert einen Satz. Aus der Gödelnummer lässt sich auch der Satz wieder ableiten.

b) Konstruktion der Formel $Beweis(x,y)$ (seht Ihr den Zusammenhang mit der oberen Menge $U_x$?). Diese Formel ist dann wahr wenn $x$ die Gödelnummer des Beweises von $S$ ist und $y$ Gödelnummer des Satzes $S$ ist. Damit ist entweder $Beweis(x,y)$ ($x$ ist ein Beweis von $y$)  oder seine Negation $\neg(Beweis(x,y))$ ($x$ ist kein Beweis von $y$) wahr.

c) Konstruktion der Formel $Beweisbar(y) = \exists x(Beweis(x,y)$ (es gibt ein $x$, welches ein Beweis von $y$ ist, damit ist $y$ beweisbar). Die Formel "$y$ ist beweisbar" ist also entweder wahr oder nicht.

d) Anwendung des Diagonallemmas (das arithmetische Konstrukt für die Selbstreferenz) für der Aussage "Ich habe die Eigenschaft F", wobei man für $F$ die Negation von $Beweisbar(y)$, nämlich $\neg(Beweisbar(y))$ einsetzt. Damit bekommt man die Aussage: "Meine Gödelnummer ist die Gödelnummer einer unbeweisbaren Formel" bzw. "Ich bin nicht beweisbar". Das ist der sogenannte Gödelsatz.

Wir sehen schon, wo das hinführt. Nehmen wir an, $y$ sei die gerade konstruierte Aussage "Ich bin nicht beweisbar". Wenn die Aussage beweisbar wäre, so wäre $Beweisbar(y)$ beweisbar. Gleichzeitig ist die Aussage $Beweisbar(y)$ jedoch auch die Negation von sich selbst. Diese Aussage ist also nicht entscheidbar und das Beweissystem  damit oder unvollständig oder widersprüchlich. Widerspruchsfreiheit bedeutet nämlich, dass für einen im System ableitbaren Satz seine Negation nicht ableitbar ist.

Beweisidee zur eigenen Inkonsistenz:

Wenn das Beweissystem konsistent ist, dann ist der Beweis der Konsistenz nicht innerhalb des Systems zu erbringen.

Für den 2. Satz über die Inkonsistenz eines Systems benutzt Gödel seinen ersten Satz und zeigt, dass ein System seine eigene Konsistenz nicht beweisen kann. Das geht wie folgt:

a) da das System lt. dem ersten Unvollständigkeitssatz den Gödelsatz $Gs$ "Ich bin nicht beweisbar" nicht beweisen kann, ist dieser wahr.

b) daraus lässt sich ableiten: $Konsistent(V) \Rightarrow Gs$. Da dieser Satz aber ebenfalls seine Negation ist, wird das System $V$ dadurch inkonsistent.

Konsistenz schließt Widersprüchlichkeit aus, d.h. wir brauchen ein System, wo wir unser konstruiertes $Beweisbar(y)$ von oben nicht beweisen können. Da $Beweisbar(y)$ ja auch die eigene Negation ist, stecken wir  wieder bei seinem Beweis in der Klemme und können die Konsistenz eines Systems (mit den mitteln des Systems) nicht beweisen. Der zweite Unvollständigkeitssatz kann also nur dazu genutzt werden die Widersprüchlichkeit, aber nicht die Widerspruchsfreiheit zu belegen.

Im Endeffekt bedeutet es für uns, dass wir mit den Möglichkeiten eines Systems die Konsistenz dieses Systems nicht darstellen können. Die Frage ist hier: und wozu taugen diese Systeme nun? Wir können mit den Mitteln der Peano Arithmetik (oder eines ausdrucksschwächeren Systems) nicht beweisen, dass die Peano Arithmetik konsistent ist. Obwohl das vielleicht erschreckend klingt, ist es nicht so tragisch wie es sich anhört. Den wir wissen anhand der beiden Sätze, dass die Peano Arithmetik vielleicht unvollständig ist, sie ist aber dennoch durch sich selbst unbewiesen widerspruchsfrei. Warum wird das ohne einen konkreten Beweis akzeptiert? Die Axiome der PA sind zu einfach zu einfach, als dass man sie in Frage stellen könnte.

Das ganze schießt aber nicht aus, dass die Widerspruchsfreiheit eines Systems von einem ausdrucksstärkeren System bewiesen werden könnte. Z.B. würde die Widerspruchsfreiheit von PA innerhalb von ZF-Mengenlehre gezeigt werden können. Was Gerhard Gentzen 1936 auch getan hat, indem er die Hilfe der transfiniten Induktion in Anspruch nahm.

Ein Resultat daraus war, dass man z.B. den Satz von Goodstein in PA zwar formulieren, aber mit den Mitteln der Peano Arithmetik nicht beweisen kann, was Kriby und Paris 1982 zeigten.

Damit haben wir mit der Peano Arithmetik ein widerspruchsfreies, aber unvollständiges System. Womit wir anscheinend ganz gut leben können.

Bei Fehlern: per Mail oder in die Kommentare. Je schneller die aus den Beiträgen raus sind, desto weniger Schaden richten sie evtl. an. Ein Danke auch wieder an die NG vom WS12/13 mit den vielen konstruktiven Beiträgen.

Nun könnt Ihr zurück zum Beitrag 3/4 und die formulierte Antwort zum Lernziel sicher etwas besser nachvollziehen.

Datum: 10. Dezember 2012
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url