mini|Porträt von Kurt Gödel, als Student der Universität Wien, 1925 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 Leistungsfähigkeit auf. Er weist nach, dass es in hinreichend starken Systemen, wie der Arithmetik, Aussagen geben muss, die man formal weder beweisen noch widerlegen kann. Der Satz beweist damit die Undurchführbarkeit des Hilbertprogramms, das von David Hilbert unter anderem begründet wurde, um die Widerspruchsfreiheit der Mathematik zu beweisen. Der Satz wurde 1931 von dem österreichischen Mathematiker Kurt Gödel veröffentlicht.Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. In: Monatshefte für Mathematik und Physik. 38, 1931, S. 173–198, doi:10.1007/BF01700692, Zentralblatt MATH, PDF, abgerufen am 3. April 2024.

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

Durch diese Sätze ist der Mathematik eine prinzipielle Grenze gesetzt: Nicht jeder mathematische Satz kann aus den Axiomen eines mathematischen Teilgebietes (zum Beispiel Arithmetik, Geometrie und Algebra) formal abgeleitet oder widerlegt werden.

In der Wissenschaftstheorie und 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 werden häufig exemplarisch hervorgehoben.

Grundbegriffe Aussagen sind Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen. Für solche Aussagen kann man im Rahmen der Modelltheorie das Konzept der Gültigkeit oder Wahrheit in Strukturen definieren. Dabei kann die Wahrheit einer Aussage durchaus von der betrachteten Struktur abhängen: Die Aussage „Es gibt eine Zahl zwischen 0 und 1“ gilt zum Beispiel in den rationalen (oder Bruch-)Zahlen (die rationale Zahl liegt zwischen 0 und 1), aber nicht in den ganzen Zahlen (es gibt keine ganze Zahl zwischen 0 und 1).

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.

Der Begriff hinreichend mächtig bedeutet im ersten und zweiten Unvollständigkeitssatz jeweils etwas anderes. Im zweiten Unvollständigkeitssatz ist damit gemeint, dass das System die Löbschen Bedingungen (L1–L3) erfüllt. Außerdem muss die Bernayssche Ableitbarkeitsbedingung erfüllt sein.

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

Ein System heißt vollständig, wenn für alle Aussagen die Aussage oder deren Negation aus 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:

Eine hinreichende Bedingung dafür, dass ein System „hinreichend mächtig“ ist, ist dabei, dass es natürliche Zahlen mit Addition und Multiplikation beschreibt und dass sich einige elementare Eigenschaften von natürlichen Zahlen darin ausdrücken und beweisen lassen, darunter beispielsweise, dass es keine natürliche Zahl unter null gibt und dass sich Aussageformen wie , oder usw. formulieren lassen.

Beweisskizze

Gödel zeigte den Satz ursprünglich unter einer etwas stärkeren Voraussetzung als der Konsistenz, nämlich der der ω-Konsistenz, die in dieser Skizze der Einfachheit halber auch angenommen wird. John Barkley Rosser zeigte 1936, wie man diese Voraussetzung fallen lassen kann.

Seine Argumentation benutzt eine Abzählung aller Sätze innerhalb des betrachteten formalen Systems. Hierbei wird jedem Satz eine eindeutige Nummer (seine Gödelnummer) zugewiesen. Gödel konstruiert dann eine Formel der Form

Er zeigt mit Hilfe einer Diagonalisierung, dass es eine Einsetzung für gibt, sodass der Satz mit der Nummer äquivalent ist zu der Aussage

Damit erhält er einen Satz mit der intuitiven Bedeutung „Ich bin nicht ableitbar“, den sogenannten Gödelsatz. Diese Konstruktion motivierte Gödel selbst mit dem Lügner-Paradoxon.

Man betrachte nun den Satz „Der Satz mit der Nummer ist ableitbar“. Anhand eines Widerspruchsbeweises zeigt sich, dass dieser Satz ebenso wenig wie seine Negation ableitbar und somit das System unvollständig ist: Angenommen, der Satz wäre ableitbar. Dann ergibt sich aus der ω-Konsistenz und der Stärke des Systems, dass der Satz mit der Nummer ableitbar ist. Dieser ist aber gerade äquivalent zur Negation des Satzes „Der Satz mit der Nummer ist ableitbar“. Hieraus ergibt sich ein Widerspruch im System. Da dieses aber als konsistent angenommen wurde, kann der Satz nicht ableitbar sein.

Man nehme nun an, dass die Negation des Satzes, also „Der Satz mit der Nummer ist nicht ableitbar“ ableitbar ist und somit auch der dazu äquivalente Satz mit der Nummer . Aus der Tatsache, dass das System als hinreichend mächtig angenommen wird, um jeden Beweis innerhalb des Systems „nachzuvollziehen“, folgt, dass mit der Ableitbarkeit eines Satzes mit irgendeiner Nummer auch der Satz „Der Satz mit der Nummer ist ableitbar“ ableitbar ist – nämlich, indem der Beweis mit Gödelnummern nachvollzogen wird. Das gilt auch für den Satz oben mit der Nummer : Er soll laut Annahme ableitbar sein, und daher ist auch „Der Satz mit der Nummer ist ableitbar“ ableitbar. Das ist aber genau die Negation der Annahme, und daher müsste hierfür das System widersprüchlich, also nicht ω-konsistent sein. Daher kann auch der Satz „Der Satz mit der Nummer ist nicht ableitbar“ nicht ableitbar sein.

Der metasprachliche Satz, dass der Satz mit der Nummer in dem System nicht ableitbar ist, ist damit jedoch bewiesen.

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

Die Aussage folgt aus dem ersten Satz. Sei ein konsistentes formales System, das so stark ist, dass darin der erste Unvollständigkeitssatz formalisiert und bewiesen werden kann. Dann beweist die Aussage: „Wenn konsistent ist, dann ist der Satz Ich bin nicht beweisbar nicht in beweisbar.“ Mittels eines Widerspruchsbeweises folgt die gewünschte Aussage: Man nehme an, beweise die Aussage „ ist konsistent“. Kombiniert man die beiden Aussagen, erhält man durch Modus ponens in einen Beweis der Aussage „Der Satz Ich bin nicht beweisbar ist nicht in 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ändigkeitssatz. Also ist entweder 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 formuliert 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, , 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 , 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 bestimmte wesentliche Eigenschaften über natürliche Zahlen darzustellen.

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