Onvolledigheidsstellingen van Gödel
De onvolledigheidsstellingen van Gödel zijn twee stellingen over de beperkingen van formele systemen, met name de eerste-orde rekenkunde, beide bewezen door Kurt Gödel in 1931.
Inhoud |
[bewerk] Geschiedenis
Begin twintigste eeuw werden pogingen ondernomen om de gehele wiskunde in één enkele 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 1930 bewees Gödel zijn volledigheidsstelling: de standaardpredicatenlogica was volledig. Een jaar later publiceerde hij zijn onvolledigheidsstellingen in een artikel in het Monatshefte für Mathematik und Physik, getiteld "Über formal unendscheidbare 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 te moeilijk zou zijn. Die vrees bleek ongegrond.
[bewerk] 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 er 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.
[bewerk] 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 a van het systeem elk een uniek nummer na 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 Bew(X) af te leiden dat waar is, dan en slechts dan als X het Gödelgetal van een bewijsbare stelling is.
Vervolgens komt een truc, die 'diagonalisatie' wordt genoemd: Zij P(X) een willekeurig predicaat. We definiëren nu het predicaat DP(Y) als het predicaat "Y is het Gödelnummer van een formule F(X), en P(F(Y)) geldt". Pas dit nu toe op het predicaat 
. Dit levert een predicaat SU(X) op, dat in woorden zegt "dit getal is het Gödelnummer van een onbewijsbare stelling".
Bekijk nu de stelling SU(A), waar A het Gödelnummer van SU(X) is.
Neem aan dat het systeem correct is (en dus geen onware stellingen kan bewijzen), en dat we SU(A) kunnen bewijzen. Omdat SU(A) waar is, betekent dit dat A het Gödelnummer van een formule F(X) is waarvoor 
geldt. A is het Gödelnummer van SU(X), dus 
, dus SU(A) is niet bewijsbaar. Tegenspraak.
Omgekeerd, als we 
kunnen bewijzen, moet SU(A) dus niet waar zijn, waaruit we op gelijke wijze kunnen bewijzen dat Bew(SU(A)).
Conclusie is dat als het axiomatisch systeem correct is, SU(A) en beide niet bewijsbaar zijn, en het systeem dus niet volledig is.
Merk op dat er een sterke overeenkomst is met de leugenaarsparadox: SU(A) is een codering voor de uitspraak 'deze uitspraak kan niet bewezen worden', die een verwante is van de uitspraak 'deze uitspraak is niet waar'.
[bewerk] 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 onwaarheid), kan niet bewezen worden binnen een gegeven consistent axiomatisch systeem.
[bewerk] 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.
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.
