Hoe het bewijs van Gödel werkt

Zijn onvolledigheidsstellingen maakten een einde aan de zoektocht naar een wiskundige 'theorie van alles'. Bijna een eeuw later zijn we nog steeds bezig met het begrijpen van de consequenties. Elk wiskundig systeem zal uitspraken bevatten die nooit bewezen kunnen worden.

Introductie

In 1931 bereikte de Oostenrijkse logicus Kurt Gödel een van de meest indrukwekkende intellectuele prestaties uit de geschiedenis. Wiskundigen uit die tijd zochten naar een solide fundament voor de wiskunde: een set basisfeiten, of axioma's, die zowel consistent was (nooit leidend tot tegenstrijdigheden) als compleet (dienend als bouwstenen voor alle wiskundige waarheden).

Maar Gödels schokkende onvolledigheidsstellingen, gepubliceerd toen hij pas 25 jaar oud was, maakten dat droombeeld kapot. Hij bewees dat elke set axioma's die je zou kunnen poneren als mogelijk fundament voor de wiskunde, onvermijdelijk onvolledig zal zijn; er zullen altijd ware feiten over getallen zijn die niet door die axioma's bewezen kunnen worden. Hij toonde ook aan dat geen enkele kandidaat-set van axioma's ooit haar eigen consistentie kan bewijzen.

Zijn onvolledigheidsstellingen betekenden dat er geen wiskundige 'theorie van alles' kan bestaan, geen unificatie van wat bewijsbaar is en wat waar is. Wat wiskundigen kunnen bewijzen hangt af van hun startaannames, niet van een fundamentele grondwaarheid waaruit alle antwoorden voortvloeien.

In de 89 jaar sinds Gödels ontdekking zijn wiskundigen precies op de soort onbeantwoordbare vragen gestuit die zijn stellingen voorspelden. Zo hielp Gödel zelf vaststellen dat de continuümhypothese (die gaat over de grootte van oneindigheid) onbeslisbaar is, net als het stopprobleem (halting problem), dat vraagt of een computerprogramma met een willekeurige input eeuwig zal draaien of uiteindelijk zal stoppen. Onbeslisbare vragen zijn zelfs in de natuurkunde naar voren gekomen, wat suggereert dat Gödeliaanse onvolledigheid niet alleen de wiskunde treft, maar — op een nog slecht begrepen manier — de realiteit zelf.

Hieronder volgt een vereenvoudigde, informele uiteenzetting van hoe Gödel zijn stellingen bewees.

Gödel-nummering

Gödels belangrijkste manoeuvre was om uitspraken over een systeem van axioma's te mappen op uitspraken binnen het systeem — dat wil zeggen, op uitspraken over getallen. Deze mapping stelt een systeem van axioma's in staat om op een coherente manier over zichzelf te spreken.

De eerste stap in dit proces is om elke mogelijke wiskundige uitspraak, of reeks uitspraken, te koppelen aan een uniek getal, genaamd een Gödel-nummer. De licht gewijzigde versie van het schema van Gödel, gepresenteerd door Ernest Nagel en James Newman in hun boek Gödel’s Proof (1958), begint met 12 basissymbolen die dienen als vocabulaire voor het uitdrukken van een set basisaxioma's.

Symbool	Gödel-nummer	Gebruikelijke betekenis
~	1	niet
$\lor$	2	of
$\supset$	3	als… dan…
$\exists$	4	er is een…
=	5	is gelijk aan
0	6	nul
s	7	de opvolger van
(	8	leesteken
)	9	leesteken
,	10	leesteken
+	11	plus
×	12	maal

Het symbool s ("opvolger van") biedt een manier om getallen te specificeren; ss0 verwijst bijvoorbeeld naar 2.

Vervolgens worden letters die variabelen representeren (beginnend met x, y en z) gekoppeld aan priemgetallen groter dan 12 (namelijk 13, 17, 19, …). Elke combinatie van deze symbolen en variabelen — elke rekenkundige formule of sequentie van formules die geconstrueerd kan worden — krijgt zo zijn eigen Gödel-nummer.

