Diagonaalbewijs van Cantor

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een illustratie van het diagonaalbewijs van Cantor voor het bestaan van de onaftelbare verzamelingen.[1] De volgorde van de onderste rij kan nergens in de oneindige lijst van rijen erboven voorkomen, dit omdat het met rood aangegeven element (op de diagonaal) per definitie van het corresponderende element op de onderste rij verschilt

Het diagonaalbewijs van Cantor (ook: 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 er geen bijectie van de verzameling natuurlijke getallen met een willekeurige oneindige verzameling X gemaakt kan worden, wordt verzameling X overaftelbaar genoemd.

Kardinaliteit[bewerken]

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 1-op-1 afbeelding bestaat tussen de verzamelingen.

De intuïtie zegt dat er meer natuurlijke getallen zijn dan even getallen. Er kan echter 1-op-1 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 \aleph_0.

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:

1/1 1/2 1/3 ...
2/1 2/2 2/3 ...
3/1 3/2 3/3 ...
... ... ...

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 1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 1/5 2/4 ...

Er zijn dus niet meer breuken van natuurlijke getallen dan natuurlijke getallen, en dus ook niet meer rationale getallen.

Het diagonaalbewijs[bewerken]

Hebben misschien alle oneindige verzamelingen hetzelfde formaat? Dit blijkt niet zo te zijn. En daar komt het diagonaalbewijs om de hoek: er zijn meer reële getallen tussen 0 en 1 dan er natuurlijke getallen zijn. Dit bewijs gebruikt reductio ad absurdum. We nemen daarom aan dat er een bijectie, dit wil zeggen een 1-op-1 afbeelding 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[2]), 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 m dat we nu hebben gemaakt (in het voorbeeld: 0,454444...) kan nooit in de lijst staan; immers als je uit de lijst het getal n haalt dan komt het n-de cijfer van dat getal niet meer overeen met het n-de cijfer uit m. Omdat er altijd een nieuwe m gemaakt kan worden, zit er tussen 0 en 1 een overaftelbaar aantal reële getallen.

Uitbreiding[bewerken]

Bij uitbreiding kan het diagonaalbewijs ook gebruikt worden om te bewijzen dat voor elke verzameling S, de verzameling van deelverzamelingen van S, genoteerd 2S, een grotere kardinaliteit heeft: Stel dat er een afbeelding a:S\mapsto 2^S bestaat zodanig dat elk element van 2S in het beeld van de afbeelding ligt. Vorm nu de deelverzameling T=\{x\in S|x\not\in a(x)\}. Neem nu de y\in S zodanig dat a(y)=T. Zit y in T? Als y\in T, dan y\in a(y), dus y\not\in T. Maar als y\not\in T, dan y\not\in a(y), dus y\in T. Dit is onmogelijk, dus er is niet een dergelijke afbeelding a.

Paradox[bewerken]

Deze laatstgenoemde versie van het diagonaalbewijs leverde een paradox: Zij S de verzameling van alle verzamelingen. 2S is de verzameling van alle verzamelingen van verzamelingen, en is dus een deelverzameling van S, 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 A de verzameling van alle dingen met eigenschap A bestond. Dit werd veranderd tot het axioma dat gegeven een verzameling S en een eigenschap A, de verzameling van die elementen van S die eigenschap A hebben, bestaat.

Continuümhypothese[bewerken]

Een andere vraag die door het werk van Cantor wordt opgeroepen is die naar de continuümhypothese. Hierboven is aangetoond dat de kardinaliteit van de reële getallen groter is dan die van de natuurlijke getallen. Zijn er verzamelingen die een kardinaliteit hebben die tussen deze twee waarden in ligt? De continuümhypothese is het vermoeden dat dit niet het geval is. Het is inmiddels bewezen dat de continuümhypothese onafhankelijk is van de bestaande axioma's van de verzamelingenleer plus het keuzeaxioma. Dat wil zeggen, noch de continuümhypothese noch haar ontkenning kan uit de bestaande axioma's bewezen worden.

Bronnen, noten en/of referenties
  1. Deze illustratie sluit nauw aan op het eerste deel van Cantors artikel uit 1891.
  2. Deze eis is nodig, omdat niet elk reëel getal een unieke decimale representatie heeft. Er geldt bijvoorbeeld dat 0,4999... = 0,5000.... Door het nieuwe getal zo te maken, dat er geen 0 of 9 in voorkomt, wordt dit probleem omzeild.