Im Jahr 1931 veröffentlichte ein 25-jähriger Wiener Logiker namens Kurt Gödel eine Arbeit mit dem Titel Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Sie war neun Seiten lang, technisch makellos und zerstörte das grundlagentheoretische Programm, das David Hilbert und Bertrand Russell jahrzehntelang aufgebaut hatten. Die Mathematik hatte gehofft, ihre eigene Widerspruchsfreiheit mit formalen Mitteln zu beweisen. Gödel zeigte: kein widerspruchsfreies formales System, das reich genug ist, die Arithmetik auszudrücken, kann seine eigene Widerspruchsfreiheit beweisen. Der Traum von einer vollständigen, sich selbst rechtfertigenden Mathematik war vorbei.
Gödels Kniff war Selbstbezüglichkeit, rigoros gemacht. Er zeigte, wie sich Aussagen über ein formales System innerhalb des Systems selbst kodieren lassen (Gödel-Nummerierung), und konstruierte dann einen Satz, der im Effekt sagt: „dieser Satz ist in diesem System nicht beweisbar.“ Ist das System widerspruchsfrei, lässt sich der Satz nicht beweisen (sonst wäre er falsch) und nicht widerlegen (sonst wäre er, seinem eigenen Inhalt nach, beweisbar und zugleich nicht). Also wahr, aber unbeweisbar. Der erste Unvollständigkeitssatz besagt: jedes hinreichend ausdrucksstarke widerspruchsfreie System enthält solche Sätze. Der zweite besagt: die Widerspruchsfreiheit des Systems selbst gehört zu jenen unbeweisbaren Aussagen. Das Ergebnis ist kein Mangel der Mathematik — es ist ein strukturelles Merkmal formaler Systeme, die über sich selbst zu sprechen versuchen. Die Mathematiker betrieben weiter Mathematik; das grundlagentheoretische Programm aber, das absolute Gewissheit anstrebte, war dauerhaft ernüchtert. Hilbert lebte noch zwölf Jahre und akzeptierte nie öffentlich, was geschehen war.
Die Unvollständigkeit taucht heute in Argumenten der Kognitionswissenschaft, KI und Philosophie des Geistes darüber auf, ob mechanische Systeme sich vollständig selbst modellieren können. Roger Penrose hat (umstritten) argumentiert, das menschliche Bewusstsein überschreite gödelsche Schranken; die meisten Philosophen des Geistes widersprechen. Die tiefere kulturelle Lehre — Systeme, die reich genug sind, um interessant zu sein, sind reich genug, um blinde Flecken über sich selbst zu haben — ist weit über die Mathematik hinausgewandert und gehört zu den meistzitierten Resultaten des zwanzigsten Jahrhunderts, selbst bei Leuten, die nicht wissen, wie der Beweis funktioniert.