Kapitel 2
Die Unvollständigkeit formaler Systeme

6    Ist Widerspruchsfreiheit beweisbar?

Hilberts Vision musste aufgrund der Ergebnisse von Gödel und Turing eine Reihe von Rückschlägen hinnehmen:

Wenn das formale System widerspruchsfrei ist, dann wird es Aussagen geben, die sich innerhalb des formalen Systems weder beweisen noch wiederlegen lassen, und wir wissen nicht bei jeder beliebigen Aussage, ob sie beweisbar oder wiederlegbar ist. Eine Aussage könnte beweisbar oder wiederlegbar sein oder auch keines von beidem; die Entscheidung darüber muss für jede Aussage individuell gesucht werden - ohne Erfolgsgarantie.

Bleibt die Frage: Ist das formale System widerspruchsfrei. Oder konkreter: ist die Peano-Arithmetik widerspruchsfrei? Die bisherigen Ergebnisse liefern dazu keine Antwort. Wir können nur sagen: Wenn die Arithmetik widerspruchsfrei ist, dann ist sie unvollständig, und es gibt kein Entscheidungsverfahren.


Hilbert sagte dazu in seinem berühmten Vortrag aus dem Jahr 1900:

"Vor Allem aber möchte ich unter den zahlreichen Fragen, welche hinsichtlich der Axiome gestellt werden können, dies als das wichtigste Problem bezeichnen, zu beweisen, dass dieselben untereinander widerspruchslos sind, d.h. dass man auf Grund derselben mittelst einer endlichen Anzahl von logischen Schlüssen niemals zu Resultaten gelangen kann, die miteinander in Widerspruch stehen.

In der Geometrie gelingt der Nachweis der Widerspruchslosigkeit der Axiome dadurch, dass man einen geeigneten Bereich von Zahlen konstruiert, derart, dass den geometrischen Axiomen analoge Beziehungen zwischen den Zahlen dieses Bereiches entsprechen und dass demnach jeder Widerspruch in den Folgerungen aus den geometrischen Axiomen auch in der Arithmetik jenes Zahlenbereiches erkennbar sein müsste. Auf diese Weise wird also der gewünschte Nachweis für die Widerspruchslogigkeit der geometrischen Axiome auf den Satz von der Widerspruchslosigkeit der arithmetischen Axiome zurückgeführt.

Zum Nachweise für die Widerspruchslosigkeit der arithmetischen Axiome bedarf es dagegen eines direkten Weges.

... Ich bin nun überzeugt, dass es gelingen muss, einen direkten Beweis für die Widerspruchslosigkeit der arithmetischen Axiome zu finden, wenn man die bekannten Schlussmethoden in der Theorie der Irrationalzahlen im Hinblick auf das bezeichnete Ziel genau durcharbeitet und in geeigneter Weise modifiziert."


Hilbert ruft also dazu auf, einen Beweis für die Widerspruchsfreiheit der arithmetrischen Axiome zu finden. Dieser Beweis muss seiner Meinung nach in der Sprache der Arithmetik selbst geführt werden ("..bedarf es eines direkten Weges"), da die Arithmetik den Grundpfeiler der Mathematik bilden soll und deshalb alle zum Beweis notwendigen Methoden der Logik enthalten muss.

Es ist interessant, dass Hilbert den Beweis der Widerspruchsfreiheit der Geometrie (z.B. die euklidische Geometrie) erwähnt. Die Geometrie ist dann widerspruchsfrei, wenn das (sehr viel mächtigere) System der Arithmetik widerspruchsfrei ist. Die Widerspruchsfreiheit eines schwächeren Systems (die Geometrie) konnte also in der Sprache eines umfassenderen Systems (Arithmetik) bewiesen werden. Ob dieses umfassendere System allerdings widerspruchsfrei ist, weiß man dabei nicht. Diesen Gedanken sollten wir uns für später merken! Bei der Arithmetik scheint es jedoch ein solches umfassenderes System nicht zu geben (wir werden später sehen, dass es doch eines gibt, aber für dieses umfassendere System stellt sich die Frage nach der Widerspruchsfreiheit dann ebenso).

Warum ist es eigentlich so wichtig, dass ein formales System keine Widersprüche enthält? Könnte man nicht mit dem einen oder anderen kleinen Widerspruch leben, solange das System ansonsten vernünftig ist?

Das Problem liegt darin, dass schon ein einziger Widerspruch das komplette formale System infiziert. Das liegt an einer Eigenschaft der Aussagenlogik, die dem formalen System zugrundeliegt. Man kann nämlich aus einem Widerspruch jede beliebige wohlgeformte Aussage ableiten, d.h. es gilt \begin{equation} \left( A \land \neg A \right) \implies B \end{equation} für beliebige Aussagen \(B\). Wenn also ein formales System, das auf der Aussagenlogik aufbaut, einen Widerspruch enthält (also zwei beweisbare Aussagen \(A\) und ihr Gegenteil \( \neg A \) ), so lässt sich jede wohlgeformte Aussage darin beweisen, und das System verliert jede Aussagekraft.

