Gödelscher Unvollständigkeitssatz

Der Gödelsche Unvollständigkeitssatz ist einer der wichtigsten Sätze der modernen Logik. Er beschäftigt sich mit der Ableitbarkeit von Aussagen in formalen Systemen. Der Satz zeigt die Grenzen der formalen Systeme ab einer bestimmten Mächtigkeit auf und weist nach, dass es in hinreichend starken Systemen, wie der Arithmetik, Aussagen gibt – und geben muss – die man weder formal beweisen, noch widerlegen kann. Der Satz beweist damit die Unmöglichkeit des Hilbertprogramms, welches von David Hilbert unter anderem begründet wurde, um die Widerspruchsfreiheit der Mathematik zu beweisen. Der Satz wurde 1931 vom österreichischen Mathematiker Kurt Gödel veröffentlicht.

Genauer werden zwei Unvollständigkeitssätze unterschieden. Der Erste Unvollständigkeitssatz besagt, dass es in hinreichend starken widerspruchsfreien Systemen immer unbeweisbare Aussagen gibt. Der Zweite Unvollständigkeitssatz besagt, dass hinreichend starke widerspruchsfreie Systeme ihre eigene Widerspruchsfreiheit nicht beweisen können.

In der Wissenschaftstheorie und in anderen Gebieten der Philosophie zählt der Satz zu den meistrezipierten der Mathematik. Das Buch Gödel, Escher, Bach und die Werke von John Randolph Lucas, der versuchte, eine Theorie der Menschenrechte mit der Aussage zu zeigen, werden in dem Zusammenhang, zusammen mit ihren ebenso zahlreichen Kritikern, gern exemplarisch herausgehoben.

Durch die Sätze ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder wahre mathematische Satz kann aus den wie auch immer gewählten Axiomen eines mathematischen Teilgebietes (zum Beispiel Arithmetik, Geometrie und Algebra) formal abgeleitet werden.

Grundbegriffe

Aussagen sind Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen. Für solche Aussagen definiert man auf naheliegende Weise das Konzept der Gültigkeit oder Wahrheit in Strukturen (siehe Modelltheorie). Dabei kann die Wahrheit einer Aussage durchaus von der betrachteten Struktur abhängen: Eine Aussage mit der intendierten Bedeutung „Es gibt ein Element, das echt größer als 0 und echt kleiner als 1 ist“ gilt zum Beispiel in der Struktur $\mathbb{R}$ der reellen Zahlen, nicht jedoch in der Struktur $\mathbb{N}$ der natürlichen Zahlen.

Ein formales System ist ein System, in dem sich mathematische Aussagen beweisen lassen. Jedes formale System besteht aus einer Sprache, die die Menge der wohlgeformten Formeln und Aussagen spezifiziert, einer Menge von Axiomen und einer Menge von Schlussregeln, mit denen aus bereits bewiesenen Aussagen neue Aussagen hergeleitet werden können. Ein formales System bestimmt eine Theorie, die Menge aller im System herleitbaren Aussagen. Wichtig ist dabei, dass die Korrektheit eines Beweises im formalen System auf mechanische Weise verifiziert werden kann. Damit sind beispielsweise Kalküle mit unendlich großen Beweisen keine formalen Systeme in diesem Sinne. Im Sinne der Berechenbarkeitstheorie entspricht dies der formalen Forderung, dass die Theorie rekursiv aufzählbar sein muss.

Ein System T heißt widerspruchsfrei oder konsistent, wenn es keine Aussage A gibt, sodass aus T sowohl A als auch die Verneinung (Negation) von A folgt. Diese Bedingung ist, wie man mit dem Prinzip Ex falso quodlibet leicht zeigen kann, äquivalent dazu, dass nicht jede Aussage aus T folgt.

Ein System T heißt vollständig, wenn für alle Aussagen A aus T die Aussage A oder deren Negation folgt.

Gödels Sätze

Erster Unvollständigkeitssatz

Aussage

Der Erste Unvollständigkeitssatz besagt, dass man in (rekursiv aufzählbaren) Systemen der Arithmetik nicht alle Aussagen formal beweisen oder widerlegen kann:

Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.

