Toen Kurt Gödel in 1931 zijn beroemde Incompleteness Theorems publiceerde, schudde dat de grondslagen van de wiskundige logica: hij weerlegde dat alle axioma's die als mogelijke basis kunnen worden opgezet onvermijdelijk onvolledig zijn om alle uitspraken over getallen te bewijzen - en vernietigde dat Hilbert's droom om de consistentie van wiskundige theorie te bewijzen.
De introductie van Gödel-getallen (de unieke afbeelding van formules naar natuurlijke getallen) en diagonalisatie (het vervangen van de vrije variabele in functies door het bijbehorende Gödel-getal) zijn twee centrale concepten die Gödel in zijn bewijs introduceert. Het cruciale bewijsidee waarin Gödel deze concepten combineert, kan als volgt worden weergegeven.:
$$P(p) \, \text{wahr} \Leftrightarrow p \in \, \overline{B}^* \Leftrightarrow d(p) \in \overline{B} \Leftrightarrow d(p) \notin B \Leftrightarrow g(P(p)) \notin B \Leftrightarrow P(p) \, \text{unbeweisbar}$$
Aangezien \(P(p)\) niet onwaar kan zijn (aangezien het anders aantoonbaar en dus waar zou zijn), moet \(P(p)\) waar zijn en daarom niet aantoonbaar. Er is dus altijd een echte zin in een taal (met een keuze uit axioma's) die niet kan worden bewezen. Hier is \(g\) de Gödelisatie, \(p\) het Gödel-nummer van het predikaat \(P\) , het complementaire archetype \(\overline{B}^*\) van \(B\) (de verzameling van alle Godel getallen van alle bewijsbare proposities) onder de diagonaalfunctie \(d\) .
Voor verdere lectuur worden Gödels publicatie uit 1931 en het inzichtrijke artikel van Stepan Parunashvili aanbevolen. Naast de onvolledigheidstheorema's leverde Gödel andere baanbrekende bijdragen, waaronder de onweerlegbaarheid van Cantors continuümhypothese en het ontologisch argument voor het bestaan van God in de taal van de modale logica.