Hoe Gödel’s onvolledigheidsstellingen werken | Quanta Magazine

Zijn onvolledigheidsstellingen stelden de zoektocht naar een wiskundige Theory of Everything in de weg. Bijna een eeuw later krijgen we nog steeds de gevolgen onder ogen.

Een artikel van

Natalie Wolchover, senior writer/editor

Lees op Quanta Magazine


Martin Knops:

“”

In 1931 behaalde de Oostenrijkse logicus Kurt Gödel een van de meest verbluffende intellectuele prestaties uit de geschiedenis.

Wiskundigen uit die tijd zochten naar een solide basis voor wiskunde: een reeks wiskundige basisfeiten of axioma’s, die zowel consistent waren – nooit tot tegenstrijdigheden leidden – als compleet, en die de bouwstenen waren van alle wiskundige waarheden.

Maar Gödels schokkende onvolledigheidsstellingen, gepubliceerd toen hij nog maar 25 was, verpletterden die droom. Hij bewees dat elke reeks axioma’s die je zou kunnen stellen als een mogelijke basis voor wiskunde onvermijdelijk onvolledig zal zijn; er zullen altijd ware feiten zijn over getallen die niet kunnen worden bewezen door die axioma’s. Hij toonde ook aan dat geen enkele reeks axioma’s ooit zijn eigen consistentie kan bewijzen. “”

Hieronder volgt de Nederlandse vertaling van het artikel:


Elk wiskundig systeem heeft enkele verklaringen die nooit kunnen worden bewezen.

In 1931 behaalde de Oostenrijkse logicus Kurt Gödel een van de meest verbluffende intellectuele prestaties uit de geschiedenis.

Wiskundigen uit die tijd zochten naar een solide basis voor wiskunde: een reeks wiskundige basisfeiten of axioma’s, die zowel consistent waren – nooit tot tegenstrijdigheden leidden – als compleet, en die de bouwstenen waren van alle wiskundige waarheden.

Maar Gödels schokkende onvolledigheidsstellingen, gepubliceerd toen hij nog maar 25 was, verpletterden die droom. Hij bewees dat elke reeks axioma’s die je zou kunnen stellen als een mogelijke basis voor wiskunde onvermijdelijk onvolledig zal zijn; er zullen altijd ware feiten zijn over getallen die niet kunnen worden bewezen door die axioma’s. Hij toonde ook aan dat geen enkele reeks axioma’s ooit zijn eigen consistentie kan bewijzen.

Zijn onvolledigheidsstellingen betekenden dat er niet van alles een wiskundige theorie kan bestaan, geen unificatie van wat kan worden bewezen en wat waar is. Wat wiskundigen kunnen bewijzen, hangt af van hun uitgangspunten en niet van enige fundamentele grondwaarheid waaruit alle antwoorden voortkomen.

In de 89 jaar sinds Gödel’s ontdekking stuitten wiskundigen op het soort onbeantwoordbare vragen die zijn stellingen voorspelden. Zo heeft Gödel zelf geholpen vast te stellen dat de continuümhypothese, die betrekking heeft op de grootte van oneindigheid, niet te ontcijferen is, evenals het stopprobleem, dat vraagt of een computerprogramma dat wordt gevoed met een willekeurige invoer voor altijd zal lopen of uiteindelijk zal stoppen. Er zijn zelfs onbesliste vragen gerezen in de natuurkunde, wat suggereert dat Gödeliaanse onvolledigheid niet alleen de wiskunde aantast, maar – op een of andere slecht begrepen manier – de werkelijkheid.

Hier is een vereenvoudigd, informeel overzicht van hoe Gödel zijn stellingen bewees.

Gödel nummering

Gödels belangrijkste manoeuvre was om uitspraken over een systeem van axioma’s toe te wijzen aan uitspraken binnen het systeem, dat wil zeggen om uitspraken over getallen. Door deze mapping kan een systeem van axioma’s overtuigend over zichzelf praten.

De eerste stap in dit proces is om elke mogelijke wiskundige verklaring of reeks verklaringen toe te wijzen aan een uniek nummer dat een Gödel-nummer wordt genoemd.

