Gödelsche Unvollständigkeitssätze
Der Beweis von 1931, dass jedes hinreichend mächtige formale System Wahrheiten enthält, die es nicht beweisen kann — und nicht einmal seine eigene Widerspruchsfreiheit bestätigen kann.
Kurt Gödel war 25 Jahre alt und in Wien tätig, als er die Arbeit mit dem sperrigen Titel Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme veröffentlichte. Erster Satz: Jedes widerspruchsfreie, mechanisch aufzählbare Axiomensystem, das für Arithmetik ausreicht, enthält Aussagen, die innerhalb des Systems weder beweisbar noch widerlegbar sind. Zweiter Satz: Ein solches System kann seine eigene Widerspruchsfreiheit nicht beweisen. Hilberts Programm, das der Mathematik ein endgültiges Fundament geben sollte, war damit nicht bloß schwierig, sondern unmöglich.
Die Technik ist das eigentliche Erbe. Gödel nummerierte Formeln: Jeder Satz bekam eine Zahl, jeder Beweisschritt wurde zu einer arithmetischen Relation zwischen Zahlen, und das System konnte so über sich selbst sprechen, ohne die Arithmetik zu verlassen. Anschließend konstruierte er einen Satz, der in dieser Kodierung behauptet: „Ich bin nicht beweisbar.“ Lässt er sich beweisen, ist er falsch, und das System beweist Falsches. Lässt er sich nicht beweisen, ist er wahr — und unbeweisbar.
Dieselbe Diagonalisierung taucht fünf Jahre später im Halteproblem wieder auf, im Satz von Rice, in Quines und in jedem Ergebnis darüber, was statische Analyse niemals entscheiden kann. Gödel kodierte Formeln als Zahlen; eine Von-Neumann-Maschine speichert Programme als Daten im selben Speicher. Es ist derselbe Trick — einmal als Beweis, einmal als Bauprinzip.