Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Kurt Gödel en zijn onvolledigheidsstelling


In Algemeen,Geschiedenis, door wiskundemeisjes

Godel

Vandaag is de honderdste geboortedag van Kurt Gödel (1906 - 1978). Ik ga vandaag niets over zijn leven schrijven, want informatie daarover kun je bijvoorbeeld lezen in zijn In Memoriam uit The Times of een moderner artikel van Christian Jongeneel.

Gödel is vooral bekend om zijn onvolledigheidsstelling. Die stelling heeft betrekking op het logische bouwsel van axioma's en stellingen dat de wiskunde is. De wiskunde is gebaseerd op axioma's, de fundamenten van de wiskunde. De axioma's zijn beweringen die je aanneemt. Door middel van de regels van de logica kun je uit die axioma's stellingen afleiden. Een stelling is dus een bewering waarvoor een bewijs, zo'n logische afleiding, is gevonden. De onvolledigheidsstelling is dus eigenlijk een meta-stelling: het is een wiskundige stelling die tegelijk iets zegt over de wiskunde zelf als formele taal.

De belangrijkste eis die wiskundigen stellen aan dit formele systeem is dat het consistent moet zijn. Dat houdt in dat in zo'n systeem alleen ware beweringen bewezen mogen kunnen worden, oftewel: als een bewering niet waar is, mag hij niet bewijsbaar zijn.

De wiskundigen uit het begin van de twintigste eeuw, bijvoorbeeld Russell en Hilbert, probeerden de hele wiskunde op die manier om te toveren tot een formele taal. Hun ultieme hoop was dat het mogelijk zou zijn om in zo'n consistent systeem alle ware beweringen ook daadwerkelijk te bewijzen.

Deze hoop werd door Gödel in 1931 de grond in geboord. Hij bewees toen namelijk zijn onvolledigheidsstelling: als je een voldoende sterk, consistent formeel systeem hebt, met de regels van de logica, dan bestaan er altijd beweringen die wel waar zijn, maar niet binnen dit systeem te bewijzen zijn! ("Voldoende sterk" betekent hier dat het systeem minstens de rekenkunde moet omvatten, wat voor een wiskundig systeem natuurlijk niet teveel gevraagd is.)

Het idee van het bewijs is gebaseerd op zelfverwijzing. Gödel is er op een slimme manier in geslaagd om binnen het systeem de volgende bewering te formuleren: "Deze bewering is onbewijsbaar". Nu zijn er natuurlijk twee mogelijkheden. De eerste mogelijkheid is dat de bewering onwaar is. Maar dan is de bewering niet onbewijsbaar, dus bewijsbaar. Dan hebben we een bewering gevonden die onwaar is en toch bewijsbaar! Maar dat is in tegenspraak met de consistentie van ons formele systeem. Deze mogelijkheid valt dus af.

De enige andere mogelijkheid is dat de bewering waar is. Maar nu volgt natuurlijk dat de bewering onbewijsbaar is. Het systeem bevat dus minstens één bewering die waar is, maar niet bewijsbaar. Omdat je dit in elk dergelijk formeel systeem kunt doen, is bewezen dat al die systemen onvolledig zijn.

Voor de wiskundige praktijk heeft de onvolledigheidsstelling veel minder gevolgen dan je misschien zou verwachten. Er is nog nooit een dergelijke zin gevonden die niet speciaal als voorbeeld geconstrueerd is met behulp van die zelfverwijzing. Dat komt natuurlijk ook omdat het in principe niet zo makkelijk is om van een bewering wel te weten dat ze waar is, terwijl er geen bewijs bestaat...

(Jeanine)

