Donnerstag, 30. Mai 2013

Panorama 24. und 27. 5. 2013

Der erste Gödelsche Unvollständigkeitssatz

Alles technische habe ich dem bereits erwähnten Lehrbuch von Rautenberg entnommen.
Eine nicht-technische Darstellung des Beweises findet sich in dem Buch von Franzén, das sich auch mit der Rezeption des Satzes außerhalb der Mathematik beschäftigt.

Wir haben zunächst die Peano-Axiome im Rahmen der Mengenlehre formuliert. Diese beschreiben die natürlichen Zahlen mit der Nachfolgeroperation bis auf Isomorphie eindeutig, was in Aufgabe 21 gezeigt wurde.

Wir haben dann die Peano-Arithmetik als Theorie erster Ordnung (also in der Prädikatenlogik erster Stufe) eingeführt. Diese ist in der Sprache der Arithmetik $\mathcal L_{\mathrm{ar}}$ formuliert, die ein Konstantenymbol $0$ sowie Funktionssymbole $S$ (Nachfolger), $+$ und $\cdot$ enthält. Aus dem Rautenberg:
Peano-Arithmetik PA
Dabei ist zu beachten, dass das Induktionsschema für jede Formel $\varphi$ ein Axiom liefert, das Axiomensystem $\mathrm{PA}$ ist also unendlich. Dennoch lässt sich von einer gegeben Formel „mechanisch“ feststellen, ob sie eines der Axiome von $\mathrm{PA}$ ist, das wird noch wichtig sein.

Das Standardmodell $\mathcal N$ von $\mathrm{PA}$, also in gewisser Hinsicht das beabsichtige Modell, besteht aus der Menge der hatürlichen Zahlen $\mathbb N$ zusammen mit der Null, sowie der üblichen Nachfolgeroperation, Addition und Multiplikation. Da $\mathrm{PA}$ ein Modell hat, haben wir also sofort (mit dem Korrektheitssatz) den

Satz. $PA$ ist konsistent.

Man muss ein wenig arbeiten, um das einzusehen, aber in $\mathrm{PA}$ lassen sich tatsächlich alle elementaren Zahlentheoretischen Beweise durchführen, sowie ein guter Teil der diskreten Mathematk. $\mathrm{PA}$ taugt damit als Repräsentant für finitistische Mathematik.

Für jede natürliche Zahl $n\in\mathbb N$ definieren den die entsprechende Zahl bezeichnenden Term $\underline n:=\underbrace{SS\cdots S}_{n}0$. Als Warnung und im Gegensatz zu Aufgabe 21 weisen wir auf die Existenz von Nichtstandardmodellen hin.

Satz. Es gibt ein Modell $\mathcal M$ von $\mathrm{PA}$, das außer $\left(\underline n\right)^{\mathcal M}$, $n\in\mathbb N$, noch weitere Elemente hat.

Auf den Beweis, der eine leichte Anwendung des Vollständigkeitssatzes ist, haben wir verzichtet. Der Interessierte findet dies als Satz 3.2 bei Rautenberg.

Das Induktionsschema leistet also nicht, was wir vielleicht erwartet hätten. Das mag zunächst verwundern, deutet aber bereits in Richtung des Unvollständigkeitssatzes.

Daraus, dass aber das Standardmodell nur die von $\underline n$ bezeichneten Elemente enthält, erhält man aber folgendes.

Satz/Definition. Es sei $\varphi=\varphi(x)\in\mathcal L_{\mathrm{ar}}$. Gilt $\mathrm{PA}\vdash\exists x\varphi(x)$, so existiert ein $n\in\mathbb N$ mit $\mathrm{PA}\not\vdash\neg\varphi(\underline n)$. Wir sagen, $\mathrm{PA}$ sei $\omega$-konsistent.

Beweis. Sonst gölte $\mathcal N\models\exists x\varphi(x)$, aber $\mathcal N\models\neg\varphi(\underline n)$ für alle $n\in\mathbb N$.

Wir wollen nun als eine Instanz des Gödelschen Unvollständigkeitssatzes skizzieren, dass $\mathrm{PA}$ unvollständig ist, dass also eine Aussage $\gamma\in\mathcal L_{\mathrm{ar}}$ mit $\mathrm{PA}\not\vdash\gamma$ und $\mathrm{PA}\not\vdash\neg\gamma$ existiert. Der Beweis basiert nun darauf, dass der Begriff der Ableitbarkeit in $\mathrm{PA}$ sich arithmetisch (also als Aussage über das Rechnen mit natürlichen Zahlen) formulieren lässt, und dass sich genug Tatsachen darüber in $\mathrm{PA}$ beweisen lassen.

