In 1931 heeft de Oostenrijkse logicus Kurt Gödel misschien wel een van de meest verbluffende intellectuele prestaties in de geschiedenis geleverd.
Mathematici van die tijd zochten naar een solide basis voor de wiskunde: een verzameling wiskundige basisfeiten, of axioma’s, die zowel consistent was – en nooit tot tegenstrijdigheden leidde – als compleet, en diende als de bouwstenen van alle wiskundige waarheden.
Maar Gödel’s schokkende onvolledigheidstheorema’s, gepubliceerd toen hij nog maar 25 jaar oud was, verpletterden die droom. Hij bewees dat elke verzameling axioma’s die je als mogelijke basis voor de wiskunde zou kunnen voorstellen, onvermijdelijk onvolledig zal zijn; er zullen altijd ware feiten over getallen zijn die niet met die axioma’s kunnen worden bewezen. Hij toonde ook aan dat geen enkele kandidaat-verzameling van axioma’s ooit haar eigen consistentie kan bewijzen.
Zijn onvolledigheidstheorema’s betekenden dat er geen wiskundige theorie van alles kan zijn, geen eenwording van wat bewijsbaar is en wat waar is. Wat wiskundigen kunnen bewijzen hangt af van hun uitgangspunten, niet van een fundamentele grondwaarheid waaruit alle antwoorden voortkomen.
In de 89 jaar sinds Gödels ontdekking zijn wiskundigen precies op het soort onbeantwoordbare vragen gestuit dat zijn stellingen voorspelden. Gödel zelf heeft bijvoorbeeld helpen vaststellen dat de continuüm-hypothese, die betrekking heeft op de grootte van het oneindige, onbeslisbaar is, evenals het halteringsprobleem, waarbij men zich afvraagt of een computerprogramma dat gevoed wordt met een willekeurige invoer eeuwig zal blijven draaien of uiteindelijk zal stoppen. Zelfs in de natuurkunde zijn onbeslisbare vragen gerezen, wat suggereert dat Gödeliaanse onvolledigheid niet alleen de wiskunde treft, maar – op de een of andere onbegrijpelijke manier – ook de werkelijkheid.
Hier volgt een vereenvoudigd, informeel overzicht van hoe Gödel zijn stellingen bewees.
Gödel Nummering
Gödel’s belangrijkste manoeuvre was om uitspraken over een systeem van axioma’s in kaart te brengen op uitspraken binnen het systeem – dat wil zeggen, op uitspraken over getallen. Dit in kaart brengen stelt een systeem van axioma’s in staat om overtuigend over zichzelf te praten.
De eerste stap in dit proces is om elke mogelijke wiskundige uitspraak, of reeks van uitspraken, in kaart te brengen in een uniek getal dat een Gödel getal wordt genoemd.
De enigszins aangepaste versie van Gödel’s schema, gepresenteerd door Ernest Nagel en James Newman in hun boek uit 1958, Gödel’s Proof, begint met 12 elementaire symbolen die dienen als vocabulaire voor het uitdrukken van een verzameling basisaxioma’s. Bijvoorbeeld, de uitspraak dat iets bestaat kan worden uitgedrukt door het symbool ∃, terwijl optellen wordt uitgedrukt door +. Belangrijk is dat het symbool s, dat “opvolger van” betekent, een manier biedt om getallen te specificeren; ss0, bijvoorbeeld, verwijst naar 2.
Deze twaalf symbolen krijgen dan de Gödel-nummers 1 tot en met 12 toegewezen.
| Constantteken | Gödelgetal | Uwelijke betekenis | ~ | 1 | niet |
| ∨ | 2 | of |
| ⊃ | 3 | als…dan… |
| ∃ | 4 | er is is een… |
| = | 5 | gelijk aan |
| 0 | 6 | nul |
| s | 7 | de opvolger van |
| ( | 8 | punctuatieteken |
| ) | 9 | punctuationeel teken |
| , | 10 | punctuationele teken |
| + | 11 | plus |
| × | 12 |
Volgende, letters die variabelen voorstellen, te beginnen met x, y en z, komen overeen met priemgetallen groter dan 12 (dat wil zeggen 13, 17, 19, …).
Dan krijgt elke combinatie van deze symbolen en variabelen – dat wil zeggen, elke rekenkundige formule of reeks formules die kan worden geconstrueerd – zijn eigen Gödel getal.
Bijv. 0 = 0. De drie symbolen van de formule komen overeen met de Gödel getallen 6, 5 en 6. Gödel moet deze rij van drie getallen veranderen in één uniek getal – een getal dat geen enkele andere rij van symbolen zal genereren. Daartoe neemt hij de eerste drie priemgetallen (2, 3 en 5), verhoogt ze elk tot het Gödel-getal van het symbool op dezelfde plaats in de rij, en vermenigvuldigt ze met elkaar. Zo wordt 0 = 0 26 × 35 × 56, ofwel 243.000.000.
De mapping werkt omdat geen twee formules ooit op hetzelfde Gödel-getal zullen uitkomen. Gödelgetallen zijn gehele getallen, en gehele getallen kunnen slechts op één manier in priemgetallen worden ontbonden. Dus de enige priemfactorisatie van 243.000.000 is 26 × 35 × 56, wat betekent dat er maar één mogelijke manier is om het Gödel getal te decoderen: de formule 0 = 0.
Gödel ging toen nog een stap verder. Een wiskundig bewijs bestaat uit een opeenvolging van formules. Dus gaf Gödel elke opeenvolging van formules ook een uniek Gödelnummer. In dit geval begint hij met de lijst van priemgetallen zoals voorheen – 2, 3, 5 enzovoort. Vervolgens verhoogt hij elk priemgetal tot het Gödel-getal van de formule op dezelfde plaats in de rij (2243.000.000 × …, als 0 = 0 bijvoorbeeld eerst komt) en vermenigvuldigt alles met elkaar.
Arithmetizing Metamathematics
Het echte voordeel is dat zelfs uitspraken over rekenkundige formules, die metamathematische uitspraken worden genoemd, zelf kunnen worden vertaald in formules met eigen Gödel-nummers.
Overweeg eerst de formule ~(0 = 0), wat betekent “nul is niet gelijk aan nul.” Deze formule is duidelijk onwaar. Toch heeft zij een Gödelgetal: 2 tot de macht 1 (het Gödelgetal van het symbool ~), vermenigvuldigd met 3 tot de macht 8 (het Gödelgetal van het “open haakjes”-symbool), enzovoort, wat 2¹ × 38 × 56 × 75 × 116 × 139 oplevert.
Omdat we Gödelgetallen kunnen genereren voor alle formules, zelfs valse, kunnen we zinnig over deze formules praten door het over hun Gödelgetallen te hebben.
Bedenk de uitspraak: “Het eerste symbool van de formule ~(0 = 0) is een tilde.” Deze (ware) metamathematische uitspraak over ~(0 = 0) vertaalt zich in een uitspraak over het Gödelgetal van de formule – namelijk dat de eerste exponent 1 is, het Gödelgetal voor een tilde. Met andere woorden, onze uitspraak zegt dat 2¹ × 38 × 56 × 75 × 116 × 139 slechts één factor 2 heeft. Als ~(0 = 0) met een ander symbool dan een tilde was begonnen, zou het Gödel-getal ten minste twee factoren 2 hebben. Dus, nauwkeuriger gezegd, 2 is een factor van 2¹ × 38 × 56 × 75 × 116 × 139, maar 22 is geen factor.
We kunnen de laatste zin omzetten in een precieze rekenkundige formule die we kunnen opschrijven* met elementaire symbolen. Deze formule heeft natuurlijk een Gödel-getal, dat we zouden kunnen berekenen door de symbolen ervan in kaart te brengen in machten van priemgetallen.
Dit voorbeeld, zo schrijven Nagel en Newman, “illustreert een zeer algemeen en diep inzicht dat de kern vormt van Gödels ontdekking: over typografische eigenschappen van lange reeksen symbolen kan op een indirecte maar volkomen nauwkeurige manier worden gesproken door in plaats daarvan te spreken over de eigenschappen van priemfactorisaties van grote gehele getallen.”
Omzetting in symbolen is ook mogelijk voor de metamathematische uitspraak: “Er bestaat een of andere reeks formules met Gödel-getal x die de formule met Gödel-getal k bewijst” – of, kort gezegd: “De formule met Gödel-getal k kan bewezen worden.” De mogelijkheid om dit soort uitspraken te “rekenen” zette de toon voor de coup.
G Itself
Gödels extra inzicht was dat hij het eigen Gödel-getal van een formule in de formule zelf kon substitueren, wat tot niet al te veel problemen leidde.
Om te zien hoe substitutie werkt, beschouw de formule (∃x)(x = sy). (Die luidt: “Er bestaat een variabele x die de opvolger is van y,” of, in het kort, “y heeft een opvolger.”) Zoals alle formules heeft ook deze formule een Gödel-getal – een groot geheel getal dat we m zullen noemen.
Nu voeren we m in de formule in in plaats van het symbool y. Dit vormt een nieuwe formule, (∃x)(x = sm), wat betekent: “m heeft een opvolger.” Hoe zullen we het Gödel-getal van deze formule noemen? Er zijn drie stukjes informatie over te brengen: We zijn begonnen met de formule die Gödel nummer m heeft. Daarin hebben we m vervangen door het symbool y. En volgens het eerder geïntroduceerde mappingschema heeft het symbool y het Gödel nummer 17. Laten we de nieuwe formule dus het Gödelnummer sub(m, m, 17) geven.
Substitutie vormt de crux van Gödels bewijs.
Hij overwoog een metamathematische uitspraak in de trant van “De formule met Gödelnummer sub(y, y, 17) kan niet bewezen worden.” Herinnerend aan de notatie die we zojuist hebben geleerd, is de formule met Gödel nummer sub(y, y, 17) de formule die wordt verkregen door de formule met Gödel nummer y (een onbekende variabele) te nemen en deze variabele y overal te substitueren waar een symbool staat waarvan het Gödel nummer 17 is (dat wil zeggen overal waar een y staat).
Dit wordt een beetje vreemd, maar toch kan onze metamathematische uitspraak – “De formule met Gödel nummer sub(y, y, 17) kan niet bewezen worden” – zeker vertaald worden in een formule met een uniek Gödel nummer. Laten we het n noemen.
Nu nog een laatste substitutieronde: Gödel maakt een nieuwe formule door het getal n overal waar een y in de vorige formule staat te substitueren. Zijn nieuwe formule luidt: “De formule met Gödel nummer sub(n, n, 17) kan niet bewezen worden.” Laten we deze nieuwe formule G noemen.
Natuurlijk heeft G een Gödel-getal. Wat is de waarde daarvan? Voorwaar, het moet sub(n, n, 17) zijn. Per definitie is sub(n, n, 17) het Gödelnummer van de formule die ontstaat door de formule met Gödelnummer n te nemen en n overal te vervangen door een symbool met Gödelnummer 17. En G is precies deze formule! Vanwege de uniciteit van priemfactorisatie zien we nu dat de formule waar G het over heeft niemand anders is dan G zelf.
G beweert van zichzelf dat hij niet bewezen kan worden.
Maar kan G wel bewezen worden? Zo ja, dan zou dat betekenen dat er een of andere reeks formules bestaat die de formule met Gödel-nummer sub(n, n, 17) bewijst. Maar dat is het tegengestelde van G, dat zegt dat zo’n bewijs niet bestaat. Tegengestelde uitspraken, G en ~G, kunnen niet allebei waar zijn in een consistent axiomatisch systeem. Dus de waarheid van G moet onbeslisbaar zijn.
Hoewel G onbeslisbaar is, is het duidelijk waar. G zegt: “De formule met Gödel-nummer sub(n, n, 17) kan niet bewezen worden,” en dat is precies wat wij gevonden hebben! Omdat G waar is, maar onbeslisbaar binnen het axiomatische systeem dat is gebruikt om het te construeren, is dat systeem onvolledig.
Je zou kunnen denken dat je gewoon een extra axioma kunt poneren, dat kunt gebruiken om G te bewijzen, en de paradox kunt oplossen. Maar dat is niet zo. Gödel liet zien dat het uitgebreide axiomatische systeem de constructie mogelijk maakt van een nieuwe, ware formule Gʹ (volgens een vergelijkbare blauwdruk als voorheen) die niet bewezen kan worden binnen het nieuwe, uitgebreide systeem. Bij het streven naar een compleet wiskundig systeem, kun je nooit je eigen staart vangen.
Geen bewijs van consistentie
We hebben geleerd dat als een verzameling axioma’s consistent is, deze onvolledig is. Dat is Gödel’s eerste onvolledigheidstheorema. De tweede – dat geen enkele verzameling axioma’s zijn eigen consistentie kan bewijzen – volgt gemakkelijk.
Wat zou het betekenen als een verzameling axioma’s kan bewijzen dat ze nooit een tegenspraak zal opleveren? Het zou betekenen dat er een opeenvolging van formules bestaat, opgebouwd uit deze axioma’s, die de formule bewijst die, metamathematisch, betekent: “Deze verzameling axioma’s is consistent.” Door de eerste stelling zou deze verzameling axioma’s dan noodzakelijkerwijs onvolledig zijn.
Maar “De verzameling 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.
Dus heeft Gödel een bewijs door tegenspraak gecreëerd: Als een verzameling axioma’s zijn eigen consistentie kon bewijzen, dan zouden we G kunnen bewijzen. Maar dat kunnen we niet. Daarom kan geen enkele verzameling axioma’s zijn eigen consistentie bewijzen.
Gödel’s bewijs maakte een einde aan de zoektocht naar een consistent, compleet wiskundig systeem. De betekenis van onvolledigheid “is niet volledig doorgrond”, schreven Nagel en Newman in 1958. Het is nog steeds waar.
* Voor de nieuwsgierigen: de stelling luidt: “Er bestaat een geheel getal x zodanig dat x vermenigvuldigd met 2 gelijk is aan 2¹ × 38 × 56 × 75 × 116 × 139, en er bestaat geen geheel getal x zodanig dat x vermenigvuldigd met 4 gelijk is aan 2¹ × 38 × 56 × 75 × 116 × 139.” De bijbehorende formule is:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
waarbij sss … sss0 staat voor 2¹ × 38 × 56 × 75 × 116 × 139 exemplaren van het opvolgsymbool s. Het symbool ⋅ betekent “en,” en is steno voor een langere uitdrukking in het fundamentele vocabulaire: p ⋅ q staat voor ~(~p ∨ ~q).
Dit artikel is overgenomen op Wired.com.