22 reacties op “Kurt Gödel en zijn onvolledigheidsstelling”

  1. Steven:

    vraagje: als een bewering NIET waar is, moet dat toch ook bewezen kunnen worden?

  2. Jeanine:

    @ Steven: Jazeker, maar dat doe je òf door de ontkenning van die bewering te bewijzen, òf door te bewijzen dat als je aanneemt dat die bewering waar is, een tegenspraak ontstaat binnen je systeem (met andere woorden: als je die bewering aanneemt dan ontstaat er een andere bewering die je kunt bewijzen, maar waarvan je de ontkenning ook kunt bewijzen, dus dan is je systeem inconsistent). In beide gevallen volgt dan dat je bewering niet waar kan zijn.

    (In feite komen deze twee manieren om te bewijzen dat iets niet waar is op hetzelfde neer: je gebruikt dat een bewering en haar ontkenning niet allebei bewijsbaar mogen zijn.)

  3. Camiel:

    How many light bulbs does it take to change a light bulb?

  4. Camiel:

    ... 1, but only if it knows it's own gödel number.

    Ik snap die 'binnen het systeem' in je stuk niet zo goed, maar ik ben dan ook een leek.
    Als je dingen zegt *over* wiskunde en zelfs bewijst, dan zit je toch in een hogere laag, een soort meta-wiskunde? Uit dat onleuke lightbulb-grapje begreep ik dat een Turing machine de (on-)waarheid van Gödel niet kan bewijzen tenzij iemand hem zijn Gödel-nummer verklapt. Dat sterkt me in de opvatting dat de afleiding van Gödel inderdaad op een hoger niveau plaatsvind. Is dat nog wel binnen het systeem?
    De bewering 'Deze bewering is onbewijsbaar' bevat tenslotte ook meerdere niveaus van taal en metataal, dat is juist de reden voor de logische taal van Frege/Russel/Hilbert, om die niveaus zichtbaar te maken en dit soort paradoxen te voorkomen (of: te laten zien dat dit soort paradoxen een foutje zijn dat op de verwarring van niveaus berust).

    Ik heb Ionica al eens gemaild dat ik een hekel heb aan Gödel en dat ik voorstel een nieuwe, fijne consistente wiskunde te beginnen. Want onbewijsbare stellingen zijn tenslotte alleen maar onesthetisch.

  5. Jeanine:

    @ Camiel: Dat onbewijsbare maar wel ware beweringen niet zo fijn zijn, was inderdaad ook voor veel wiskundigen uit die tijd een reden om niet zo blij te zijn met Gödels bewijs. Maar hij heeft bewezen dat zo'n wiskunde zoals veel mensen graag zouden zien jammer genoeg niet bestaat (als je tenminste wil dat je wiskunde consistent is en dat je erin kan rekenen. Je kan ook ophouden na het definiëren van de nul en de andere getallen maar vergeten, maar ook daar worden wiskundigen niet gelukkig van).

    De kracht van Gödels bewijs is dat hij liet zien dat het, hoe tegen-intuïtief ook, inderdaad mogelijk is om binnen je systeem uitspraken over je systeem te doen. Dat is waarom het zo'n briljant bewijs is.

    De bewering "Deze bewering is onbewijsbaar" kun je natuurlijk niet direct formuleren binnen je systeem, daar moet je wel echt wat voor doen. De bewering ziet er veel ingewikkelder uit in wiskundige termen. De Gödelgetallen waar jij het over hebt heb je nodig voor de zelfreferentie.

  6. Camiel:

    Ik ga dat boek van Hofstädter nog maar eens uitlezen denk ik. Of een avondje wikipedia doorlezen.

    Volgende week: Camiel trekt ten strijde tegen de quantummechanica! Want lieve katjes zijn òf dood, òf levend, maar niet allebei!

  7. Camiel:

    Dirk van Delft schrijft over Godel en zijn stelling in de Wetenschapsbijlage van het NRC van afgelopen zaterdag, 13 mei.

  8. Vincent:

    Probeer ook eens het scoop-artikel over de onvolledigheidsstelling:

    http://www.science.uva.nl/student/scoop/artikels/Scoop%202003%20Okt%2021-28%20Godel.pdf

  9. Vincent:

    trouwens, volgens mij is het niet zo heel moeilijk om voorbeelden van ware maar onbewijsbare uitspraken te geven zolang je maar een heel klein axiomastelseltje hanteert. Ik geloof dat het mogelijk moet zijn alle getallen te definieren zonder het bestaan van oneindige verzamelingen aan te nemen. Het kan dan onmogelijk zijn om uitspaken van het type "alle getallen hebben die-en-die eigenschap" in een keer te bewijzen, maar voor ieder getal dat je uitkiest blijkt het dat het die eigenschap wel degelijk heeft (mits je je eigenschap slim kiest).

    Een voorbeeld is geloof ik (maar nu betreden we het domein van de speculatie en wilde geruchten) het volgende:

    neem een getal en schrijf het binair.

    Trek 1 af en schrijf de uitkomst weer binair.

    Maak hiervan een groter getal door de cijfers te interpreteren in het drietallig stelsel.

    Trek van dit grotere getal weer 1 af en schrijf de uitkomst nog steeds drietallig.

    Maak nu een groter getal door de cijfers die je net hebt opgeschreven als een getal in het viertalligstelsel te interpreteren

    Trek weer 1 af etc.

    Mijn bewering is nu: uiteindelijk kom je altijd uit op 0.

    Voorbeeld:
    111_2 (7 in normale mensen taal) wordt:
    110_2 (6 in normale mensentaal) wordt:
    110_3 (13 in normale mensentaal) wordt:
    102_3 (12 in normale mensentaal) wordt:
    102_4 (18 in normale mensentaal) wordt:
    101_4 (17 in normale mensentaal) wordt:
    101_5 (26 in normale mensentaal) wordt:
    100_5 (25 in normale mensentaal) wordt:
    100_6 (36 in normale mensentaal) wordt:
    55_6 (35 in normale mensentaal) wordt:
    55_7 (40 in normale mensentaal) wordt:
    54_7 (39 in normale mensentaal) wordt:
    54_8 (44 in normale mensentaal) wordt:
    53_8 (43 in normale mensentaal) wordt:
    ...
    50_12 (60 in normale mensentaal) wordt:
    4(11)_12 (59 in normale mensentaal)
    4(11)_13 (63 in normale mensentaal)

    etc
    etc
    etc

    Het is een lange weg omdat in het begin de sprongen omhoog veel groter zijn dan de 1 omlaag, maar de aanhouder wint.

    Als je wel gelooft in het bestaan van oneindige verzamelingen is er een eenvoudig bewijs dat het voor alle begingetallen goed gaat, maar ik heb nooit een bewijs gezien dat met bijv. inductie werkt.

    Iemand een idee?

    Natuurlijk kun je het bestaan van oneindige verzamelingen aan je axioma's toevoegen en dan moet je weer een nieuw voorbeeld van een ware maar niet bewijsbare stelling verzinnen. De kracht van Goedels bewijs is dat hij het voor alle axiomastelsels in een keer doet.

  10. Jasper:

    Overigens is het bewijs van Gödel ver reikender dan alleen de wiskunde. Het betreft ieder voldoende sterk consistent formeel systeem. Hoewel in de vorige eeuw logica en wiskunde bijna identiek werden, een consequentie van de PM van Hilbert en Russel, zijn zij dat niet.
    Overigens is de gelijkstelling van logica aan wiskunde een bewijs voor de kracht van mathematici en de zwakte van logici, maar dat is een ander verhaal

  11. Geert:

    Misschien een vitterijtje, maar 'consistent' betekent voor zover ik weet dat het systeem nooit zowel een uitspraak als haar ontkenning kan bewijzen; m.a.w. er zijn geen contradicties bewijsbaar binnen het systeem.

    De eigenschap dat een systeem enkel ware beweringen kan produceren, wordt 'betrouwbaarheid' (E: 'soundness') genoemd.

  12. Joop Theunissen:

    oneindige verzameling is een wanbwgrip, het is een taalverkrachting. Wasnt wat is een verzameling? Antwoord: het resultaat van verzamelen. En zo'n resultaat kan alleen maar eindig zijn. Zolang je aan het verzamelen bent bestaat het resultaat niet. Het begrip oneindig of oneindigen behoort niet tot de verzameling zelf.
    Joop Theunissen

  13. Marco:

    @Joop Theunissen: Als je onder een `verzameling' het resultaat van het woord `verzamelen' verstaat, dan zal een oneindige verzameling natuurlijk niet bestaan. Maar er is ook het wiskundige begrip `verzameling', wat een soort basisbegrip is in de wiskunde. Als voorbeelden van verzamelingen kan je dan denken aan de verzameling van alle gehele getallen. Deze verzameling bevat oneindig veel getallen.

  14. Arno van Asseldonk:

    @Joop Theunissen: In de wiskunde verstaan we onder een verzameling een aantal bij elkaar genomen of gedachte objecten. Deze objecten noemen we de elementen van de desbetreffende verzameling. Het aantal elementen van een verzameling noemen we het kardinaalgetal van deze verzameling.
    Als je het begrip verzameling uitsluitend in de alledaagse betekenis van het woord opvat, kan een verzameling inderdaad alleen maar eindig zijn omdat zo'n verzameling slechts een eindig aantal elementen bevat, maar als je het begrip verzameling in de strikt wiskundige betekenis van het woord opvat, dan bestaan er naast eindige verzamelingen ook oneindige verzamelingen, ofwel verzamelingen met een oneindig aantal elementen. De verzameling van de natuurlijke getallen, dus de verzameling getallen 1, 2, 3,... is in dat verband een bekend voorbeeld.
    Zoals ik al aangaf noemen we aantal elementen van een verzameling het kardinaalgetal van deze verzameling. Als het aantal elementen van zo'n verzameling eindig is, zeggen we dat zo'n verzameling een finiet kardinaalgetal heeft. Zo zal een verzameling met 4 elementen het finiete kardinaalgetal 4 hebben.
    Als het aantal elementen van zo'n verzameling
    oneindig is, zoals bij de verzameling natuurlijke getallen, zeggen we dat zo'n verzameling een transfiniet kardinaalgetal heeft.
    Als 2 verzamelingen hetzelfde kardinaalgetal hebben, en dus hetzelfde aantal elementen hebben, zeggen we dat deze verzamelingen gelijkmachtig zijn. Je kunt dan ieder element van de ene verzameling koppelen aan ieder element van de andere verzameling via een zogenaamde een-op-een-relatie.
    Wanneer we naast de natuurlijke getallen ook nog het getal 0 en de negatieve gehele getallen -1, -2, -3,... erbij nemen krijgen we de verzameling gehele getallen, en als we de verzameling nemen van alle gebroken getallen, ofwel alle getallen van de vorm a/b, waarbij a en b gehele getallen zijn en b niet 0 is, dan krijgen we de verzameling rationale getallen.
    Het blijkt nu dat de verzameling gehele getallen en de verzameling rationale getallen hetzelfde aantal elementen hebben als de natuurlijke getallen. Ze zijn dus oneindige verzamelingen die gelijkmachtig zijn met de verzameling natuurlijke getallen. We noemen een oneindige verzameling die gelijkmachtig is met de verzameling natuurlijke getallen een aftelbare verzameling. De verzameling gehele getallen en de verzameling rationale getallen zijn dus aftelbaar, zoals dat heet. Aan ieder element van een aftelbare verzameling kan dus via een een-op-een-relatie een natuurlijk getal worden gekoppeld, en omgekeerd. Wanneer het niet mogelijk is om aan ieder element van een oneindige verzameling via een een-op-een-relatie een natuurlijk getal te koppelen, en ook niet omgekeerd, noemen we zo'n oneindige verzameling een overaftelbare verzameling. Een voorbeeld van zo'n overaftelbare verzameling is de verzameling oneindige decimale breuken tussen 0 en 1. Deze verzameling is gelijkmachtig met de verzameling reële getallen. De verzameling reële getallen bevat naast de rationale getallen de irrationale getallen, ofwel de getallen die niet als een rationaal getal kunnen worden geschreven, zoals bijvoorbeeld het getal pi.
    Een overaftelbare verzameling is weliswaar ook een oneidige verzameling, maar met meer elementen dan een aftelbare verzameling, dus een overaftelbare verzameling heeft meer elementen dan de verzameling natuurlijke getallen. We zien dus dat er niet alleen diverse oneindige verzamelingen bestaan, maar dat er zelfs oneindige verzamelingen met een verschillend (transfiniet) kardinaalgetal kunnen bestaan, en het blijkt zelfs dat het aantal verschillende (transfiniete) kardinaalgetallen zelf ook weer oneindig is.

  15. Wiskundemeisjes » Vallende sterren (1):

    [...] wiskundige is de beroemde Kurt Gödel. We schreven al eerder over Gödel en zijn onvolledigheidsstelling en over de film die onlangs over zijn leven gemaakt [...]

  16. Joop Theunissen:

    Toevallig loop ik aan tegen een paar reacties op mijn opmerking dat er geen oneindige verzamelingen zijn, zoals er wel eindige verzamelingen zijn. Een opmerking: iemand gebruikt de uitdrukking Oneindig aantal elementen. Brrrrrrrrrrrrrrrrrrrrrrrrrrrr
    Hartelijke groetjes.
    Joop Theunissen

  17. bjorn:

    wat zijn aalle cijfers cmet 123 er mogen maar 3 getallen zijn

  18. Wiskundemeisjes » Blog Archive » Vallende sterren (10):

    [...] Onder Hilbert werkte hij aan het axiomatiseren van de wiskunde. In diezelfde tijd bewees Gödel zijn onvolledigheidsstelling. Gentzen was eerst ongerust dat dit gevolgen had voor zijn werk, maar later schreef hij dat het [...]

  19. Dirkboss:

    Je zou waar of onwaar beter moeten formuleren. Een perfect logisch consistent systeem kan onjuiste beweringen bewijzen als de aannames onjuist is. Enja wat is de waarheid binnen deze context, we bevinden ons op glad ijs hier. Inconsistentie impliceert dat er binnen het systeem een stelling x bestaat zo dat je zowel de stelling als de negatie van die stelling binnen het axiomatische systeem kan bewijzen.

  20. Count Iblis:

    Er is ook een bewijs gebaseerd op de Berry paradox: "The first positive integer that cannot be specified in less than a billion words",
    zie hier:

    http://www.cs.auckland.ac.nz/~chaitin/unm2.html

  21. JohnG1000:

    Wat ik me afvraag is waarom geaccepteerd wordt dat er geen causaal verband is in de eerste uitspraak. In de zin "deze uitspraak is niet waar" ontstaan het beoordeelde en de beoordeling op hetzelfde moment. Hoe kun je iets beoordelen wat er nog niet is? Als de uitspraak er eenmaal is wordt deze wel op een deductieve manier beoordeeld: als de uitspraak waar is dan dit of als de uitspraak niet waar is dan dat. In mijn beleving zit er geen "tijd" tussen de beoordeling en het beoordeelde in de eerste uitspraak.

  22. Kurt G̦del РIn het licht van wat wij weten:

    […] Dankzij de Nederlandse wiskunde-meisjes hebben we een begrijpbare uitleg: http://www.wiskundemeisjes.nl/20060428/kurt-gdel-en-zijn-onvolledigheidsstelling/ […]

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.