Donnerstag, 20. Juni 2013

Panorama 17. 6. 2013

Noch einmal eine Zusammenfassung des Teils dieser Sitzung, der der Wiederholung und Diskussion der Gödelschen Unvollständigkeitssätze gewidmet war. Dies enthält nun wieder ein paar Feinheiten, die das ganze vielleicht schwieriger erscheinen lassen als es ist. Außer allen Sätzen sind vor allem die Teile in Fettdruck wichtig.

Wir haben uns noch einmal mit den Gödelschen Unvollständigkeitssätzen beschäftigt. Die einfachste Form, die wir formuliert hatten, war:

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

Dabei ist $X$ eine Menge von Aussagen in der Sprache der Arithmetik. Nun ist eine solche Aussage zunächst ein rein syntaktisches Gebilde, es ist erst nach Interpretation der Aussage sinnvoll, davon zu reden, ob sie wahr oder falsch ist. Aussagen in der Sprache der Arithmetik können wir aber immer als Aussagen über natürliche Zahlen interpretieren und damit wahr oder falsch nennen. Wenn wir $\mathcal N\models X$ schreiben, so heißt dies gerade, dass alle Aussagen aus $X$ so interpretiert wahr sind. Wenn wir das so verstehen, können wir auch schreiben:

Satz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und enthält $X$ nur wahre Aussagen, so existiert eine wahre Aussage, die sich nicht aus $X$ ableiten lässt.

Der Beweis hiervon lässt sich einfacher skizzieren als ich das in einer früheren Sitzung getan hatte: Es ist möglich, eine Aussage $\gamma$ zu konstruieren, die gerade sagt, dass $\gamma$ nicht aus $X$ ableitbar ist. Wäre $\gamma$ falsch, so ließe sich $\gamma$ also ableiten, es ließe sich aus $X$ also eine falsche Aussage ableiten, was im Widerspruch dazu steht, dass $X$ nur wahre Aussagen enthält. Damit ist $\gamma$ also wahr und nicht aus $X$ ableitbar.

Eigentlich möchte man aber nicht nur über Mengen wahrer Aussagen sprechen. Redet man vom ersten Gödelschen Unvollständigkeitssatz meint man meist eine Form des folgenden, auch wenn dies eigentlich eine Verstärkung des Satzes durch Rosser ist.

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

Es gibt also eine Aussage, so dass weder diese Aussage noch ihre Negation aus $X$ ableitbar sind. Aber Achtung: Dies muss nicht auf unsere oben konstruierte Aussage $\gamma$ zutreffen, Rossers Konstruktion ist eine andere. Wer in einer populären Darstellung also diese starke Fassung formuliert, dann aber zum Beweis einen Satz der Art „ich bin nicht beweisbar“ vorbringt, der schummelt.

Durchaus aber folgt für die Aussage $\gamma$ von oben, dass $X$ inkonsistent ist, wenn $\gamma$ aus $X$ ableitbar ist. (Wenn $\gamma$ aus $X$ ableitbar ist, so ist diese Tatsache auch in $X$ beweisbar, das heißt $\neg\gamma$ ist aus $X$ ableitbar.)  Das heißt aber, dass $X$ genau dann konsistent ist, wenn $\gamma$ nicht aus $X$ ableitbar ist, was wiederum die Aussage von $\gamma$ ist. Die Grundlage des Beweises des zweiten Gödelschen Unvollständigkeitssatzes ist nun, dass sich die Äquivalenz von $\gamma$ und $Con_X$ (der Konsistenz von $X$) auch in $X$ beweisen lässt. Dies liefert:

Zweiter Gödelscher Unvollständigkeitssatz. Ist $X\supset\mathrm{PA}$ rekursiv aufzählbar und konsistent, so ist $Con_X$ nicht aus $X$ ableitbar.

Betrachten wir ein Beispiel: PA selbst ist konsistent. Dies liegt daran, dass PA ein Modell hat, nämlich das Standardmodell $\mathcal N$. Kurz: PA enthält nur wahre Aussagen. (Dies ist ein Beweis der Konsistenz von PA, den wir in „unserer Mathematik“ geführt haben, in der es ja die Menge der natürlichen Zahlen gibt. Dies ist also ein Beweis der Konsistenz von PA in ZF. Keine Unvollstänidgkeitssätze wurden verletzt.) Also ist $Con_{\mathrm{PA}}$ nicht in PA beweisbar. Das heißt aber, dass $X:=\mathrm{PA} + \neg Con_{\mathrm{PA}}$ konsistent ist. (Wäre $X$ inkonsistent, so ließe sich aus $\mathrm{PA} + \neg Con_{\mathrm{PA}}$ ein Widerspruch herleiten, die Aussage $Con_{\mathrm{PA}}$ wäre also in PA per Widerspruch beweisbar.) $X$ ist also eine konsistente Theorie, die eine falsche Aussage enthält (wobei falsch wie gesagt nur bedeutet, dass sie im Standardmodell $\mathcal N$ nicht gilt). Wir wissen insbesondere, dass auch $X$ unvollständig ist. Aber: Ist $\gamma$ die Aussage, die behauptet, dass $\gamma$ in $X$ nicht beweisbar ist, so ist $\gamma$ wie gehabt äquivalent zu $Con_X$. Da $Con_X$ aber $Con_{\mathrm PA}$ impliziert, ist $\neg\gamma$ aus $X$ ableitbar. $X$ ist also konsistent, behauptet aber seine eigene Inkonsistenz.

All das gilt wie schon früher bemerkt nicht nur für die Sprache der Arithmetik und PA, sondern wo immer man genug Mathematik nachbilden kann, um sinnvoll über Beweisbarkeit zu reden. Insbesondere gilt das für die Sprache der Mengenlehre und ZF, also:

Satz.  Ist $X\supset\mathrm{ZF}$ rekursiv aufzählbar und konsistent, so ist $X$ unvollständig und $Con_X$ nicht aus $X$ ableitbar.

Wir müssen hier nur aufpassen: Im Gegensatz zu der Situation bei PA dürfen wir hier nicht einfach „in ZF lässt sich die Konsistenz von ZF nicht beweisen“ behaupten. Dass es überhaupt eine Aussage gibt, die sich in ZF nicht beweisen lässt, heißt ja, dass ZF konsistent ist. Hätten wir tatsächlich einen Beweis dieser Tatsache, den wir in unserer üblichen Mathematik, also in ZFC, geführt hätten, so würde also ZFC die Konsistenz von ZF beweisen. Von Gödel wissen wir aber (das wurde in einer früheren Sitzung berichtet), dass wenn ZF konsistent ist, auch ZFC konsistent ist. ZFC würde also seine eigene Konsistenz beweisen, was nach dem zweiten Gödelschen Unvollständigkeitssatz nur möglich ist, wenn ZFC inkonsistent ist, was wir doch nicht hoffen wollen. Wir müssen also genau sein und sagen: „Wenn ZF konsistent ist, lässst sich in ZF die Konsistenz von ZF nicht beweisen.“

Keine Kommentare:

Kommentar veröffentlichen