De licht gewijzigde 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 reeks basisaxioma’s. De verklaring dat er iets bestaat, kan bijvoorbeeld worden uitgedrukt door het symbool ∃, terwijl toevoeging wordt uitgedrukt door +. Belangrijk is dat het symbool s, dat “opvolger van” aangeeft, een manier geeft om getallen te specificeren; ss0 verwijst bijvoorbeeld naar 2.

Deze twaalf symbolen krijgen dan de Gödel-nummers 1 tot en met 12 toegewezen.

Constant sign Gödel number Usual Meaning
~ 1 not
2 or
3 if…then…
4 there is an…
= 5 equals
0 6 zero
s 7 the successor of
( 8 punctuation mark
) 9 punctuation mark
, 10 punctuation mark
+ 11 plus
× 12 times

Vervolgens worden letters die variabelen vertegenwoordigen, beginnend met x, y en z, toegewezen aan priemgetallen groter dan 12 (dat wil zeggen 13, 17, 19, …).

Vervolgens 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-nummer.

Overweeg bijvoorbeeld 0 = 0. De drie symbolen van de formule komen overeen met Gödel-nummers 6, 5 en 6. Gödel moet deze reeks van drie cijfers veranderen in één uniek nummer – een nummer dat geen enkele andere reeks symbolen zal genereren. Om dit te doen, neemt hij de eerste drie priemgetallen (2, 3 en 5), verhoogt ze elk tot het Gödel-nummer van het symbool op dezelfde positie in de reeks en vermenigvuldigt ze samen. Dus 0 = 0 wordt 26 × 35 × 56 of 243.000.000.

De mapping werkt omdat geen twee formules ooit met hetzelfde Gödel-nummer zullen eindigen. Gödel-getallen zijn gehele getallen en gehele getallen spelen slechts op één manier een rol bij priemgetallen. 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 reeks formules. Dus gaf Gödel elke reeks formules ook een uniek Gödel-nummer. In dit geval begint hij met de lijst met priemgetallen zoals voorheen – 2, 3, 5 enzovoort. Vervolgens verhoogt hij elk priemgetal tot het Gödel-nummer van de formule op dezelfde positie in de reeks (2243.000.000 × … als bijvoorbeeld 0 = 0 als eerste komt) en vermenigvuldigt alles samen.

Rekenkundige metamathematica

De echte zegen is dat zelfs uitspraken over rekenkundige formules, metamathematische uitspraken genoemd, zelf kunnen worden vertaald in formules met eigen Gödel-getallen.

Overweeg eerst de formule ~ (0 = 0), wat betekent “nul is niet gelijk aan nul”. Deze formule is duidelijk onjuist. Niettemin heeft het een Gödel-nummer: 2 verhoogd tot de macht 1 (het Gödel-nummer van het symbool ~), vermenigvuldigd met 3 verhoogd tot de macht 8 (het Gödel-nummer van het “open haakje” -symbool), enzovoort , wat 2 × 38 × 56 × 75 × 116 × 139 oplevert.

Omdat we Gödel-nummers kunnen genereren voor alle formules, zelfs valse, kunnen we verstandig over deze formules praten door over hun Gödel-nummers te praten.

Beschouw de uitspraak: “Het eerste symbool van de formule ~ (0 = 0) is een tilde.” Deze (echte) metamathematische verklaring over ~ (0 = 0) vertaalt zich in een verklaring over het Gödel-nummer van de formule – namelijk dat de eerste exponent ervan 1 is, het Gödel-nummer voor een tilde. Met andere woorden, onze verklaring zegt dat 2 × 38 × 56 × 75 × 116 × 139 slechts een enkele factor van 2 heeft. Was ~ (0 = 0) begonnen met een ander symbool dan een tilde, dan zou zijn Gödel-nummer minstens twee factoren van 2. Meer precies, 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 rekenformule die we kunnen opschrijven * met elementaire symbolen. Deze formule heeft natuurlijk een Gödelgetal, dat we konden berekenen door de symbolen ervan in kaart te brengen op krachten van priemgetallen.