Eine hinreichende Bedingung dafür, dass ein System „ausreichend mächtig“ ist, ist dabei, dass es natürliche Zahlen mit Addition und Multiplikation beschreibt und dass sich einige elementare Eigenschaften von Zahlen darin beweisen lassen, darunter beispielsweise, dass es keine natürliche Zahl unter Null gibt und dass Addition und Multiplikation für alle Paare von Zahlen definiert sind.

Beweisskizze

Hauptartikel: Beweise der Gödelschen Unvollständigkeitssätze

Gödels Argumentation benutzt eine Abzählung aller Sätze innerhalb des formalen Systems, jedem Satz wird eine eindeutige Nummer zugewiesen. Er konstruiert dann mit Hilfe einer Diagonalisierung eine Formel der Form: „Der Satz mit der Nummer x ist nicht ableitbar“ und zeigt, dass es eine Einsetzung n für x gibt, sodass a gleich der Nummer der Aussage „Der Satz mit der Nummer n ist nicht ableitbar“ ist. Damit erhält er einen Satz der Form „Ich bin nicht ableitbar“, den sogenannten Gödelsatz. Diese Konstruktion ähnelt dem klassischen Lügner-Paradoxon. Es gibt nun zwei Möglichkeiten: Entweder der Gödelsatz ist wahr, dann ist er nicht ableitbar, denn genau das ist sein Inhalt: „Ich bin nicht ableitbar.“. Oder der Gödelsatz ist falsch, dann muss er ableitbar sein. Demnach ist entweder das formale System unvollständig, oder es beweist falsche arithmetische Aussagen.

Falls das formale System nicht widersprüchlich ist, ist der Satz mit Nummer n und der Bedeutung „Satz n ist nicht ableitbar“ damit gezeigt. Wir vertrauen auf diesen „Beweis“, obwohl es innerhalb des Systems keine Ableitung gibt, die zu diesem Satz führt.

Damit obiger Ansatz funktioniert, muss das zugrundegelegte formale System mindestens Addition und Multiplikation auf den natürlichen Zahlen darstellen können. Für zu einfache Systeme gilt der Unvollständigkeitssatz daher nicht. Die Möglichkeit von Addition und Multiplikation sind ganz wesentliche Eigenschaften in vielen Theorien, so dass hier dieser Satz gilt. Insbesondere muss aber eine Substitution wie im Beweis Gödels möglich sein. Es gibt sehr einfache Systeme, für die diese Bedingungen erfüllt sind.

Nun könnte man sich dadurch behelfen, dass man für alle Sätze, die weder bewiesen noch widerlegt werden können, einfach festlegt, ob sie als wahr oder falsch gelten. Das formale System würde dann durch diese zusätzlichen Axiome erweitert. Lesen wir jedoch erneut den Unvollständigkeitssatz, so sehen wir, dass auch hier die Voraussetzungen erfüllt sind und somit auch das erweiterte System unvollständig bleibt, da stets unbeweisbare Sätze übrigbleiben.

Zweiter Unvollständigkeitssatz

Der Zweite Unvollständigkeitssatz besagt, dass jedes hinreichend mächtige konsistente System die eigene Konsistenz nicht beweisen kann:

Jedes hinreichend mächtige konsistente formale System kann die eigene Konsistenz nicht beweisen.

Die Aussage folgt aus dem ersten Satz. Sei T ein konsistentes formales System, das so stark ist, dass darin der erste Unvollständigkeitssatz formalisiert und bewiesen werden kann. Dann beweist T die Aussage: „Wenn T konsistent ist, dann ist der Satz „Ich bin nicht beweisbar“ nicht in T beweisbar.“ Um einen Widerspruch zu erzeugen, nehme man an, T beweist die Aussage „T ist konsistent“. Kombiniert man die beiden Aussagen, erhält man durch Modus ponens in T einen Beweis der Aussage „Der Satz „Ich bin nicht beweisbar“ ist nicht in T beweisbar.“ Diese Aussage ist aber gleichbedeutend mit der Aussage „Ich bin nicht beweisbar“, damit gibt es auch einen Beweis für diese Aussage. Dies ist ein Widerspruch zum ersten Unvollständigkeissatz. Also ist entweder T inkonsistent, oder es kann die eigene Konsistenz nicht beweisen.