Voorbeeld: $0 = 0$ De drie symbolen in deze formule corresponderen met de Gödel-nummers 6, 5 en 6. Om deze reeks om te zetten in één uniek getal, neemt Gödel de eerste drie priemgetallen (2, 3 en 5), verheft elk tot de macht van het Gödel-nummer van het symbool op die positie, en vermenigvuldigt ze: $2^6 \times 3^5 \times 5^6 = 243.000.000$.

Deze mapping werkt omdat geen twee formules ooit hetzelfde Gödel-nummer zullen hebben; integers kunnen namelijk maar op één enkele manier ontbonden worden in priemfactoren. De enige manier om $243.000.000$ te decoderen is dus de formule $0 = 0$.

Gödel ging nog een stap verder: een wiskundig bewijs bestaat uit een sequentie van formules. Hij gaf elke sequentie van formules daarom ook een uniek Gödel-nummer. Hij gebruikt hiervoor opnieuw de lijst met priemgetallen (2, 3, 5, etc.) en verheft deze tot de macht van het Gödel-nummer van de formule op die positie in de sequentie.

Het aritmetiseren van metawiskunde

Het grote voordeel is dat zelfs uitspraken over rekenkundige formules — zogenaamde metawiskundige uitspraken — kunnen worden vertaald naar formules met hun eigen Gödel-nummers.

Neem bijvoorbeeld de formule $\sim(0 = 0)$, wat betekent "nul is niet gelijk aan nul". Deze formule is duidelijk onwaar, maar heeft wel een Gödel-nummer: $2^1 \times 3^8 \times 5^6 \times 7^5 \times 11^6 \times 13^9$. Omdat we voor alle formules (ook de onware) Gödel-nummers kunnen genereren, kunnen we zinvol over deze formules spreken door te spreken over hun Gödel-nummers.

Beschouw de uitspraak: "Het eerste symbool van de formule $\sim(0 = 0)$ is een tilde." Deze (ware) metawiskundige uitspraak vertaalt zich naar een uitspraak over het Gödel-nummer van de formule — namelijk dat de eerste exponent 1 is (het Gödel-nummer voor een tilde). Met andere woorden: onze uitspraak zegt dat $2^1 \times 3^8 \times 5^6 \times 7^5 \times 11^6 \times 13^9$ slechts één factor 2 heeft.

We kunnen deze laatste zin omzetten in een precieze rekenkundige formule die we met basissymbolen kunnen opschrijven (zie voetnoot). Deze formule heeft op zijn beurt weer een eigen Gödel-nummer.

Dit voorbeeld illustreert het kerninzicht van Gödel: typografische eigenschappen van lange ketens symbolen kunnen indirect maar perfect accuraat worden beschreven door te spreken over de eigenschappen van priemfactorisaties van grote gehele getallen. Ook metawiskundige uitspraken zoals "Er bestaat een sequentie van formules met Gödel-nummer x die de formule met Gödel-nummer k bewijst" (of kortweg: "De formule met Gödel-nummer k is bewijsbaar") kunnen worden omgezet in symbolen.

G zelf

Gödels extra inzicht was dat hij het eigen Gödel-nummer van een formule in diezelfde formule kon substitueren.

Om te zien hoe substitutie werkt, nemen we de formule $(\exists x)(x = sy)$. Dit betekent: "Er bestaat een variabele $x$ die de opvolger is van $y$" (of simpelweg: "$y$ heeft een opvolger"). Deze formule heeft een Gödel-nummer, dat we voor het gemak $m$ noemen.

Als we nu $m$ in de formule plaatsen in plaats van het symbool $y$, ontstaat er een nieuwe formule: $(\exists x)(x = sm)$, wat betekent "$m$ heeft een opvolger". Het Gödel-nummer van deze nieuwe formule noemen we $\text{sub}(m, m, 17)$, waarbij 17 het Gödel-nummer is van het symbool $y$.

Substitutie vormt de kern van het bewijs. Gödel overwoog een metawiskundige uitspraak in de trant van: "De formule met Gödel-nummer $\text{sub}(y, y, 17)$ kan niet worden bewezen." Deze uitspraak vertaalt zich naar een formule met een uniek Gödel-nummer, dat we $n$ noemen.