Dit voorbeeld, schreven Nagel en Newman, “illustreert een zeer algemeen en diep inzicht dat ten grondslag ligt aan de ontdekking van Gödel: typografische eigenschappen van lange ketens van symbolen kunnen op een indirecte maar perfect nauwkeurige manier worden besproken door in plaats daarvan te praten over de eigenschappen van priemfactoren van grote gehele getallen. ‘

Conversie in symbolen is ook mogelijk voor de metamathematische verklaring: “Er bestaat een reeks formules met Gödel nummer x die de formule bewijst met Gödel nummer k” – of kort gezegd “De formule met Gödel nummer k kan worden bewezen.” De mogelijkheid om dit soort uitspraken te ‘rekenen’ vormde het toneel voor de staatsgreep.

G zelf

Het extra inzicht van Gödel was dat hij het eigen Gödel-nummer van een formule in de formule zelf kon vervangen, waardoor de problemen eindeloos waren.

Bekijk de formule (∃x) (x = sy) om te zien hoe vervanging werkt. (Er staat: “Er bestaat een variabele x die de opvolger is van y”, of, kort gezegd, “y heeft een opvolger.”) Zoals alle formules heeft het een Gödel-nummer – een groot geheel getal noemen we gewoon m .

Laten we nu m introduceren in de formule in plaats van het symbool y. Dit vormt een nieuwe formule, (∃x) (x = sm), wat betekent: “m heeft een opvolger.” Hoe noemen we het Gödel-nummer van deze formule? Er zijn drie soorten informatie om over te brengen: We zijn begonnen met de formule met Gödel nummer m. Daarin hebben we m vervangen door het symbool y. En volgens het eerder geïntroduceerde kaartschema heeft het symbool y het Gödel nummer 17. Dus laten we de Gödel nummer sub van de nieuwe formule aanduiden (m, m, 17).

Vervanging vormt de kern van het bewijs van Gödel.

Hij overwoog een metamathematische verklaring in de trant van “De formule met Gödel-getallen sub (y, y, 17) kan niet worden bewezen.” Herinnerend aan de notatie die we zojuist hebben geleerd, is de formule met Gödel-nummer sub (y, y, 17) degene die wordt verkregen door de formule te nemen met Gödel-nummer y (een onbekende variabele) en deze variabele y te vervangen overal waar er een symbool is waarvan het Gödel-nummer is 17 (dat wil zeggen, overal waar ay is).

Het wordt trippy, maar toch, onze metamathematische verklaring – “De formule met Gödel-nummer sub (y, y, 17) kan niet worden bewezen” – zal zich zeker vertalen in een formule met een uniek Gödel-nummer. Laten we het n noemen.

Nu nog een laatste vervangingsronde: Gödel maakt een nieuwe formule door het getal n overal in de vorige formule te vervangen door een y. Zijn nieuwe formule luidt: “De formule met Gödel-getallen sub (n, n, 17) kan niet worden bewezen.” Laten we deze nieuwe formule G noemen


Kurt Gödel als student in Wenen. Hij publiceerde zijn onvolledigheidsstellingen in 1931, een jaar na zijn afstuderen.

Kurt Gödel Papers, het Shelby White en Leon Levy Achives Center, Institute for Advanced Study


G heeft natuurlijk een Gödel-nummer. Wat is de waarde ervan? Kijk en zie, het moet sub zijn (n, n, 17). Sub (n, n, 17) is per definitie het Gödel-nummer van de formule die resulteert uit het nemen van de formule met Gödel-nummer n en het vervangen van n overal waar er een symbool is met Gödel-nummer 17. En G is precies deze formule! Vanwege het unieke karakter van priemfactoren, zien we nu dat de formule waar G het over heeft niets anders is dan G zelf.

G stelt zelf dat het niet kan worden bewezen.

Maar kan G worden bewezen? Als dat zo is, zou dit betekenen dat er een reeks formules is die de formule bewijst met Gödel nummer sub (n, n, 17). Maar dat is het tegenovergestelde van G, dat zegt dat zo’n bewijs niet bestaat. Tegenovergestelde verklaringen, G en ~ G, kunnen niet allebei waar zijn in een consistent axiomatisch systeem. Dus de waarheid van G moet onduidelijk zijn.