Bedeutung

Erster Unvollständigkeitssatz

Gödels erster Unvollständigkeitssatz zeigt, dass jedes konsistente formale System, das genug Aussagen über natürliche Zahlen enthält, unvollständig ist: es gibt wahre Aussagen, die in seiner Sprache ausdrückbar sind, die aber nicht beweisbar sind. Damit kann kein formales System (das die Voraussetzungen des Satzes erfüllt) die natürlichen Zahlen eindeutig charakterisieren, da immer unbeweisbare zahlentheoretische Aussagen übrigbleiben.

Die Existenz eines unvollständigen formalen Systems ist zunächst nicht überraschend. Ein System kann einfach deswegen unvollständig sein, weil nicht alle nötigen Axiome entdeckt worden sind. Beispielsweise ist die Euklidische Geometrie ohne das Parallelenaxiom unvollständig; dieses kann mit den übrigen Axiomen weder bewiesen noch widerlegt werden.

Gödels Satz zeigt, dass in Theorien, die eine kleine Menge Zahlentheorie enthalten, eine vollständige und konsistente endliche Liste von Axiomen prinzipiell nicht existieren kann, und dass eine entsprechende unendliche Liste von einem Computerprogramm nicht aufgezählt werden kann. Nach der Church-Turing-These kann eine solche Liste auch nicht durch einen anderen intuitiv berechenbaren Algorithmus erstellt werden. Jedes Mal wenn ein neuer Satz als Axiom hinzugefügt wird, gibt es andere wahre Aussagen, die auch mit dem neuen Axiom immer noch nicht bewiesen werden können. Wenn ein Axiom hinzugefügt wird, das das System vollständig macht, wird das System gleichzeitig widersprüchlich.

Dennoch gibt es vollständige und konsistente Axiomenmengen für die Arithmetik, die aber von einem Algorithmus nicht aufgezählt werden können. Beispielsweise ist die Menge der wahren Aussagen über natürliche Zahlen, $\{\Phi\in\mathcal L_{\operatorname{PA}};\ \mathbb N\models\Phi \}$, eine vollständige und konsistente Axiomatisierung der Arithmetik. Die Schwierigkeit dabei ist, dass es keine mechanische Methode gibt, um nachzuweisen, dass eine Aussage in dieser Menge liegt. Ein ähnliches Problem entsteht bei unendlichen Kalkülen wie der Arithmetik mit ω-Regel, einer unendlichen Schlussregel, mit der sich genau die wahren arithmetischen Aussagen beweisen lassen. Da Ableitungen mit der ω-Regel unendlich groß sind, gibt es keine mechanische Methode, solche Beweise zu verifizieren.

Der Unvollständigkeitssatz sagt nur etwas aus für formale Systeme, die die notwendigen Voraussetzungen erfüllen. Nicht alle mathematisch interessanten Axiomensysteme erfüllen diese Voraussetzungen, selbst wenn sie Modelle haben, die die natürlichen Zahlen enthalten. Beispielsweise gibt es vollständige Axiomatisierungen der euklidischen Geometrie, der Theorie der algebraisch abgeschlossenen Körper von Charakteristik p, der dichten linearen Ordnungen ohne größtes und kleinstes Element und der natürlichen Zahlen ohne Multiplikation (Presburger-Arithmetik). Entscheidend ist, dass diese Theorien nicht ausdrucksstark genug sind, um wesentliche Eigenschaften über natürliche Zahlen darzustellen.

Zweiter Unvollständigkeitssatz

Gödels zweiter Unvollständigkeitssatz impliziert auch, dass eine ausreichend starke Theorie T₁ nicht die Konsistenz einer Theorie T₂ beweisen kann, wenn diese die Konsistenz von T₁ beweist. Denn eine solche Theorie T₁ kann beweisen, dass wenn T₂ konsistent ist und dieses die Konsistenz von T₁ beweist, T₁ auch konsistent sein muss. Denn die Konsistenz von T₁ lässt sich formalisieren als „keine Zahl n ist Gödelnummer eines Widerspruchsbeweises in T₁“. WennT₁ inkonsistent wäre, dann würde T₂ für ein n beweisen, dass n die Gödelnummer eines Widerspruchsbeweises in T₁ ist. Aber wenn T₂ auch die Konsistenz von T₁ beweist, beweist es auch, dass kein solches n existiert, wäre also inkonsistent.

