Gödels erster Unvollständigkeitssatz
Ich bin nicht beweisbar
Eine unbeweisbare Aussage
Auch das Gegenteil ist nicht beweisbar
Im letzten Kapitel haben die folgenden beiden Ergebnisse für die Peano-Arithmetik (und generell für jedes formale System, in dem das Representation Theorem gilt, d.h. das mächtig genug ist, alle berechenbaren Funktionen darzustellen) bewiesen:
Wäre die Peano-Arithmetik widerspruchsfrei und vollständig, so hätte sie aber ein Entscheidungsverfahren. Also folgt sofort:
Es gibt also wohlgeformte Aussagen über natürliche Zahlen, die sich aufgrund der Axiome weder beweisen noch wiederlegen lassen. Hilberts Vision ist nicht durchführbar!
Wir hatten im letzten Kapitel diese Ergebnisse durch einen Widerspruchsbeweis bewiesen: Die Annahme, dass ein Entscheidungsverfahren existiert, führte zu einem Widerspruch. Diese Beweisidee stammt von Alan Turing aus dem Jahr 1936.
Gödel verwendete im Jahr 1931 (also fünf Jahre zuvor) eine andere Methode, um seinen ersten Unvollständigkeitssatz zu beweisen. Er konstruierte explizit eine wohlgeformte Aussage (nennen wir sie ihm zu Ehren \(G\) ), die nicht beweisbar sein kann, wenn die Peano-Arithmetik widerspruchsfrei ist, und deren Gegenteil \( \neg G \) ebenfalls nicht beweisbar ist.
Gödels Beweis lässt die Frage offen, ob es ein Entscheidungsverfahren gibt – er zeigt nur, dass sich nicht alle Aussagen aus den Axiomen ableiten bzw. wiederlegen lassen. Es wäre also immer noch denkbar gewesen, dass sich die Beweisbarkeit einer Aussage generell entscheiden lässt. Diese Frage hat erst Turing 1936 geklärt. Insofern geht der Beweis, den wir im letzten Kapitel kennengelernt haben, über Gödels Beweis hinaus, denn er zeigt, dass sich die Beweisbarkeit einer Aussage nicht durch ein allgemeines Verfahren immer generell entscheiden lässt. Es gibt kein Entscheidungsverfahren.
Andererseits ist Gödels Beweis konkreter als Turings Methode, denn er zeigt nicht nur, dass eine widerspruchsfreie Peano-Arithmetik unvollständig ist, sondern er konstruiert eine konkrete Aussage, die nicht beweisbar und nicht widerlegbar ist. Wir wollen uns daher diese Aussage und Gödels Beweis im Folgenden genauer ansehen.
Eine der wesentlichen Ideen für die Konstruktion der Aussage \(G\) besteht darin, Aussagen und natürliche Zahlen miteinander in Beziehung zu setzen. Aussagen über Zahlen können dann als Aussagen über andere Aussagen gewertet werden, so dass innerhalb der Peano-Arithmetik etwas über die Peano-Arithmetik gesagt werden kann.
Es gibt sehr viele Möglichkeiten, Aussagen eindeutig durch natürliche Zahlen zu charakterisieren. Beispielsweise kann man einfach die ASCII-Codes der Zeichen in der Aussagen-Zeichenkette hintereinanderhängen und so jeder Aussage eine eindeutige natürliche Zahl zuordnen.
Eine andere Möglichkeit kennen wir bereits: Wir wissen, dass man eine vollständige Liste aller wohlgeformten Aussagen \( A_k \) aufstellen kann. Der Algorithmus zum Aufstellen dieser Liste ordnet dabei jeder Aussage \( A_k \) eine natürliche Zahl \(k\) (die Zeilennummer in der Liste) zu.
Zu Ehren Gödels bezeichnet man eine eindeutig der Aussage zugeordnete natürliche Zahl als Gödelnummer der Aussage. Wir können uns diese Gödelnummer immer als die Zeilennummer vorstellen, in der die betrachtete Aussage in der Liste aller wohlgeformten Aussagen steht.
Betrachten wir nun eine wohlgeformte Aussage mit einer freien Variablen – nennen wir sie \( A_k(x) \). Der Index \(k\) deutet dabei an, dass es sich um die \(k\)-te Aussage in der Liste aller wohlgeformten Aussagen mit einer freien Variablen handelt. Entsprechend wählen wir den Index \(k\) als Gödelnummer der Aussage.
Wir interessieren uns nun für das Diagonalelement \( A_k(k) \), d.h. wir ersetzen die freie Variable \(x\) in der Aussage \( A_k(x) \) durch die Gödelnummer dieser Aussage. Im folgenden werden wir daher \( A_k(k) \) als das Diagonalelement zur Aussage \( A_k(x) \) bezeichnen. Vielleicht ahnen es einige Leser bereits: in gewissem Sinn spricht \( A_k(k) \) über sich selbst, denn es macht eine Aussage über die Gödelnummer der Aussage \( A_k(x) \).
Als nächsten Schritt wollen wir in der Sprache der Peano-Arithmetik ausdrücken, ob das Diagonalelement \( A_k(k) \) bewiesen werden kann oder nicht.
Erinnern wir uns (Kapitel 2.2): Man kann eine vollständige Liste aller Beweise wohlgeformter Aussagen aufstellen, d.h. die Beweise lassen sich eindeutig durchnummerieren. Jedem Beweis entspricht also eindeutig eine natürliche Zahl \(p\). Nennen wir den entsprechenden Beweis \( P_p \) (das große \(P\) steht dabei für das englische Proof, und der Index \(p\) ist die Gödelnummer des Beweises, also die Zeilennummer in der Liste aller Beweise, in der der Beweis steht).
Nun definieren wir die folgende Funktion \(W(k,p)\):
Diese Funktion ist berechenbar, denn man kann mechanisch die folgenden Schritte jeweils in endlich vielen Schritten durchführen:
Da die Funktion \(W(k,p)\) demnach berechenbar ist, können wir das Representation Theorem anwenden und die Funktion durch eine wohlgeformte Aussage (nennen wir sie \(B(k,p)\) ) in der Peano-Arithmetik darstellen. Dabei gilt:
Die Aussage \(B(k,p)\) ist also beweisbar, wenn \( P_p \) ein Beweis zur Aussage \( A_k(k) \) ist. Andernfalls ist \( \neg B(k,p) \) beweisbar. Wenn \(B(k,p)\) beweisbar ist, so bezeichnet man die beiden Zahlen \(k\) und \(p\) auch als Beweispaar, denn die Beweisnummer \(p\) liefert den Beweis zum Diagonalelement der \(k\)-ten Aussage.
Und nun wird es interessant: Wir konstruieren die folgende wohlgeformte Aussage – nennen wir sie \(M(x)\) :
Die Interpretation dieser Aussage ist: Für alle \(y\) gilt, dass \(y\) nicht die Beweisnummer zum Diagonalelement der \(x\)-ten Aussage ist. Frei übersetzt bedeutet das: Kein \(y\) ist die Beweisnummer zum Diagonalelement der \(x\)-ten Aussage.
Nun ist aber \(M(x)\) ebenfalls eine Aussage, sagen wir, die \(m\)-te , d.h. \(m\) ist die Gödelnummer der Aussage \(M(x)\). Wir können daher \(M(x)\) auf sich selber anwenden, indem wir \( x = m \) setzen – wir bilden also das Diagonalelement von \(M(x)\). Zu Ehren Gödels bezeichnen wir dieses Diagonalelement \(M(m)\) als \(G\). Sie haben es sicher geahnt: \(G\) ist genau die oben bereits erwähnte Gödelsche Aussage):
Die Interpretation von \( G \) lautet: Kein \(y\) ist die Beweisnummer zum Diagonalelement der \(m\)-ten Aussage, also von \( G \) selbst.
Frei übersetzt behauptet \( G \) also: Ich bin nicht beweisbar!.
Nun kann \( G \) zunächst einmal viel behaupten. Überprüfen wir daher die Konsequenzen:
Angenommen, \( G \) ist beweisbar (\( G \) hatte die Gödelnummer \(m\)). Dann gibt es einen Beweis von \( G \) mit einer Beweisnummer (nennen wir sie \(g\) ), so dass die Aussage \(B(m,g)\) beweisbar ist.
Andererseits gibt es eine allgemeine logische Umformungsregel (die sogenannte Spezialisierungsregel), mit der man den Universal-Quantor \( \forall \) in \( G \) eliminieren kann: Man lässt den Teil \( \forall y : \) weg und setzt für \(y\) eine beliebige natürliche Zahl ein, beispielsweise \(g\). Diese Umwandlungsregel begründet letztlich die Interpretation des Universal-Quantors \( \forall \) als das umgangssprachliche für alle. Wenn etwas für alle Zahlen \(y\) gilt, dann auch für die spezielle Zahl \(g\).
\( G \) lässt sich also umformen in die Aussage \( \neg B(m,g) \). Damit folgt aus der angenommenen Beweisbarkeit von \( G \), dass die synonyme Aussage \( \neg B(m,g) \) beweisbar ist.
Oben hatten wir aber bereits gesehen, dass aus der Beweisbarkeit von \(G\) die Beweisbarkeit von Aussage \(B(m,g)\) folgt. Damit wären die Aussagen \(B(m,g)\) und \( \neg B(m,g) \) beide beweisbar, d.h. die Peano-Arithmetik wäre widerspruchsvoll. Dieser Widerspruch folgt aus der angenommenen Beweisbarkeit von \(G\).
Umgekehrt gilt also:
Mit \( G \) haben wir eine ganz konkrete wohlgeformte Aussage gefunden, die sich nicht beweisen lässt (Widerspruchsfreiheit vorausgesetzt), die aber dennoch eine wahre Interpretation hat, denn sie sagt ja "Ich bin nicht beweisbar".
Wie sieht es dann mit der gegenteiligen Aussage \( \neg G \) aus? Ist sie beweisbar, wenn schon \( G \) nicht beweisbar ist?
Tasten wir uns langsam an die Interpretation von \( \neg G \) heran. In voller Schönheit lautet sie:
Es gibt also mindestens eine Beweisnummer zu einem Beweis für \( G \). Die verneinte Aussage \( \neg G \) behauptet also: \(G\) ist beweisbar.
Diese verneinte Aussage \( \neg G \) ist nach unserer obigen Interpretation falsch, denn wir haben gerade gezeigt, dass \( G \) nicht beweisbar sein kann (Widerspruchsfreiheit wieder vorausgesetzt). Wir erwarten also, dass auch \( \neg G \) nicht beweisbar ist, denn sonst würde sie die Beweisbarkeit von \( G \) beweisen, was zu einem Widerspruch führt.
Allerdings ist dies noch kein Beweis, dass \( \neg G \) nicht beweisbar ist. Wir haben lediglich eine Interpretation für \( \neg G \) gefunden, die eine falsche Aussage liefert. Wir werden in einem späteren Kapitel aber noch eine Interpretation finden, in der \( \neg G \) wahr ist. Man stelle sich vor, es gäbe neben den natürlichen Zahlen noch gewisse andere (übernatürliche) Zahlen, und das Existenz-Symbol \( \exists \) würde interpretiert als es gibt eine gewisse (ggf. übernatürliche) Zahl. Details dazu folgen in einem späteren Kapitel.
Untersuchen wir also, ob \( \neg G \) beweisbar ist oder nicht. Dazu genügt es, die Widerspruchsfreiheit der Peano-Arithmetik vorauszusetzen. Der Beweis ist dann jedoch etwas umständlich (aber durchführbar). Wir werden daher eine etwas vereinfachte Version des Beweises betrachten, bei der wir die Omega-Widerspruchsfreiheit der Peano-Arithmetik voraussetzen. Was bedeutet das?
Omega-Widerspruchsfreiheit bedeutet, dass für jede wohlgeformte Aussage \( A(p) \) mit einer freien Variablen gilt:
Nun könnte man meinen, Omega-Widerspruchsfreiheit sei dasselbe wie gewöhnliche Widerspruchsfreiheit. Es gibt jedoch subtile Unterschiede, die mit der Interpretation der Quantoren \( \exists \) und \( \forall \) zusammenhängen. Immerhin folgt aus der Omega-Widerspruchsfreiheit die gewöhnliche Widerspruchsfreiheit (aber nicht umgekehrt!) - wir wollen diese Tatsache hier ohne Beweis zur Kenntnis nehmen.
Wir setzen also die Omega-Widerspruchsfreiheit der Peano-Arithmetik voraus. Nehmen wir nun an, \( \neg G \) wäre beweisbar. Dann ist \( G \) nicht beweisbar (wegen der Widerspruchsfreiheit), d.h. es gibt keine Beweisnummer zu \(m\) (das war die Gödelnummer von \(G\) ). Für jede Beweisnummer \(p\) gilt also \( W(m,p) = 0 \) (d.h. \(p\) ist keine Beweisnummer zur \(G\) ), und daraus folgt, dass für alle \(p\) die Aussage \( \neg B(m,p) \) beweisbar ist.
Die Omega-Widerspruchsfreiheit sagt dann (setze \( \neg B(m,p) \) für \(A(p)\) ein), dass die Aussage \( \exists y: \neg \neg B(m,y) \) und somit \( \exists y: B(m,y) \) nicht beweisbar ist, wenn wir die Beweisbarkeit von \( \neg G \) annehmen.
Andererseits ist \( \neg G \) die Aussage
Diese Aussage lässt sich mit Hilfe einer formalen Umwandlungsregel der Logik (die sogenannte Austauschregel) in die folgende Aussage umformen.
Grund: die Austauschregel sagt, dass man in jeder wohlgeformten Zeichenkette den Substring \( \forall y : \neg \) ersetzen kann durch den Substring \( \neg \exists y: \) , denn wenn etwas für alle \(y\) nicht gilt, dann gibt es auch kein \(y\), für das es gilt. \( \neg G \) wird damit zur Aussage \( \neg \neg \exists y : B(m,y) \) . Anschließend muss man nur noch die doppelte Verneinung \( \neg \neg \) wegstreichen und wir haben \( \exists y : B(m,y) \) .
Das aber bedeutet, dass es eine Beweisnummer \(y\) zur Aussage Nummer \(m\), also der Aussage \(G\) gibt, wenn wir die Beweisbarkeit von \( \neg G \) annehmen. Beide Aussagen \(G\) und ihr Gegenteil \( \neg G \) wären beweisbar.
Damit aber folgt, dass die Peano-Arithmetik nicht mehr widerspruchsfrei und somit auch nicht Omega-widerspruchsfrei ist, entgegen unserer Voraussetzung.
Daher kann \( \neg G \) nicht bewiesen werden, wenn die Peano-Arithmetik Omega-widerspruchsfrei ist (wobei man mit etwas Aufwand diese Voraussetzung so abschwächen kann, dass nur noch die Widerspruchsfreiheit gefordert ist).
Halten wir fest:
Weder \( G \) noch \( \neg G \) können also bewiesen werden, wenn die Peano-Arithmetik widerspruchsfrei ist. Sie ist also unvollständig. Damit haben wir wieder Gödels ersten Unvollständigkeitssatz bewiesen, dass die Peano-Arithmetik nicht zugleich widerspruchsfrei und vollstängig sein kann.
© Jörg Resag, www.joerg-resag.de
last modified on 25 February 2023