Loading AI tools
Van Wikipedia, de vrije encyclopedie
Het diagonaalbewijs van Cantor of de diagonaalmethode van Cantor is een bewijs, afkomstig van de wiskundige Georg Cantor, dat de kardinaliteit van de verzameling van reële getallen groter is dan die van de verzameling van natuurlijke getallen. De verzameling natuurlijke getallen is aftelbaar oneindig, kortweg aftelbaar genoemd. Als een oneindige verzameling niet een-eenduidig op de natuurlijke getallen kan worden afgebeeld, wordt overaftelbaar genoemd. Met zijn diagonaalmethode laat Cantor zien dat er geen een-eenduidige correspondentie is tussen de natuurlijke getallen en de reële getallen. Cantor publiceerde dit bewijs in 1891, maar had de overaftelbaarheid van de reële getallen al eerder bewezen.
Cantor hield zich bezig met het begrip oneindig, tot dan toe door wiskundigen nog slechts weinig begrepen. Hij definieerde de kardinaliteit (grootte) van oneindige verzamelingen: Twee verzamelingen hebben dezelfde kardinaliteit als er een een-eenduidige afbeelding bestaat tussen de verzamelingen.
De intuïtie zegt dat er meer natuurlijke getallen zijn dan even getallen. Er kan echter een-op-een een afbeelding worden gemaakt:
Natuurlijke getallen | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
Even getallen | 2 | 4 | 6 | 8 | 10 | 12 |
Anders gezegd, de verzameling even getallen is aftelbaar, evenals de verzameling natuurlijke getallen, en de kardinaliteit is dezelfde. Deze kardinaliteit wordt wel aangeduid als .
Gaan we naar op het eerste gezicht grotere verzamelingen, dan blijkt dat ook de rationale getallen dezelfde kardinaliteit hebben als de natuurlijke getallen. Het gaat hier om de volgende getallen:
... | |||
... | |||
... | |||
... | ... | ... |
We kunnen ze niet aftellen door met de eerste kolom te beginnen, want dan komen we nooit aan de tweede kolom toe. Het kan echter wel door diagonaal te werken: eerst de breuken waarvan teller en noemer samen 2 zijn, daarna de breuken met som 3 enzovoort. Dit levert:
Natuurlijke getallen | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Breuken | ... |
Er zijn dus niet meer breuken van natuurlijke getallen, dus rationale getallen, dan natuurlijke getallen, .
Er zijn meer reële getallen tussen 0 en 1 dan er natuurlijke getallen zijn. Dit bewijs gebruikt reductio ad absurdum. We nemen aan dat er een bijectie, een een-op-eenafbeelding, van de natuurlijke getallen naar de reële getallen bestaat. Zo'n afbeelding ziet er bijvoorbeeld zo uit:
1 ↔ 0,23958239052222... 2 ↔ 0,14345678901234... 3 ↔ 0,00000000000120... 4 ↔ 0,50000000000000... 5 ↔ 0,14159265358979... 6 ↔ 0,23562877077729...
enzovoort.
De lijst is in twee richtingen oneindig lang. Nu nemen we van het eerste getal het eerste cijfer achter de komma. Van het tweede getal nemen we het tweede cijfer achter de komma, enzovoort. Deze cijfers zetten we achter elkaar, zodat we een nieuw getal krijgen, in het voorbeeld: 0,240098.... Het getal vormt als het ware de diagonaal van de tabel. Elk cijfer in dit getal veranderen we in een willekeurig ander cijfer (anders dan 0 of 9[1]), bijvoorbeeld door het getal in 4 te veranderen als het anders is dan 4, en in 5 als het gelijk is aan 4. Het nieuwe getal dat we nu hebben gemaakt (in het voorbeeld: 0,454444...) kan niet in de lijst staan. Immers, als je uit de lijst het getal haalt, komt het -de cijfer van dat getal niet meer overeen met het -de cijfer uit . Omdat er altijd een nieuwe gemaakt kan worden, zit er tussen 0 en 1 een overaftelbaar aantal reële getallen.
Bij uitbreiding kan het diagonaalbewijs ook gebruikt worden om te bewijzen dat voor elke verzameling , diens machtsverzameling (de verzameling van deelverzamelingen van ), genoteerd , een grotere kardinaliteit heeft. Stel dat er een afbeelding bestaat zodanig dat elk element van in het beeld van de afbeelding ligt. Vorm nu de deelverzameling . Neem nu de zodanig dat . Zit in ? Als , dan , dus . Maar als , dan , dus Dit is onmogelijk, dus er is niet een dergelijke afbeelding .
Door te beginnen met de natuurlijke getallen en het diagonaalargument oneindig vaak toe te passen op een volgende machtsverzameling, kan een oneindig aantal oneindige kardinaliteiten worden verkregen.
Deze laatstgenoemde versie van het diagonaalbewijs leverde een paradox: Zij de verzameling van alle verzamelingen. is de verzameling van alle verzamelingen van verzamelingen, en is dus een deelverzameling van , en dus kleiner of even groot, maar niet groter. Maar bovenstaand bewijs toont aan dat het groter moet zijn. Hier was dus duidelijk iets mis.
Een vergelijkbaar probleem werd geleverd door de "verzameling van alle verzamelingen die zichzelf niet bevatten". Bevat deze verzameling zichzelf of niet? Zie Russellparadox voor een uitgebreidere behandeling van deze paradoxen.
Op basis van deze paradoxen werd de verzamelingenleer opnieuw gedefinieerd: Tot dan toe had men als axioma aangenomen dat voor elke eigenschap de verzameling van alle dingen met eigenschap bestond. Dit werd veranderd tot het axioma dat gegeven een verzameling en een eigenschap , de verzameling van die elementen van die eigenschap hebben, bestaat.