Vervolgens voert Gödel één laatste substitutie uit: hij vervangt elke $y$ in de vorige formule door het getal $n$. De nieuwe formule luidt nu: "De formule met Gödel-nummer $\text{sub}(n, n, 17)$ kan niet worden bewezen." Laten we deze formule G noemen.

Wat is het Gödel-nummer van G? Het blijkt precies $\text{sub}(n, n, 17)$ te zijn. Vanwege de uniciteit van priemfactorisatie zien we nu dat de formule waar G over spreekt, niets anders is dan G zelf. G beweert over zichzelf dat hij niet bewezen kan worden.

Kan G echter wel worden bewezen?

• Als G bewijsbaar zou zijn, zou er een sequentie formules moeten zijn die G bewijst. Maar dat is precies het tegenovergestelde van wat G beweert. In een consistent axiomatisch systeem kunnen tegenstrijdige uitspraken (G en $\sim\text{G}$) niet beide waar zijn.
• Daarom moet de waarheid van G onbeslisbaar zijn binnen het systeem.

Hoewel G onbeslisbaar is, is hij overduidelijk waar. G zegt immers: "De formule met Gödel-nummer $\text{sub}(n, n, 17)$ kan niet worden bewezen", en dat is precies wat we zojuist hebben vastgesteld! Omdat G waar is maar onbeslisbaar binnen het axiomatische systeem waarin hij is geconstrueerd, is dat systeem onvolledig.

Men zou kunnen denken dat je simpelweg een extra axioma kunt toevoegen om G te bewijzen en de paradox op te lossen. Maar Gödel toonde aan dat het uitgebreide systeem opnieuw toelaat om een nieuwe, ware formule $\text{G}'$ te construeren die niet bewezen kan worden binnen dat nieuwe, uitgebreide systeem. In de zoektocht naar een compleet wiskundig systeem kun je je eigen staart nooit vangen.

Geen bewijs van consistentie

Als we hebben geleerd dat een set axioma's onvolledig is als deze consistent is, dan is dat Gödels eerste onvolledigheidsstelling. De tweede — dat geen enkele set axioma's haar eigen consistentie kan bewijzen — volgt daar logisch uit.

Wat zou het betekenen als een set axioma's kon bewijzen dat ze nooit een tegenstrijdigheid zouden opleveren? Het zou betekenen dat er een sequentie formules bestaat die de formule bewijst die metawiskundig betekent: "Deze set axioma's is consistent". Volgens de eerste stelling zou deze set axioma's dan noodzakelijkerwijs onvolledig zijn.

Echter, "De set axioma's is onvolledig" is hetzelfde als zeggen: "Er is een ware formule die niet bewezen kan worden." Deze uitspraak is equivalent aan onze formule G. En we weten dat de axioma's G niet kunnen bewijzen.

Gödel creëerde hiermee een bewijs door contradictie: als een set axioma's haar eigen consistentie zou kunnen bewijzen, zouden we in staat zijn om G te bewijzen. Maar dat kunnen we niet. Daarom kan geen enkele set axioma's haar eigen consistentie bewijzen.

Gödels bewijs maakte een einde aan de zoektocht naar een consistent en compleet wiskundig systeem. De volledige betekenis van deze onvolledigheid is, zoals Nagel en Newman in 1958 schreven, nog steeds niet volledig doorgrond.

***

Voetnoot: Over de omzetting naar symbolen Voor wie nieuwsgierig is: de bewering dat "het eerste symbool een tilde is" luidt rekenkundig als volgt: "Er bestaat een geheel getal $x$ zodanig dat $x$ vermenigvuldigd met 2 gelijk is aan [de priemfactorisatie van de formule], en er bestaat geen enkel geheel getal $x$ zodanig dat $x$ vermenigvuldigd met 4 gelijk is aan [diezelfde factorisatie]."

De corresponderende formule is: $(\exists x)(x \times \text{ss}0 = \text{sss} \dots \text{sss}0) \cdot \sim(\exists x)(x \times \text{ssss}0 = \text{sss} \dots \text{sss}0)$

Hierbij staat $\text{sss} \dots \text{sss}0$ voor het aantal kopieën van het opvolgersymbool s dat overeenkomt met de waarde van de priemfactorisatie. Het symbool $\cdot$ betekent "en", wat een kortere notatie is voor $\sim(\sim p \lor \sim q)$.