Kapitel 2
Die Unvollständigkeit formaler Systeme

5  Wie Gödel die Unvollständigkeit der Arithmetik bewies

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 G), die nicht beweisbar sein kann, wenn die Peano-Arithmetik widerspruchsfrei ist, und deren Gegenteil ("NICHT 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 wiederlegbar ist. Wir wollen uns daher diese Aussage und Gödels Beweis im Folgenden genauer ansehen (die folgende Darstellung von Gödels Beweis orientiert sich an Peter Smith: Gödel's Proof, http://www.phil.cam.ac.uk/Smith/MathLogic/Godelproof.pdf ).


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 Ak aufstellen kann. Der Algorithmus zum Aufstellen dieser Liste ordnet dabei jeder Aussage Ak 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 Ak(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 Ak(k), d.h. wir ersetzen die freie Variable x in der Aussage Ak(x) durch die Gödelnummer dieser Aussage. Im folgenden werden wir daher Ak(k) als das Diagonalelement zur Aussage Ak(x) bezeichnen. Vielleicht ahnen es einige Leser bereits: in gewissem Sinn spricht Ak(k) über sich selbst, denn es macht eine Aussage über die Gödelnummer der Aussage Ak(x).

Als nächsten Schritt wollen wir in der Sprache der Peano-Arithmetik die Tatsache ausdrücken, ob das Diagonalelement Ak(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 Pp (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:

  1. Suche zu k die zugehörige Aussage Ak(x) (wenn es keine gibt, ist W(k,p)=0 ).
  2. Ersetze die freie Variable in der Aussage durch k, d.h. bilde das Diagonalelement Ak(k) .
  3. Suche zu p den zugehörigen Beweis Pp (wenn es keinen gibt, ist W(k,p)=0 ).
  4. Überprüfe, ob Pp ein Beweis für die Aussage Ak(k) ist (d.h. überprüfe, ob diese Aussage an Schluss der Beweiskette steht). Wenn ja, ist W(k,p)=1, andernfalls ist W(k,p)=0 .

Da W(k,p) 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:

B(k,p) ist also beweisbar, wenn Pp ein Beweis zur Aussage Ak(k) ist. Andernfalls ist "NICHT 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 (d.h. wir bilden das Diagonalelement von M(x)). Zu Ehren Gödels bezeichnen wir dieses Diagonalelement M(m) als G (ja, das ist die oben bereits erwähnte Gödelsche Aussage):

Die Interpretation von G lautet: Kein y ist die Beweisnummer zum Diagonalelement der m-ten Aussage (d.h. 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 "FÜR_ALLE" in G eliminieren kann: Man lässt den Teil "FÜR_ALLE y GILT:" weg und setzt für y eine beliebige natürliche Zahl ein, beispielsweise g (diese Umwandlungsregel begründet letztlich die Interpretation des Quantors "FÜR_ALLE" als das umgangssprachliche für alle). G lässt sich also umformen in die Aussage "NICHT B(m,g)". Damit folgt aus der angenommenen Beweisbarkeit von G, dass die Aussagen B(m,g) und "NICHT B(m,g)" beide beweisbar sind, d.h. die Peano-Arithmetik wäre widerspruchsvoll. 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 Aussage "NICHT G" aus? Ist sie beweisbar?

Tasten wir uns langsam an die Interpretation von "NICHT G" heran. In voller Schönheit lautet sie: Es ist nicht so, dass für alle y gilt, dass y nicht die Beweisnummer zum Diagonalelement der m-ten Aussage (also G) ist. Es gibt also mindestens eine Beweisnummer zu einem Beweis für G . "NICHT G" behauptet also: G ist beweisbar. Diese Aussage 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 "NICHT G" nicht beweisbar ist, denn sonst würde die Beweisbarkeit von G behauptet, was zu einem Widerspruch führt. Allerdings ist dies noch kein Beweis, dass "NICHT G" nicht beweisbar ist. Wir haben lediglich eine Interpretation für "NICHT G" gefunden, die eine falsche Aussage liefert. Wir werden in einem späteren Kapitel aber noch eine Interpretation finden, in der "NICHT G" wahr ist. Man stelle sich vor, es gäbe neben den natürlichen Zahlen noch gewisse andere (übernatürliche) Zahlen, und die Zeichenkette "ES_GIBT" würde interpretiert als es gibt eine gewisse (ggf. übernatürliche) Zahl. Details dazu folgen in einem späteren Kapitel.

Untersuchen wir also, ob "NICHT 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(x) mit einer freien Variablen gilt: Wenn A(n) für jede natürliche Zahl n beweisbar ist, dann ist die Aussage "ES_GIBT x: NICHT A(x)" nicht beweisbar. Es soll also nicht vorkommen, dass wir für jede natürliche Zahl n die Aussage A(n) beweisen können, aber dennoch zeigen können, dass es irgendein x gibt, für dass "NICHT A(x)" 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 ES_GIBT und "FÜR_ALLE" 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, "NICHT G" wäre beweisbar. Dann ist G nicht beweisbar (wegen der Widerspruchsfreiheit), d.h. es gibt keine Beweisnummer zu m (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 "NICHT B(m,p)" beweisbar ist.

Andererseits ist "NICHT G" die Aussage "NICHT FÜR_ALLE y GILT: NICHT B(m,y)". Diese Aussage lässt sich mit Hilfe einer formalen Umwandlungsregel der Logik (die sogenannte Austauschregel) in die Aussage "ES_GIBT y: B(m,y)" umformen.
Anmerkung: die Austauschregel sagt, dass man in jeder wohlgeformten Zeichenkette den Substring "FÜR_ALLE y GILT: NICHT" ersetzen kann durch den Substring "NICHT ES_GIBT y:" . Anschließend muss man nur noch die doppelte Verneinung "NICHT NICHT" wegstreichen - dies ist aufgrund der Umwandlungsregel der doppelten Verneinung erlaubt.

Damit aber folgt, dass die Peano-Arithmetik nicht mehr Omega-widerspruchsfrei ist, entgegen unserer Voraussetzung. Daher kann "NICHT 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 "NICHT G" können also bewisen werden, wenn die Peano-Arithmetik widerspruchsfrei ist. Sie ist also unvollständig. Damit haben wir wieder Gödels ersten Unvollständigkeitssatz bewiesen:


zurück zum Inhaltsverzeichnis

last modified on 16 December 2008