von K. Gödel 1931 angegebener Satz, der intuitiv besagt, daß die Zahlentheorie, die Arithmetik, nicht axiomatisierbar ist. Anders ausgedrückt: Jede widerspruchsfreie Axiomatisierung der Zahlentheorie (z. B. die Peano-Arithmetik) ist unvollständig, in dem Sinne, daß sich arithmetische Aussagen finden lassen, die zwar wahr, aber mit der gegebenen Axiomatisierung nicht beweisbar sind.

Dieser Satz zeigt, daß die insbesondere von Hilbert ausgesprochene Hoffnung, daß die gesamte Mathematik „algorithmisierbar” oder „kalkülisierbar” sei, nicht zu realisieren ist. Eine arithmetische Aussage ist hierbei eine Formel der Prädikatenlogik der ersten Stufe ohne Vorkommen von freien Variablen, in der die speziellen Funktionssymbole + und * vorkommen, mit der entsprechenden Interpretation als Addition und Multiplikation auf den natürlichen Zahlen. Jede arithmetische Aussage ist in dieser Struktur (ℕ, +, *) entweder wahr oder falsch.

Man kann von den Einzelheiten einer Axiomatisierung der Zahlentheorie dadurch abstrahieren, daß man beachtet, daß jede Axiomatisierung (Menge von Axiomen und Schlußregeln) notwendigerweise auf eine rekursiv aufzählbare Menge führt, indem man systematisch alle Axiome aufzählt und ebenso systematisch die Schlußregeln auf die bisher erhaltenen Formeln anwendet. Daher ist eine Formulierung des Gödelschen Unvollständigkeitssatzes im Rahmen der Berechnungstheorie wie folgt möglich: Die Menge der wahren arithmetischen Aussagen ist nicht rekursiv aufzählbar (und damit insbesondere nicht entscheidbar, Entscheidbarkeit).

Der Beweis des Gödelschen Satzes verwendet als wesentliches Hilfsmittel das Konzept der Arithmetisierung, und zwar werden arithmetische Formeln und schließlich Beweise in der gegebenen Axiomatisierung (oder Turing-Maschinen in der berechnungstheoretischen Formulierung) als natürliche Zahlen dargestellt und können deshalb Bestandteil arithmetischer Formeln sein. Man kann daher arithmetische Formeln angeben die, intuitiv gesagt, ausdrücken: „Diese Formel ist nicht beweisbar”. Der Widerspruchsbeweis erinnert daher an die Antinomie vom Lügner, der sagt „ich lüge jetzt”.

Neben diesem „ersten” Unvollständigkeitssatz gibt Gödel noch einen „zweiten Unvollständigkeitssatz” an, der besagt, daß es in keinem widerspruchsfreiem Beweissystem S für die Arithmetik, das mindestens so stark wie die Peano-Arithmetik ist, möglich ist, eine arithmetische Formel W zu beweisen, die (per Arithmetisierung) besagt, daß S widerspruchsfrei ist.

Man vergleiche hierzu auch das Stichwort Logik.