Dieses Korollar des zweiten Unvollständigkeitssatzes zeigt, dass es nicht möglich ist, etwa die Konsistenz der Peano-Arithmetik mit finiten Mitteln zu formalisieren, die sich in einer schwächeren Theorie formalisieren lässt, deren Konsistenz die Peano-Arithmetik bewiesen kann. Beispielsweise lässt sich die Konsistenz der Primitiv Rekursiven Arithmetik (PRA), die oft als Formalisierung des finiten Kerns der Mathematik angesehen wird, in der Peano-Arithmetik beweisen. Damit kann PRA die Konsistenz der Peano-Arithmetik nicht beweisen. Die Tatsache wird oft als Beweis gesehen, dass Hilberts Programm, das die Mathematik durch finite Konsistenzbeweise begründen wollte, zumindest nicht im engeren Sinne von „finit“ ausführbar ist.

Der zweite Unvollständigkeitssatz macht Konsistenzbweise nicht vollkommen unmöglich, nur Konsistenzbeweise, die in der betroffenen Theorie selbst formalisiert werden können. Insbesondere sind oft Konsistenzbeweise in stärkeren Systemen möglich. So beweist die Peano-Arithmetik die Konsistenz schwächerer Formen der Arithmetik, die Zermelo-Frankel-Mengenlehre die Konsistenz der Peano-Arithmetik, und Erweiterungen der Zermelo-Frankel-Mengenlehre mit großen Kardinalzahlen beweisen die Konsistenz der Mengenlehre. Eine solche Theorie muss aber nicht immer stärker sein. So lässt sich Gentzens Konsistenzbeweis für die Peano-Arithmetik in einer Theorie formalisieren, die aus der schwachen Primitiv Rekursiven Arithmetik und einem Axiom für die Wohlfundiertheit der Ordinalzahl ε₀ besteht. Keine der beiden Theorien beweist alle Aussagen der anderen, die Stärken der beiden Theorien sind also nicht direkt vergleichbar.

Der zweite Unvollständigkeitssatz ist nur für formale Systeme bewiesen, die stark genug sind, um den Beweis des ersten Unvollständigkeitssatzes zu formalisieren. Es gibt konsistente Theorien, die Konsistenz ausdrücken und beweisen können, insbesondere Subsysteme der Arithmetik, in denen Multiplikation nicht beweisbar eine totale Funktion ist. Diese Systeme können zwar den Beweisbarkeitsbegriff formalisieren, aber nicht die für den ersten Unvollständigkeitssatz nötige Diagonalisierung.

Bedeutung für das Hilbertprogramm

Gödel versetzte mit seinem Unvollständigkeitssatz dem sogenannten Hilbertprogramm einen schweren Schlag. Dieses wurde von David Hilbert 1921 vorgeschlagen und hatte einen entscheidenden Einfluss auf die Forschung in der Logik in den 1920er Jahren. Es zielte darauf ab, die gesamte Mathematik durch ein Axiomensystem in Prädikatenlogik erster Stufe zu formalisieren und die Widerspruchsfreiheit der Axiome nachzuweisen. Hiermit sollten die Bedenken gegenüber nichtkonstruktiven Schlussweisen in der Mathematik, die vor allem von Intuitionisten geäußert wurden, ausgeräumt werden. Hilbert schlug vor, die Widerspruchsfreiheit von komplexeren Systemen durch diejenige einfacherer Systeme nachzuweisen. Die Motivation hierfür ist, dass einem Beweis zur Widerspruchsfreiheit eines Systems, der in diesem System selbst gegeben ist, nicht getraut werden kann. Denn aus einem Widerspruch heraus lässt sich alles beweisen (Ex falso quodlibet), also ließe sich aus einem Widerspruch im System auch die Widerspruchsfreiheit des Systems beweisen. Daher sollte die Widerspruchsfreiheit in einem einfacheren System bewiesen werden, sodass letztlich die Widerspruchsfreiheit der gesamten Mathematik auf einfache, offensichtlich widerspruchsfreie Axiome zurückgeführt werden kann.