Allerdings ist die Entdeckung eines Widerspruchs in einem mathematischen System in der Praxis (wie auch im täglichen Leben) zumeist keine Katastrophe, sondern eher ein guter Ansatzpunkt zur Weiterentwicklung des Systems. Man kann die Ursache für den Widerspruch analysieren und versuchen, das System so zu verändern, dass der Widerspruch verschwindet. Ein bekanntes Beispiel ist dafür die Mengenlehre, in der ein unvermuteter Widerspruch (die Menge aller Mengen, die sich nicht selbst enthalten) Anlass zur Weiterentwicklung gab – wir kommen in einem späteren Kapitel darauf zurück.

Wenn wir jedoch den Anspruch haben, ein verlässliches Fundament für die Mathematik z.B. durch die Peano-Arithmetik aufzubauen, so erscheint es wünschenswert, dass dieses Fundament keine Widersprüche enthält, und dass sich dies mit den Mitteln dieses Fundamentes beweisen lässt.


Untersuchen wir also, ob man innerhalb der Peano-Arithmetik beweisen kann, dass die Peano-Arithmetik selbst widerspruchsfrei ist:

Dazu müssen wir innerhalb der Peano-Arithmetik die Widerspruchsfreiheit ausdrücken. Wir brauchen einen wohlgeformten Ausdruck, dessen Interpretation lautet: "es gibt keine Widersprüche". Betrachten wir zwei beliebige wohlgeformte Aussagen \(A_m\) und \(A_n\) mit Gödelnummern (also Aussagennummern) \(m\) und \(n\) (siehe Kap. 2.5) sowie zwei beliebige Beweisketten mit Gödelnummern (Beweisnummern) \(p\) und \(q\). Nun definieren wir eine berechenbare, überall definierte Funktion \(f(m,n,p,q)\):

Da die Funktion berechenbar ist, gibt es nach dem Representation Theorem eine wohlgeformte Aussage \( W(m,n,p,q) \), die beweisbar ist, wenn \( f(m,n,p,q) = 1 \) ist, und deren Gegenteil \( \neg W(m,n,p,q) \) beweisbar ist, wenn \( f(m,n,p,q) = 0 \) ist.

Nun konstruieren wir die folgende wohlgeformte Aussage, die wir \( \mathrm{CONS} \) (für engl. Consistent) nennen wollen:

Diese Aussage bedeutet: Es gibt keine Aussagennummern \(m\) und \(n\) und keine Beweisnummern \(p\) und \(q\), so dass Aussage Nummer \(m\) durch Beweis Nummer \(p\) bewiesen wird, Aussage Nummer \(n\) durch Beweis Nummer \(q\) bewiesen wird, und die beiden Aussagen einen Widerspruch darstellen. Anders gesagt: Man kann keine widersprüchlichen Aussagen herleiten.

Die Frage ist nun: kann die Aussage \( \mathrm{CONS} \) aus den Axiomen abgeleitet werden?

