Gödels Theorem: Unvollständigkeit formaler Systeme

Der Unvollständigkeitssatz von Gödel erklärt: Warum die formale Mathematik Grenzen hat

1931 bewies Kurt Gödel fundamentale Grenzen jedes hinreichend mächtigen formalen Arithmetik-Systems. Seine Unvollständigkeitssätze zeigen, dass es unmöglich ist, ein konsistentes System zu konstruieren, das alle wahren Aussagen über natürliche Zahlen beweisen kann. Diese Entdeckung zerstörte den Traum einer vollständigen Formalisierung der gesamten Mathematik.

Der Vereinigungstrend in Wissenschaft und Mathematik

Um die Jahrhundertwende vom 19. zum 20. Jahrhundert war in der Wissenschaft ein starker Vereinigungstrend zu beobachten. Newton vereinte die irdische Gravitation mit der Himmelsmechanik. Maxwell fasste Elektrizität, Magnetismus und Licht in einem einzigen elektromagnetischen Feld zusammen. Darwin erklärte die Vielfalt des Lebens durch die natürliche Auslese.

Mathematiker verfolgten eine ähnliche Synthese: Sie wollten Arithmetik, Geometrie und Analysis aus einem einzigen Axiomensystem ableiten. Frege schlug vor, Zahlen mithilfe der Mengenlehre zu definieren:

• 0 = ∅ (die leere Menge)
• 1 = {∅}
• 2 = {∅, {∅}}

Der Nachfolger einer Zahl n wurde als Vereinigung aller vorhergehenden Zahlen definiert – so ließ sich die gesamte Arithmetik formalisieren. Doch Russells Paradoxon brachte das System zum Einsturz: Aus seinen Axiomen folgte ein Widerspruch – die berüchtigte „Menge aller Mengen, die sich nicht selbst enthalten“.

Die Grundlagenkrise und Hilberts Programm

Russells Paradoxon löste eine tiefe Grundlagenkrise in der Mathematik aus. David Hilbert reagierte mit einem ehrgeizigen Formalisierungsprogramm, das drei zentrale Eigenschaften für jedes Axiomensystem forderte:

• Vollständigkeit (K): Das System beweist jede wahre arithmetische Aussage.
• Konsistenz (K): Das System beweist niemals falsche Aussagen.
• Entscheidbarkeit: Es existiert ein Algorithmus, der für jede gegebene Aussage berechnet, ob sie beweisbar ist.

Hilbert bestand darauf, dass diese Eigenschaften metamathematisch nachgewiesen werden – also mithilfe endlicher, anschaulicher Schlussweisen über das System selbst.

Russells und Whiteheads Principia Mathematica

Bertrand Russell und Alfred North Whitehead verfassten die Principia Mathematica (PM) – ein axiomatisches logisches System, das stark genug war, die gesamte Mathematik neu aufzubauen. Sie leiteten die Arithmetik von Grund auf ab und benötigten dafür berühmtermaßen über 300 Seiten, um 1 + 1 = 2 zu beweisen.

Um PM zu analysieren, vereinfachte Gödel dessen Syntax zu einer PM-Lisp-ähnlichen Sprache:

| Symbol | Bedeutung | Beispiel |

|--------|-----------|----------|

| 0 | Null | 0 |

| next | Nachfolger | (next 0) |

| + | Addition | (+ 0 (next 0)) |

| | Multiplikation | ( 0 (next 0)) |

| = | Gleichheit | (= 0 (* 0 (next 0))) |

Logische Operatoren:

| Symbol | Bedeutung | Beispiel |

|--------|-----------|----------|

| not | Negation | (not (= 0 1)) |

| or | Disjunktion | (or (= 0 1) (not (= 0 1))) |

| when | Implikation | (when 0 (or 0 1)) |

| there-is | Existenzquantor | (there-is x (= 4 (* x 2))) |

Zu den Axiomen von PM gehörten Tautologien wie:

• (when (or p p) p)
• (when p (or p q))
• Kommutativität und Assoziativität der Disjunktion
• Die Syllogismusregel

Aus diesen wurden Schritt für Schritt Gleichheit und Arithmetik abgeleitet.

Gödel-Nummerierung: Syntax als Zahlen kodieren

Gödel wandte eine Cantor-artige Kodierung an, um jede Formel einer eindeutigen natürlichen Zahl zuzuordnen. Jedes Symbol erhielt eine eigene, primzahlbasierte Gödel-Nummer:

| Symbol | Gödel-Nummer |

|--------|--------------|

| ( | 1 |

| ) | 3 |

| 0 | 5 |

| next | 7 |

| + | 9 |

| * | 11 |

| = | 13 |

| not | 15 |

| or | 17 |

| when | 19 |

| there-is | 21 |

| a, b, c, … | 2, 4, 6, … |

Die Formel (there-is a (= (next 0) a)) wird zunächst in eine Token-Sequenz zerlegt; ihre Gödel-Nummer berechnet sich dann als G = 2^g₁ × 3^g₂ × 5^g₃ × …, wobei jedes gᵢ die Gödel-Nummer des i-ten Tokens ist. Damit entsteht eine perfekte, eindeutige Zuordnung zwischen Formeln und natürlichen Zahlen.

Entscheidend ist: Die Arithmetik von PM-Lisp ist innerhalb ihrer selbst ausdrückbar: Formellänge, Substitution und Beweisbarkeit lassen sich alle als primitiv-rekursive Funktionen darstellen – was Selbstbezüglichkeit ermöglicht.

Selbstbezüglichkeit und der Unvollständigkeitssatz

Gödel konstruierte eine Formel G, die ihre eigene Unbeweisbarkeit behauptet: ∃p Proof(p, ⌜G⌝) – „Es gibt keinen Beweis mit Nummer p für mich.“

Durch das Diagonallemma (ein Fixpunktsatz) gilt:

G ≡ ¬Provable(⌜G⌝)

Satz 1: Ist PM konsistent, dann ist G wahr, aber innerhalb von PM unbeweisbar.

Satz 2: Ist PM konsistent, dann ist Con(PM) (die Aussage, die die Konsistenz von PM behauptet) innerhalb von PM unbeweisbar.

Wichtige Erkenntnisse:

• Jedes System, das die Peano-Arithmetik interpretiert, ist unvollständig.
• Die Konsistenz eines Systems lässt sich nicht innerhalb des Systems selbst beweisen.
• Natürliche Zahlen kodieren Syntax – und ermöglichen damit Selbstbezüglichkeit.
• Hilberts Programm ist prinzipiell nicht realisierbar.
• Wahrheit und Beweisbarkeit sind nicht identisch.

Konsequenzen für die Informatik

Gödels Satz ist logisch äquivalent zum Halteproblem von Turing. Formale Systeme besitzen inhärente „blinde Flecken“. In der Programmierung zeigt sich das beispielsweise als:

• Nicht-berechenbare Funktionen (z. B. eine hypothetische Halte-Oracle).
• Logische Bomben in Verifikationswerkzeugen.
• Harte Grenzen formaler Softwareverifikation.

Moderne Beweisassistenten (Coq, Lean) erkennen die Unvollständigkeit explizit an – sie stützen sich auf vertrauenswürdige Axiome, statt absolute Gewissheit zu beanspruchen.

— Editorial Team