Nach dem zweiten Unvollständigkeitssatz ist es aber unmöglich, die Widerspruchsfreiheit eines Systems in ihm selbst nachzuweisen, und damit erst recht, sie in einem einfacheren System nachzuweisen.

Philosophische Interpretationen

Obwohl Gödel sich im Laufe seines Lebens wiederholt als Platoniker zu erkennen gab, wurde sein Unvollständigkeitssatz wiederholt in einem subjektivistischen Sinn interpretiert. Auch schien Gödels Teilnahme am Wiener Kreis eine Nähe des Unvollständigkeitssatzes mit dem logischen Positivismus nahezulegen, der dem Platonismus in vielerlei Hinsicht entgegengesetzt ist. Gödels zurückhaltende, konfliktscheue Art trug dazu bei, die Fehlinterpretationen am Leben zu erhalten.

Gödel selbst verstand seinen Satz jedoch insbesondere als einen Schlag gegen den von Hilbert propagierten Formalismus in der Mathematik, der in letzter Konsequenz die gesamte Mathematik zu einem rein formalen Gebilde ohne Bezug zur „realen Welt“ machen sollte. Für Gödel als Platoniker waren jedoch die mathematischen Objekte durchaus „real“. Sie waren zwar nicht durch Sinneswahrnehmungen zu bestätigen (wie es die Positivisten einforderten), doch waren sie der Erkenntnis zugänglich. Der Unvollständigkeitssatz zeigte für Gödel, dass man dieser Realität nicht mit rein formalen Mitteln beikommen konnte.

Obwohl Gödel sich in seiner Grundhaltung gegenüber dem damals bedeutsamen logischen Positivismus nicht sehr von Ludwig Wittgenstein unterschied, der eine Realität jenseits der möglichen Bedeutung von Sätzen anerkannte (und sie sogar für wichtiger hielt als das Sagbare), hielten Wittgenstein und Gödel Zeit ihres Lebens nicht viel voneinander. In Wittgensteins Werk wird der Unvollständigkeitssatz eher abschätzig behandelt. Für Wittgenstein taugte der Satz lediglich für „logische Kunststücke“. Gödel hingegen wies in späteren Interviews jeglichen Einfluss Wittgensteins auf sein eigenes Denken weit von sich.

Häufige Fehlschlüsse

Die Gödelschen Unvollständigkeitssätze werden auch außerhalb der mathematischen Logik, ja sogar außerhalb der Fachmathematik zitiert. Dabei wird aber leicht übersehen, dass das in den Sätzen verwendete Fachvokabular nicht immer die Bedeutung hat, die die Begriffe in anderem Zusammenhang haben. In manchen Versuchen, die Ergebnisse einem breiteren Publikum zugänglich zu machen, wird dieses Problem aber auch nicht deutlich hervorgehoben. Dadurch kommen viele falsche Vorstellungen über die Bedeutung der Sätze zustande.

Daher folgen hier einige Warnungen vor Fehlschlüssen:

• Viel Verwirrung entsteht dadurch, dass Gödel ja nicht nur die Unvollständigkeitssätze bewiesen hat, sondern auch den Gödelschen Vollständigkeitssatz. Hier ist zu beachten, dass der Begriff der Vollständigkeit in zwei verschiedenen Bedeutungen gebraucht wird:
  • Der Vollständigkeitssatz beweist die semantische Vollständigkeit der Prädikatenlogik der ersten Stufe, behandelt also eine Eigenschaft von formalen Systemen.
  • Der Unvollständigkeitssatz hingegen beweist, dass gewisse Mengen von Ausdrücken nicht vollständig im Sinn einer Theorie sind: es gibt Fälle, wo weder ein Satz noch seine Negation zur Theorie gehören.
