Diagonaalbewijs van Cantor
Het diagonaalbewijs van Cantor (ook: de diagonaalmethode van Cantor) is een bewijs, afkomstig van de wiskundige Georg Cantor, dat de cardinaliteit van de verzameling van reële getallen groter is dan die van de verzameling van natuurlijke getallen.
Inhoud |
[bewerk] Cardinaliteit
Cantor hield zich bezig met het begrip oneindig, totdantoe door wiskundigen nog slechts weinig begrepen. Hij definieerde de cardinaliteit (grootte) van oneindige verzamelingen: Twee verzamelingen hebben dezelfde cardinaliteit als er een 1-op-1 afbeelding bestaat tussen de verzamelingen. Volgens deze definitie zijn er bijvoorbeeld evenveel positieve even getallen of priemgetallen als natuurlijke getallen.
Gaan we naar op het eerste gezicht grotere verzamelingen, dan blijkt dat ook de rationale getallen dezelfde cardinaliteit hebben als de natuurlijke getallen. We kunnen de paren natuurlijke getallen aftellen door eerst de paren met som 0, dan de paren met som 1, dan de paren met som 2, etcetera te nemen. Dit levert (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3), (1,2), (2,1), (3,0), enzovoort. Er zijn dus niet meer paren natuurlijke getallen dan natuurlijke getallen, en dus ook niet meer rationale getallen.
[bewerk] Het diagonaalbewijs
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, d.w.z. 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.12345678901234... 3 - 0.00000000000120... 4 - 0.50000000000000... 5 - 0.14159265358979... 6 - 0.23562877077729...
enzovoort.
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 nieuwe getal krijgen, in het voorbeeld: 0.220098. Elk cijfer in dit getal veranderen we door een willekeurig ander cijfer. Het nieuwe getal m dat we nu hebben gemaakt, 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, zitten er tussen 0 en 1 een overaftelbaar aantal reële getallen.
[bewerk] Uitbreiding
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 cardinaliteit heeft: Stel dat er een afbeelding 
bestaat zodanig dat elk element van 2S in het beeld van de afbeelding ligt. Vorm nu de deelverzameling 
. Neem nu de 
zodanig dat a(y) = T. Zit y in T? Als 
, dan 
, dus 
. Maar als , dan 
, dus . Dit is onmogelijk, dus er is niet een dergelijke afbeelding a.
[bewerk] Paradox
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 duidelijk kleiner. 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 geherdefinieerd: Totdantoe 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.
[bewerk] Continuümhypothese
Een andere vraag die door het werk van Cantor wordt opgeroepen is dat naar de continuümhypothese. Hierboven is aangetoond dat de cardinaliteit van de reële getallen groter is dan die van de natuurlijke getallen. Zijn er verzamelingen die een cardinaliteit 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.
