Onvolledigheidsstellingen van Gödel

De onvolledigheidsstellingen van Gödel zijn twee stellingen over de beperkingen van formele systemen, beide bewezen door Kurt Gödel in 1931. Door deze onvolledigheidsstellingen gaf Gödel het platonisme binnen de wiskunde een nieuw elan.

Geschiedenis
Begin twintigste eeuw werden pogingen ondernomen om de gehele wiskunde in één enkel formeel systeem te vangen. Om te beginnen werd de rekenkunde van de natuurlijke getallen geformaliseerd. De meest geslaagde poging hiertoe werd ondernomen door Bertrand Russell en Alfred North Whitehead in hun boek Principia Mathematica.

In 1929 bewees Gödel zijn volledigheidsstelling: de standaard predicatenlogica was volledig. Een jaar later publiceerde hij zijn onvolledigheidsstellingen in een artikel in de Monatshefte für Mathematik und Physik, getiteld "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I". De I duidt erop dat Gödel van plan was een toegankelijker vervolgartikel te schrijven, omdat hij vreesde dat zijn artikel zelfs voor zijn collega's onbegrijpbaar zou zijn. Die vrees bleek ongegrond: het belang van zijn resultaat werd al spoedig onderkend.

De eerste onvolledigheidsstelling
De eerste onvolledigheidsstelling stelt dat ieder axiomatisch wiskundig systeem dat voldoende krachtig is om alle basiseigenschappen van de natuurlijke getallen te bewijzen, hetzij onvolledig is (dat wil zeggen dat er ware uitspraken zijn die niet bewezen kunnen worden), hetzij inconsistent is (dat wil zeggen dat er onware uitspraken zijn die wel bewezen kunnen worden). Anders geformuleerd zal ieder consistent axiomatisch systeem van voldoende kracht om de getaltheorie in uit te drukken, stellingen kennen, die noch bewezen, noch ontkracht kunnen worden binnen dat systeem, en dus onbeslisbaar zijn.

Om dit te bewijzen construeert Gödel een zin Z in de formele taal van een axiomatisch systeem A die over zichzelf beweert: Z is niet bewijsbaar in A. Als deze zin waar is, dan is hij dus niet bewijsbaar (want dat is wat hij beweert). Maar dan is een ware zin niet bewijsbaar, en is het systeem A dus onvolledig. Is de zin echter niet waar, dan is hij dus wel bewijsbaar, en is er een onwaarheid bewijsbaar in A. In deze simpele formulering vertoont de zin Z een sterke gelijkenis met de leugenaarsparadox.

Overzicht van het bewijs
Hier volgt een korte samenvatting van het bewijs van Gödel.

Ten eerste gebruikt hij een zogenaamde Gödelnummering. Dit is een systeem om aan elke formule in het systeem, en elke serie uitspraken in het systeem, een getal toe te kennen. Een methode hiervoor is om de verschillende symbolen  van het systeem elk een uniek nummer  toe te kennen, en de uitspraak  (met  symbolen) vervolgens weer te geven met het getal  (gebruik alleen de priemgetallen).

Vervolgens wordt deze nummering gebruikt om aan te geven dat een serie van formules een bewijs vormt van een gegeven stelling. Dat wil zeggen, dat elke formule hetzij een axioma is, hetzij via een enkele afleidingsregel uit de voorgaande formules volgt, en dat de laatste formule de gegeven stelling is. Hieruit is vervolgens op eenvoudige wijze een predicaat  af te leiden dat waar is, dan en slechts dan als  het Gödelgetal van een bewijsbare stelling is.

Vervolgens komt een truc, die 'diagonalisatie' wordt genoemd: Zij  een willekeurig predicaat. We definiëren nu het predicaat  als het predicaat "Y is het Gödelnummer van een formule F(X), en  geldt". Pas dit nu toe op het predicaat . Dit levert een predicaat  op, dat in woorden zegt "dit getal is het Gödelnummer van een onbewijsbare stelling".

Bekijk nu de stelling , waar A het Gödelnummer van  is.

Neem aan dat het systeem correct is (en dus geen onware stellingen kan bewijzen), en dat we  kunnen bewijzen. Omdat  waar is, betekent dit dat A het Gödelnummer van een formule F(X) is waarvoor  geldt. A is het Gödelnummer van , dus , dus  is niet bewijsbaar. Tegenspraak.

Omgekeerd, als we  kunnen bewijzen, moet  dus niet waar zijn, waaruit we op gelijke wijze kunnen bewijzen dat .

Conclusie is dat als het axiomatisch systeem correct is,  en  beide niet bewijsbaar zijn, en het systeem dus niet volledig is.

Merk op dat er een sterke overeenkomst is met de leugenaarsparadox:  is een codering voor de uitspraak 'deze uitspraak kan niet bewezen worden', die verwant is met de uitspraak 'deze uitspraak is niet waar'.

De tweede onvolledigheidsstelling
Gödels tweede onvolledigheidsstelling houdt in dat de formele rekenkunde haar eigen consistentie niet kan bewijzen. Dat wil zeggen, de stelling  ( staat voor contradictie), kan niet bewezen worden binnen een gegeven consistent axiomatisch systeem.

Filosofische consequenties
Merk op dat de stelling heel algemeen is: ze zegt niet slechts dat bepaalde axiomatiseringen van de rekenkunde incompleet (of incorrect) zijn, maar dat alle axiomatiseringen dat zijn. Men zou een nieuw systeem kunnen maken dat  als axioma toevoegt, en dat is nog steeds consistent, maar Gödels stelling treedt prompt weer in werking en levert een nieuwe onbewijsbare en onweerlegbare stelling in het nieuwe systeem.

Merk tevens op dat de techniek van Gödelnummering werkt vanwege het feit dat het axiomastelsel in staat is uitspraken te doen over natuurlijke getallen. Doordat er via de nummering een één-op-één relatie bestaat tussen stellingen en natuurlijke getallen is het axiomastelsel ook in staat uitspraken te doen over zichzelf. Ofschoon dit volledigheid en flexibiliteit suggereert, geeft het eigenlijk aanleiding tot het bewijs dat het axiomastelsel juist niet volledig is. Deze ironische paradox (volledigheid die leidt tot onvolledigheid) wordt tot heden intensief bestudeerd door filosofen en logici.

De consequenties van de tweede onvolledigheidsstelling gaan zelfs nog verder: we zullen nooit in staat zijn te bewijzen dat de rekenkunde (en daarmee de wiskunde) consistent is. Als we de consistentie van de rekenkunde willen aantonen, hebben we een sterkere theorie nodig (zoals de verzamelingenleer). Deze kan echter ook haar eigen consistentie niet aantonen om dezelfde reden, enzovoort.

De eerste onvolledigheidsstelling van Gödel wordt soms ook gebruikt om te beredeneren dat mensen iets kunnen wat computers niet kunnen. In het argument van Lucas van J.R. Lucas wordt beredeneerd dat mensen wel de waarheid van een Gödelzin kunnen inzien terwijl een computer, een formeel systeem, de waarheid van zo'n zin niet kan bewijzen (of 'inzien'). 

Ook Douglas Hofstadter verwijst in zijn bekroonde boek Gödel, Escher, Bach naar deze filosofie.

Zie ook
 Beslissingsprobleem

Filosofie van de wiskunde
Wiskundige logica
Gödel
Paradox