• Ein weiterer Fehlschluss ist, dass die meisten in der Mathematik benutzten Theorien unvollständig seien. Es gibt aber einige wichtige vollständige Theorien, wie z. B. die Theorie der algebraisch abgeschlossenen Körper von Charakteristik $p$, die Theorie der dichten linearen Ordnungen ohne größtes und kleinstes Element oder Tarskis Axiomatisierung der euklidischen Geometrie. Entscheidend ist, dass diese Theorien nicht ausdrucksstark genug sind, um wesentliche Eigenschaften über natürliche Zahlen darzustellen.
  • Es gibt es vollständige, widerspruchsfreie, rekursiv aufzählbare Axiomensysteme. Diese können aber keine Erweiterung der Arithmetik sein; insbesondere ist es in derartigen Systemen nicht möglich, über dieses System selbst zu reden. Sie sind damit nicht so ausdrucksstark, wie die volle Arithmetik mit 0, Nachfolger, Addition und Multiplikation. Ein einfaches Beispiel für ein derartiges, schwaches System ist die Arithmetik nur mit 0 und Nachfolger, ein weiters die Presburger-Arithmetik.
• Es ist möglich, die Arithmetik vollständig zu beschreiben: Die Theorie $T=\{\Phi\in\mathcal L_{\operatorname{PA}};\ \mathbb N\models\Phi \}$ ist eine (im hier verlangten Sinn) vollständige, widerspruchsfreie Erweiterung der bekannten Peano-Axiome. Man könnte die gesamte Menge dieser Sätze als „Axiomatisierung“ der Arithmetik bezeichnen. Der erste Unvollständigkeitssatz zeigt, dass diese Axiomatisierung aber nicht entscheidbar ist. Mit anderen Worten: es gibt kein Verfahren, mit dem für jeden Satz $\Phi$ feststellbar ist ob er zu dieser Menge gehört – es sei denn, man untersucht in $\N$, ob $\Phi$ dort gilt.
• Die Nichtbeweisbarkeit der eigenen Widerspruchsfreiheit in der Arithmetik kann nur unter starken Einschränkungen als eine „absolute“ Grenze des formalen Denkens bezeichnet werden. So hat etwa Gerhard Gentzen gezeigt, dass man die Widerspruchsfreiheit der Peano-Arithmetik (in einem formalen System) beweisen kann, wenn man die Möglichkeiten der Arithmetik etwas erweitert. Damit zeigen die Unvollständigkeitssätze lediglich, dass man ein stärkeres System benötigt, um die Widerspruchsfreiheit eines schwächeren Systemes zu beweisen. (Anschaulich ausgedrückt: „Das Münchhausen-Prinzip“ funktioniert auch in der Logik nicht ohne zusätzliche Hilfsmittel.) Setzt man, wie in der Mathematik üblich, die (Konsistenz der) Mengenlehre voraus, kann man mit den Natürlichen Zahlen $\mathbb N$ ein Modell der Arithmetik angeben. Damit ist die Widerspruchsfreiheit der Arithmetik gezeigt. Jedoch ist die Mengenlehre ihrerseits ein axiomatisches System, das ausdrucksstärker als die Arithmetik ist. Damit ist sie selbst wieder unvollständig und sie kann wiederum ihrerseits nicht ihre eigene Konsistenz beweisen.
• Damit die Unvollständigkeitssätze überhaupt einen Sinn haben, muss man die Widerspruchsfreiheit der Arithmetik voraussetzen. Aus der Inkonsistenz der Axiome würde sofort folgen, dass jeder Satz und auch seine Negation beweisbar wäre. Allerdings kann sie nicht innerhalb der Arithmetik selbst bewiesen werden.

Beispiele für Unvollständigkeit

Während die unbeweisbare Aussage, die beim Beweis des ersten Unvollständigkeitssatzes konstruiert wird, eher künstlich ist, sind auch natürliche mathematische Aussagen bekannt, die in natürlichen mathematischen Axiomensystemen unbeweisbar sind.

