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 $a$ van het systeem elk een uniek nummer $n_{a}$ toe te kennen, en de uitspraak $abc\dots k$ (met $a,b,c,\dots k$ symbolen) vervolgens weer te geven met het getal $2^{n_{a}}\cdot 3^{n_{b}}\cdot 5^{n_{c}}\dots p^{n_{k}}$ (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 $D_{P}(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 $\neg Bew(X)$. 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 $\neg Bew(F(A))$ geldt. A is het Gödelnummer van $SU(X)$, dus $\neg Bew(SU(A))$, dus $SU(A)$ is niet bewijsbaar. Tegenspraak.

Omgekeerd, als we $\neg SU(A)$ 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 $\neg SU(A)$ 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 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 $\neg Bew(\bot )$ ($\bot$ 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 $\neg SU(A)$ 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

Bronnen, noten en/of referenties

• Weisstein, Eric W. Gödel's Incompleteness Theorem, MathWorld--A Wolfram Web Resource.