Hoewel G onbeslist is, is het duidelijk waar. G zegt: “De formule met Gödel-nummer sub (n, n, 17) kan niet worden bewezen”, en dat is precies wat we hebben vastgesteld! Aangezien G waar is en toch onbeslisbaar binnen het axiomatische systeem dat werd gebruikt om het te construeren, is dat systeem onvolledig.

Je zou kunnen denken dat je gewoon wat extra axioma kunt gebruiken, het kunt gebruiken om G te bewijzen en de paradox kunt oplossen. Maar dat kan niet. Gödel toonde aan dat het verbeterde axiomatische systeem de constructie mogelijk maakt van een nieuwe, echte formule Gʹ (volgens een vergelijkbare blauwdruk als voorheen) die niet kan worden bewezen binnen het nieuwe, verbeterde 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 set axioma’s consistent is, deze onvolledig is. Dat is de eerste onvolledigheidsstelling van Gödel. De tweede – dat geen enkele reeks axioma’s zijn eigen consistentie kan bewijzen – volgt gemakkelijk.

Wat zou het betekenen als een stel axioma’s zou kunnen bewijzen dat het nooit een tegenspraak zal opleveren? Het zou betekenen dat er uit deze axioma’s een reeks formules bestaat die de formule bewijst die metamathematisch betekent: “Deze set axioma’s is consistent.” Volgens de eerste stelling zou deze reeks axioma’s dan noodzakelijkerwijs onvolledig zijn.

Maar “De reeks axioma’s is onvolledig” is hetzelfde als te zeggen: “Er is een echte formule die niet kan worden bewezen.” Deze verklaring komt overeen met onze formule G. En we weten dat de axioma’s G. niet kunnen bewijzen.

Dus Gödel heeft een tegenstrijdig bewijs gemaakt: als een reeks axioma’s zijn eigen consistentie zou kunnen bewijzen, dan zouden we G. kunnen bewijzen. Maar dat kunnen we niet. Daarom kan geen enkele reeks axioma’s zijn eigen consistentie bewijzen.

Gödel’s bewijs doodde de zoektocht naar een consistent, compleet wiskundig systeem. De betekenis van onvolledigheid ‘is niet volledig doorgrond’, schreven Nagel en Newman in 1958. Het blijft vandaag de dag waar.


*Voor de nieuwsgierigen luidt de verklaring: “Er bestaat een geheel getal x zodat x vermenigvuldigd met 2 gelijk is aan 2 × 38 × 56 × 75 × 116 × 139, en er bestaat geen geheel getal x zodat x vermenigvuldigd met 4 is gelijk aan 2 × 38 × 56 × 75 × 116 × 139. ” De bijbehorende formule is:

(x) (x × ss0 = sss … sss0) ~ (x) (x × ssss0 = sss … sss0)

waar sss… sss0 staat voor 2 × 38 × 56 × 75 × 116 × 139 exemplaren van het opvolgersymbool s. Het symbool betekent “en” en is een afkorting voor een langere uitdrukking in de fundamentele woordenschat: p q staat voor ~ (~ p ~ q). [Terug naar artikel.]

Voor de nieuwsgierigen luidt de verklaring: “Er bestaat een geheel getal x zodat x vermenigvuldigd met 2 gelijk is aan 2 × 38 × 56 × 75 × 116 × 139, en er bestaat geen geheel getal x zodat x vermenigvuldigd met 4 is gelijk aan 2 × 38 × 56 × 75 × 116 × 139. ” De bijbehorende formule is:

(x) (x × ss0 = sss … sss0) ~ (x) (x × ssss0 = sss … sss0)

waar sss… sss0 staat voor 2 × 38 × 56 × 75 × 116 × 139 exemplaren van het opvolgersymbool s. Het symbool betekent “en” en is een afkorting voor een langere uitdrukking in de fundamentele woordenschat: p q staat voor ~ (~ p ~ q).


RELATED:


  1. Does Time Really Flow? New Clues Come From a Century-Old Approach to Math.
  2. Mathematicians Measure Infinities and Find They’re Equal
  1. A Fight to Fix Geometry’s Foundations

Geef een reactie