• 1943 zeigte Gerhard Gentzen, dass die transfinite Induktion bis ε₀ in der Peano-Arithmetik nicht hergeleitet werden kann.
• 1977 zeigten Jeff Paris und Leo Harrington, dass eine gewisse Variante des Satzes von Ramsey wahr, aber in der Peano-Arithmetik unbeweisbar ist (Satz von Paris-Harrington).
• 1982 zeigte Jeff Paris und Laurie Kirby, dass der Satz von Goodstein in der Peano-Arithmetik unbeweisbar ist.
• Paul Cohen bewies 1963, dass sowohl das Auswahlaxiom als auch die Kontinuumshypothese auf Grundlage der Zermelo-Fraenkel-Mengenlehre (ZF) formal unentscheidbar sind. (In dieser Mengenlehre kann man natürlich ausreichend viele Aussagen über natürliche Zahlen formulieren)
• Seitdem wurden zahlreiche weitere Beispiele dafür gefunden, dass in der Zermelo-Fraenkel-Mengenlehre (ZF) oder Erweiterungen Aussagen unentscheidbar sind. Für den Beweis greift man dabei immer wieder auf die Ergebnisse von Gödel zurück: wenn aus einer Aussage folgt, dass es ein Modell dieser Mengenlehre gibt und sie daher konsistent ist, dann kann diese Aussage nicht ableitbar sein.

Sonstiges

Gödel nannte seinen Aufsatz Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I, weil er plante, einen zweiten Aufsatz zu verfassen, in dem er den Beweis genauer erläutern wollte. Der erste Aufsatz fand jedoch bereits so große Anerkennung, dass der Bedarf für einen zweiten entfiel, der daher auch nie geschrieben wurde.

Konkret bezog sich Gödels Aufsatz auf die Principia Mathematica, ein großes formales System, das Bertrand Russell und Alfred North Whitehead zwischen 1910 und 1913 veröffentlichten. Gödel zeigte jedoch auf, dass jedes System mit der gleichen Mächtigkeit wie die Principia Mathematica ebenso anfällig ist.

Weiterhin konnte Gerhard Gentzen zeigen, dass eine konstruktive Mathematik und Logik durchaus widerspruchsfrei ist. Hier zeigt sich ein Grundlagenstreit der Mathematik. Der Philosoph Paul Lorenzen hat eine widerspruchsfreie Logik und Mathematik erarbeitet (Methodischer Konstruktivismus), und sein Buch Metamathematik (1962) eigens geschrieben, um zu zeigen, dass der gödelsche Unvollständigkeitssatz keinen Einwand gegen einen widerspruchsfreien Aufbau der Mathematik darstellt.

Siehe auch

• Metamathematik
• Goodstein-Folgen haben eine innerhalb der Peano-Arithmetik formulierbare, aber nicht beweisbare Eigenschaft.
• Referenzproblem

Literatur

Originalpublikationen

• Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik 38, 1931, S. 173–198, doi:10.1007/BF01700692. Zentralblatt MATH.
• Kurt Gödel: Diskussion zur Grundlegung der Mathematik: Erkenntnis 2. Monatshefte für Math. und Physik, 1931–32, S. 147–148.
•  J. Barkley Rosser: Extensions of some theorems of Gödel and Church. In: Journal of Symbolic Logic. 1, 1936, S. 87–91.

Populäre Einführungen

• Douglas R. Hofstadter: Gödel, Escher, Bach, ein Endloses Geflochtenes Band. München 1991 ISBN 3-423-30017-5 (Eine interessante und relativ leicht verständliche Erklärung von Gödels Satz und seinen Implikationen).
• Wolfgang Franz: Über mathematische Aussagen, die samt ihrer Negation nachweislich unbeweisbar sind. Der Unvollständigkeitssatz von Gödel. Franz Steiner Verlag, Wiesbaden, 1977, 27 S., ISBN 3-515-02612-6. (verständlicher Vortrag mit wissenschaftsgeschichtlichen Bezügen).
• Raymond Smullyan: Dame oder Tiger – Logische Denkspiele und eine mathematische Novelle über Gödels große Entdeckung. Fischer-Verlag Frankfurt am Main 1983. Das amerikanische Original erschien bei Alfred A. Knopf, New York 1982.
• Raymond Smullyan: To Mock a Mockingbird. 1985.
• Raymond Smullyan: Forever undecided: a puzzle guide to Gödel. 1987.