Zunächst führt man ein Schema ein, nachdem man jeder Formel $\gamma$ injektiv eine Gödelnummer $n\in\mathbb N$ zuordnet. Wir schreiben dafür dann $\dot\gamma=n$ und $\lceil\gamma\rceil=\underline n$. Ebenso ordnen wir jeder potentiellen Herleitung einer Formel (man denke an etwas, das aussieht wie die lange Folge von Zeilen in Aufgabe 22. Dieses soll so sein, dass sich auch Formel $bew(n,m)$ angeben lässt, die „sagt“, dass $n$ Gödelnummer eines Beweises einer Formel mit Gödelnummer $m$ ist. Und in der Tat soll sich, wenn das der Fall ist, das auch in $PA$ herleiten lassen. Dies ist zu erreichen, da das Testen, ob etwas eine Herleitung ist, ja tatsächlich rein mechanisch möglich ist (man denke wieder an Aufgabe 22), und wie oben bereits behauptet sich solche Argumente in $\mathrm{PA}$ durchführen lassen. Natürlich wäre hier einiges zu zeigen. Wir können aber genau sagen, was wir erreichen wollen, nämlich, dass für jede jede Formel $\varphi$ die folgenden Implikationen gelten, wobei wir noch $bwb(m):=\exists n\,bew(n,m)$ setzen:\begin{align*}\mathrm{PA}\ \vdash\ \varphi\quad&\Rightarrow\quad\text{Ex. $n\in\mathbb N$ mit $\mathrm{PA}\vdash bew(\underline n,\lceil\varphi\rceil)$}\\&\Rightarrow\quad\mathrm{PA}\vdash bwb(\lceil\varphi\rceil),\\\mathrm{PA}\not\vdash\varphi\quad&\Rightarrow\quad\mathrm{PA}\vdash\neg bew(\underline n,\lceil\varphi\rceil)\text{ f.a. $n\in\mathbb N$}.\end{align*}Nächstes Ziel ist nun, eine Aussage $\gamma$ zu finden, die von sich selber behauptet, nicht in PA beweisbar zu sein. Genauer wollen wir\[\mathrm{PA}\vdash\,\gamma\leftrightarrow\neg bwb(\lceil\gamma\rceil).\]Für eine solche Aussage gilt in der Tat weder $\mathrm{PA}\vdash\gamma$ noch $\mathrm{PA}\vdash\neg\gamma$. Aus ersterem folgte nämlich einerseits aufgrund der Eigenschaft von $\gamma$, dass $\mathrm{PA}\vdash\neg bwb(\lceil\gamma\rceil)$ und andererseits aufgrund einer Eigenschaft von $bwb$, dass $\mathrm{PA}\vdash bwb(\lceil\gamma\rceil)$. Dies widerspräche der Konsistenz von $\mathrm{PA}$. Aus $\mathrm{PA}\not\vdash\gamma$ folgt nun aber nach obigem $\mathrm{PA}\vdash\neg bew(\underline n,\lceil\gamma\rceil)$ für alle $n\in\mathbb N$, was aufgrund der $\omega$-Konsistenz von $\mathrm{PA}$ impliziert, dass $\mathrm{PA}\not\vdash \exists n\,bew(n,\lceil\gamma\rceil)$, also nach Definition von $bwb$ und der Eigenschaft von $\gamma$ auch $\mathrm{PA}\not\vdash\neg\gamma$.

Die Frage ist nun also, wie man an eine solche Aussage $\gamma$ kommt, die etwas über sich selbst behauptet. Gödels Trick benutzt nun textuelle Ersetzung. Später hat Quine folgendes natürlichsprachliche Analogon angegeben:
„ergibt einen unbeweisbaren Satz, wenn man ihm sein Zitat voranstellt.“ ergibt einen unbeweisbaren Satz, wenn man ihm sein Zitat voranstellt.
Dieser Satz sagt von einem anderen, dass er unbeweisbar sei, und dieser andere ist aber gleich ihm selbst. Dabei entspricht das Zitieren mit Anführungszeichen dem Zitieren via Gödelnummer. Auf der technischen Seite zeigt man, dass es man eine Formel $sb(m,n,y)$ konstruieren kann, die sagt, dass $y$ die Gödelnummer der Formel ist, die man erhält, wenn man in der Formel mit Gödelnummer $m$ die Variable $x$ durch $\underline n$ ersetzt, genauer wollen wir für alle Formeln $\varphi=\varphi(x)$ und $n\in\mathbb N$\[PA\,\vdash\,sb(\lceil\varphi\rceil,\underline n,y)\leftrightarrow y=\lceil\gamma(\underline n)\rceil.\]Weiterhin setzt man nun $\beta(z):=\forall y(sb(z,z,y)\rightarrow\neg bwb(y))$ („Die Aussage, die man erhält, wenn man in die Formel mit Gödelnummer z für die Variable x gerade z einsetzt, ist nicht beweisbar“) und $\gamma:=\beta(\lceil\beta\rceil)$. So erhält man in der Tat\begin{align*}\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\forall y(y=\lceil\beta(\lceil\beta\rceil)\rceil\rightarrow\neg bwb(y)),\\\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\neg bwb(\lceil\beta(\lceil\beta\rceil)\rceil),\\\mathrm{PA}\quad&\vdash\quad\gamma\leftrightarrow\neg bwb(\lceil\gamma\rceil).\end{align*}Damit sind wir am Ziel angelangt.

Satz (Gödel). Für obige Aussage $\gamma\in\mathcal L_{\mathrm{ar}}$ gilt $\mathrm{PA}\not\vdash\gamma$ und $\mathrm{PA}\not\vdash\neg\gamma$. PA ist also unvollständig.

Wenn $\gamma$ in PA weder beweisbar noch widerlegbar ist, ist es dann trotzdem sinnvoll zu fragen, ob $\gamma$ wahr ist? In der Tat ist im allgemeinen in der Prädikatenlogik nur sinnvoll von Beweisbarkeit aus einer Formelmenge (wie hier PA) oder Wahrheit in einem Modell zu reden. Nun hat aber PA das Standardmodell $\mathcal N$, und wir können fragen, ob $\gamma$ in diesem erfüllt ist. Der Beweis zeigt, dass das tatsächlich dann der Fall ist, wenn $\gamma$ in PA nicht beweisbar ist.

Bemerkung. Für dieses $\gamma$ gilt $\mathcal N\models\gamma$. In diesem Sinne ist $\gamma$ also wahr.

Damit ist $\mathcal N$ auch Modell von $\mathrm{PA}\cup\{\gamma\}$. Ist diese Formelmenge nun vielleicht vollständig? Immerhin ist $\gamma$ aus ihr ja trivial ableitbar. Sicher ist sie es auch nicht, denn wir können obigen Beweis für sie wiederholen, nur muss $bew$ dann durch eine neue Formel, die die Beweisbarkeit in $\mathrm{PA}\cup\{\gamma\}$ beschreibt, ersetzt werden, und wir erhalten eine neue Aussage $\gamma'$, die in $\mathrm{PA}\cup\{\gamma\}$ weder beweis- noch widerlegbar ist. Allgemeiner könnten wir eine Formelmenge $X\supset\mathrm{PA}$ betrachten und für diese den Beweis durchführen. Es ist dabei lediglich wichtig, dass sich Beweisbarkeit in $X$ auch wieder durch eine Formel ausdrücken lässt. Dies ist gegeben, wenn sich wieder „mechanisch“ überprüfen lässt, ob eine gegebene Formel zu $X$ gehört oder nicht. Wir brauchen zur Formulierung des Ergebnisses daher einen Berechenbarkeitsbegriff, ein ausreichender ist der der rekursiven Aufzählbarkeit. Es gilt dann der folgende

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und $\mathcal N\models X$, so ist $X$ unvollständig.

Man beachte, dass andererseits $X=\{\varphi\in\mathcal L_{\mathrm{ar}}\colon \text{$\varphi$ Aussage, $\mathcal N\models\varphi$}\}$ natürlich vollständig ist. Damit ist diese Menge nicht rekursiv aufzählbar.

Kommentare:

  1. Danke für die Zusammenfassung. Ein inhaltlich bedeutsamer Schreibfehler: bei der Definition von bew steht einmal n statt m. Außerdem gibt es einen MathJax Error in der vorletzten Zeile.

    AntwortenLöschen