Betrachten wir Gödels ersten Satz aus Kapitel 2.5 :

  • Wenn die Peano-Arithmetik widerspruchsfrei ist, dann kann \(G\) nicht bewiesen werden.
  • Bei der Durchführung dieses Beweises haben wir nur logische Methoden verwendet, wie sie auch in der Peano-Arithmetik verfügbar sind. Wir müssten also in der Lage sein, den Beweis in die Sprache der Peano-Arithmetik zu übersetzen. Die entsprechende Beweiskette hätte irgendwo am Anfang die Aussage \( \mathrm{CONS} \) als Voraussetzung (stellvertretend für die Bedingung "Wenn die Peano-Arithmetik widerspruchsfrei ist" aus Gödels Satz), und am Ende steht das Peano-Äquivalent für die Aussage "\(G\) kann nicht bewiesen werden", also die wohlgeformte Zeichenkette \( \forall y : \neg B(m,y) \)   (siehe Kapitel 2.5).

    Zugegeben: diese vollständige Übersetzung des Gödelschen Beweises in die formale Sprache der Peano-Arithmetik ist nicht ganz einfach vorzunehmen. Aber wir sind nicht überrascht, dass es geht, auch wenn wir hier diese mühsame Aufgabe nicht im Detail durchführen wollen.

    Nun ist aber die hergeleitete Zeichenkette \( \forall y : \neg B(m,y) \) , die aussagt, dass \(G\) nicht bewiesen werden kann, gerade selbst die Zeichenkette \(G\). Wir haben also eine Beweiskette wohlgeformter Ausdrücke gebildet, die irgendwo vorne mit dem Ausdruck \( \mathrm{CONS} \) anfängt und hinten mit dem Gödelschen Ausdruck \(G\) endet.

    Nehmen wir nun an, die Aussage \( \mathrm{CONS} \) wäre innerhalb der Peano-Arithmetik beweisbar. Dann können wir die obige Beweiskette von \( \mathrm{CONS} \) nach \(G\) an den Beweis von \( \mathrm{CONS} \) anhängen und hätten eine Beweiskette für die Aussage \(G\) gefunden. In Kapitel 2.5 haben wir aber gesehen, dass die Beweisbarkeit von \(G\) zu einem Widerspruch führt (gerade so hatten wir die Nichtbeweisbarkeit von \(G\) begründet). Wenn es also einen Beweis für die Aussage \( \mathrm{CONS} \) gibt, so gibt es einen Beweis für \(G\), und damit kann man einen Widerspruch in der Peano-Arithmetik erzeugen. Dieses Ergebnis wurde ebenfalls von Kurt Gödel im Jahr 1931 gefunden; es wird daher auch als Gödels zweiter Satz bezeichnet. Halten wir fest:

    Und wieder gilt dieser Satz nicht nur für die Peano-Arithmetik, sondern für jedes formale System, das berechenbare Funktionen darstellen kann (das also hinreichend stark ist, so dass das Representation Theorem gilt).


    Gödels zweiter Satz sagt: Klar kannst Du versuchen, die Widerspruchsfreiheit der Peano-Arithmetik mit den Mitteln der Peano-Arithmetik zu beweisen. Aber solltest Du tatsächlich Erfolg haben, so hast Du gleichzeitig gezeigt, dass die Peano-Arithmetik Widersprüche enthält. Und in einer Theorie, die Widersprüche enthält, ist alles beweisbar, auch die Aussage \( \mathrm{CONS} \) – nur hat diese Beweisbarkeit dann keine Bedeutung mehr. Wenn die Peano-Arithmetik aber widerspruchsfrei ist, so kannst Du diese Widerspruchsfreiheit nicht mit den Mitteln der Peano-Arithmetik beweisen!

    Man kann sich in der Mathematik nicht selbst aus dem Sumpf ziehen. Und es wäre auch tatsächlich etwas merkwürdig, wenn das ginge. Es wäre so, als ob jemand behauptet "ich habe recht" und zur Begründung sagt "weil ich es sage".

    Ein hinreichend mächtiges formales System kann sich nicht selbst rechtfertigen. Um die Widerspruchsfreiheit eines solchen formalen Systems zu zeigen, benötigt man Ideen und Methoden, die über die Methoden des betrachteten Systems hinausgehen. Genau dies war auch notwendig, um die Widerspruchsfreiheit der Geometrie zu zeigen (siehe oben).

    Gibt es ein umfassenderes formales System, das die Peano-Arithmetik umfasst, aber gleichzeitig über sie hinausgeht, und das die notwendigen Methoden enthält, um die Widerspruchsfreiheit der Peano-Arithmetik zu beweisen?

    Tatsächlich gibt es ein solches System: die Mengenlehre (wir gehen in einem späteren Kapitel genauer darauf ein). In der Mengenlehre lassen sich Aussagen über natürliche Zahlen beweisen, die sich in der Peano-Arithmetik nicht beweisen lassen - und das, obwohl die Mengenlehre sich zunächst gar nicht um Zahlen zu kümmern scheint. Ein Beispiel für eine solche Aussage ist \( \mathrm{CONS} \) , die ja etwas über Vierergruppen von natürlichen Zahlen \( (m, n, p, q) \) aussagt.

    Aber auch die Mengenlehre kann sich nicht selbst rechtfertigen. Tatsächlich fand man in einer der früheren Versionen dieser Theorie auch einen überaschenden Widerspruch, obwohl jeder von der Widerspruchsfreiheit dieser Theorie überzeugt war. Man erweiterte daraufhin die Theorie, so dass der Widerspruch beseitigt wurde. Aber keiner weiß, ob die heute übliche Theorie der Mengenlehre wirklich widerspruchsfrei ist. Sollte man irgendwann einen Widerspruch entdecken, so bedeutet das aber keineswegs den Zusammenbruch der Mathematik. Man wird vielmehr die genauen Ursachen für den Widerspruch untersuchen und dabei vermutlich viel Neues über die Grundlagen der Mathematik lernen können. Schließlich wird man die neuen Erkenntnisse dazu nutzen, die Theorie so umzubauen, dass der Widerspruch verschwindet. Diese neue Theorie wird vermutlich reicher und mächtiger sein als die ursprüngliche.

    Gödels Ergebnisse sorgen also dafür, dass man niemals in einer endgültigen mathematischen Theorie erstarrt. Jede noch so mächtige Theorie bietet Raum für neue Ideen, neue Begriffe und neue Methoden. Die Welt der mathematischen Möglichkeiten ist unendlich reichhaltig, und sie kann von keinem noch so mächtigen mathematischen System vollständig erfasst werden. Vielleicht könnte man es bildlich so ausdrücken: selbst Gott kennt nicht alles, was mathematisch möglich ist.



    zurück zum Inhaltsverzeichnis

    © Jörg Resag, www.joerg-resag.de
    last modified on 25 February 2023