Gödels Unvollständigkeitssätze

Sobald ein formales System die Arithmetik ausdrücken kann, reicht es nicht mehr an sich selbst heran: Seine eigene Widerspruchsfreiheit bleibt ihm unbeweisbar.

Als Nächstes empfohlen → Logik & Quantoren · MATH · T3

Der Beitrag

Sechsundzwanzig Seiten, technisch makellos, 1931 von einem 25-jährigen Wiener Logiker vorgelegt: Kurt Gödels Arbeit Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme riss das Grundlagenprogramm ein, an dem David Hilbert und Bertrand Russell Jahrzehnte gebaut hatten. Dieses Programm hatte einen Wahlspruch — „Wir müssen wissen, wir werden wissen“ — und eine sehr konkrete Hoffnung: die gesamte Mathematik auf ein endliches, mechanisches Fundament zu stellen, dessen Widerspruchsfreiheit im Prinzip ein geduldiger Schreiber nachprüfen könnte. Mit ihren eigenen formalen Mitteln sollte die Mathematik für sich selbst einstehen; Gödel zeigte jedoch, dass kein widerspruchsfreies formales System, das reich genug ist, um Arithmetik auszudrücken, seine eigene Widerspruchsfreiheit beweisen kann, und beendete damit den Traum von einer vollständigen, sich selbst begründenden Mathematik.

Gödels Kunstgriff war die streng gemachte Selbstbezüglichkeit. Über die Gödelisierung bekommt jedes Zeichen, jede Formel und jeder Beweis eine eindeutige Zahl; damit lässt sich, was ein System beweisen kann, als gewöhnliche arithmetische Aussage schreiben — und die kann das System dann über sich selbst treffen. Auf diesem Weg baute Gödel einen Satz, der der Sache nach behauptet: „Dieser Satz ist in diesem System nicht beweisbar.“ Ist das System widerspruchsfrei, lässt er sich weder beweisen — sonst wäre er falsch — noch widerlegen, denn dann wäre er seinem eigenen Inhalt nach beweisbar und zugleich nicht beweisbar. Bleibt: wahr und trotzdem unbeweisbar. Mit der Antinomie des Lügners hat das nichts zu tun; der Lügnersatz ist sinnleer, weder wahr noch falsch, Gödels Satz dagegen bestimmt wahr — von außen ist zu sehen, dass er gilt, das System aber kommt nicht an ihn heran. So weit der erste Unvollständigkeitssatz: Jedes hinreichend ausdrucksstarke widerspruchsfreie System enthält solche Sätze. Der zweite legt nach, denn auch die Widerspruchsfreiheit des Systems gehört zu ihnen. Kein System stellt sich selbst ein Gütesiegel aus; die Widerspruchsfreiheit der Arithmetik muss man voraussetzen oder von außen in einem reicheren System nachweisen, dessen eigene dann zur Debatte steht. Bei jedem Zugriff weicht die Gewissheit um einen Schritt zurück. Ein Mangel der Mathematik ist das nicht, sondern ein Strukturmerkmal formaler Systeme, die über sich selbst reden wollen. Wenige Jahre später fassten Turing und Church dieselbe Grenze berechenbarkeitstheoretisch: Es gibt kein allgemeines Verfahren, das entscheidet, was ein System beweisen kann, und das Halteproblem ist nichts anderes als die Unvollständigkeit, wie sie dem Ingenieur unterkommt. Mathematik wurde weiter betrieben wie zuvor; ernüchtert blieb auf Dauer das Grundlagenprogramm, das absolute Gewissheit wollte. Hilbert lebte noch zwölf Jahre und hat öffentlich nie eingeräumt, was geschehen war.

Warum jetztHeute taucht die Unvollständigkeit dort auf, wo Kognitionswissenschaft, KI-Forschung und Philosophie des Geistes darüber streiten, ob sich ein mechanisches System vollständig selbst abbilden kann. Roger Penrose hat — umstritten genug — vertreten, das menschliche Bewusstsein entkomme den gödelschen Schranken; die meisten Philosophen des Geistes sehen das anders. In der Informatik trägt das Resultat, es schmückt nicht: Auf ihm ruhen die Unentscheidbarkeitssätze, die abstecken, wie viel Compiler, Verifikationswerkzeuge und Typprüfer überhaupt zusichern können. Und die derzeit modische Hoffnung, eine hinreichend fortgeschrittene KI werde beweisbar sicher, indem sie über den eigenen Code nachdenkt, läuft gegen dieselbe Wand wie damals Hilbert. Über die Mathematik hinaus ist der Satz zu einer Warnung vor lückenloser Selbsterkenntnis geworden: Hinreichend ausdrucksstarke formale Systeme können nicht jede Frage über sich selbst entscheiden. Die Metapher wird weit häufiger zitiert, als der Beweis verstanden wird.

Zur VertiefungWer den Beweis selbst verstehen will, greift nach wie vor am besten zu Nagel und Newman, Gödel's Proof (1958) — kurz und von großer Klarheit; Hofstadters Gödel, Escher, Bach (1979) ist die lange, rekursive Variante. Gegen ein Jahrhundert der Überdehnung hilft Torkel Franzén, Gödel's Theorem: An Incomplete Guide to Its Use and Abuse (2005). Den mathematischen Kontext liefert van Heijenoorts Sammelband From Frege to Gödel (1967) in Übersetzung, die menschliche Seite Rebecca Goldsteins Incompleteness (2005).