Mathematische Einführungen

•  David Hilbert und Paul Bernays: Grundlagen der Mathematik. II (= Die Grundlehren der mathematischen Wissenschaften. 50). Springer-Verlag, Berlin 1939. (enthält eine detaillierte arithmetisierte Beweisskizze des zweiten Unvollständigkeitssatzes)
•  Peter G. Hinman: Fundamentals of Mathematical Logic. A K Peters, Wellesley 2005, ISBN 1-56881-262-0. (enthält einen detaillierten Beweis des zweiten Unvollständigkeitssatzes in der Mengenlehre)
• Ernest Nagel u. James R. Newman: Der Gödelsche Beweis. 8. Auflage 2007. ISBN 978-3-486-45218-1.
•  Wolfgang Rautenberg: Einführung in die Mathematische Logik. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2 (http://www.springerlink.com/content/u46007/).
• Peter Smith: An Introduction to Gödel’s Theorems. Cambridge Introductions to Philosophy. Cambridge 2007. ISBN 978-0-521-85784-0.
•  Craig Smorynski: The incompleteness theorems. In: Jon Barwise (Hrsg.): Handbook of Mathematical Logic. North Holland, 1977, ISBN 0444863885.
• Raymond Smullyan: Gödel’s Incompleteness Theorems. Oxford Logic Guides. Oxford University Press, 1992.
• Max Urchs, Klassische Logik: eine Einführung, Berlin (1993). – ISBN 3-05-002228-0. (dort im Kapitel: Theorien erster Ordnung, S. 137–149).

Zur Bedeutung der Sätze

• Norbert Domeisen: Logik der Antinomien. Bern 1990. ISBN 3-261-04214-1, Zentralblatt MATH.
• Ludwig Fischer: Die Grundlagen der Philosophie und der Mathematik. Leipzig 1933.
• Torkel Franzen: Gödel’s Theorem. An incomplete guide to its use and abuse. Wellesley, Massachusetts 2005. ISBN 1-56881-238-8 (Eine leicht verständliche Erläuterung von Gödels Unvollständigkeitssätzen, ihren Implikationen und ihren Fehlinterpretationen).
• Sybille Krämer: Symbolische Maschinen: die Idee der Formalisierung in geschichtlichem Abriß. Darmstadt 1988. ISBN 3-534-03207-1.
• Paul Lorenzen: Metamathematik. Mannheim 1962. ISBN 3-86025-870-2.
• Paul Lorenzen: Lehrbuch der konstruktiven Wissenschaftstheorie. Stuttgart 2000. ISBN 3-476-01784-2.
• S. G. Shanker (Hg.): Gödel’s Theorem in focus. London/New York 1988. ISBN 0-415-04575-4.
• Wolfgang Stegmüller: Unvollständigkeit und Unentscheidbarkeit. Die metamathematischen Resultate von Gödel, Church, Kleene, Rosser und ihre erkenntnistheoretische Bedeutung. 3. Auflage, Springer-Verlag, Wien, New York, 1973. ISBN 3-211-81208-3. 116 S.
• Max Woitschach: Gödel, Götzen und Computer: eine Kritik der unreinen Vernunft. Stuttgart 1986. ISBN 3-87959-294-2.
• Palle Yourgrau: Gödel, Einstein und die Folgen. Vermächtnis einer ungewöhnlichen Freundschaft. Beck, München 2005. ISBN 3-406-52914-3. (Original: A World Without Time: The Forgotten Legacy of Gödel and Einstein. Basic Books, Cambridge, Massuchusetts 2005).

Weblinks

• Die Grenzen der Berechenbarkeit
• Einstieg in die Zusammenhänge des Unvollständigkeitssatzes
• Christopher v. Bülow: Der erste Gödelsche Unvollständigkeitssatz. Eine Darstellung für Logiker in spe. März 1992 (PDF, 355 kB)
• Eine englische Übersetzung von Gödels Aufsatz Über formal unentscheidbare Aussagen. (PDF, 328 KB)
• A short proof of Gödel's Second Incompleteness Theorem (PDF, 85 KB) von Thomas Jech