“De paradox van de oneindigheid ligt slechts bestorven in het feit dat onze gedachten eindig zijn.”
Introductie
Laten we eens kijken naar wat we eigenlijk verstaan onder het begrip oneindig. Vaak denken we aan oneindig groot, soms oneindig klein. Maar oneindig is eigenlijk een begrip wat alleen wiskundig bestaat. Want is het aantal mensen op aarde oneindig, of het aantal micro-organismen? Wat te denken van het heelal? Het heelal is naar alle waarschijnlijkheid uitdijend, wat impliceert dat zelfs het heelal niet oneindig is. Wat hopelijk wel duidelijk is uit bovenstaande, is dat we het hebben over verzamelingen. Dat is, als het goed is, bekend van de middelbare school, in ieder geval voor die mensen van na de mammoet. Maar wat herhaling kan geen kwaad.
Eindige verzamelingen
Een eindige verzameling is een opsomming van “dingen”, die we elementen noemen, die op de een of andere manier verband met elkaar houden. Zo kunnen we bijvoorbeeld praten over de verzameling van alle Nederlandse mannen met rood haar, of van de verzameling van alle toetsenborden waarvan het opschrift van de e-toets is versleten, of van alle Big-blauwe-pennen-dopjes-fetisjisten, en ga zo maar door. Al deze verzamelingen zijn eindig, dat wil zeggen dat we precies kunnen zeggen hoeveel elementen die verzamelingen hebben. Laten we eens kijken naar wiskundige verzamelingen. Bijvoorbeeld de verzameling van alle natuurlijke getallen onder de tien, dat overigens dezelfde verzameling is als dat van de cijfers van het decimale stelsel. We kunnen dat op twee manieren wiskundig schrijven: { ∀ n ∈ ℕ | n < 10} of {0,1,2,3,4,5,6,7,8,9}. De eerste verzameling spreken we formeel uit als volgt: de verzameling van alle (∀) n element van ℕ waarvoor geldt dat n kleiner is dan 10, de tweede als de verzameling 0 t/m 9. Formeel zijn ze identiek. Het aantal elementen van de verzamelingen is 10, dit noemen we ook wel het kardinaalgetal van de verzameling, dus het kardinaalgetal van een verzameling is het aantal elementen van de verzameling. Tot zover is het allemaal simpel, denk ik.
Hilberts hotel
Laatst was ik op reis in Timboektoe en was na een drukke dag wel erg moe. Ik reed toen net langs een iewat vervallen gebouw dat een hotel bleek te zijn. Op het bord in neon-letters stond te lezen Hilberts–hotel. Vermoeid ging ik naar binnen en vroeg om een kamer. Het hotel is vol, kreeg ik te horen, maar we zullen eens even kijken. Hoeveel kamers heeft u dan, vroeg ik. Oneindig veel, zei de man, met een duidelijk vermoeide klank in zijn stem. Dat maakt de administratie ook zo lastig, verzuchtte hij nog. Afijn, na een minuut of 5 had hij de oplossing: Iedere gast verhuist naar een kamer met het nummer 1 hoger dan hij/zij nu heeft, dus nummer 1 gaat naar nummer 2, nummer 2 naar nummer 3, etc., daarmee komt dan kamer nummer 1 voor u vrij. Gelukkig kon ik na enige tijd mijn kamer betrekken en mijn vermoeide hoofd op het kussen te rusten leggen. De volgende ochtend, na een goede nachtrust, werd ik wakker en realiseerde me dat dit toch eigenlijk wel een boeiend hotel was. Ik besloot nog maar eens een paar dagen te blijven. Tegen de middag kwam er een bus vol met gasten aan, er zaten 50 mensen in de bus die ieder een kamer wilde. Na enig aarzelen kwam de hotel-klerk met een zelfde soort oplossing als de vorige avond bij mij, dus moest ik verhuizen naar kamer nummer 51. Verder gebeurde er niets bijzonders die dag. De volgende dag echter kwam er een vreemd voertuig bij het hotel aan. De chauffeur stapte uit en ging naar de balie van het hotel, en vroeg of er nog kamers vrij waren. De man antwoordde als altijd dat het hotel vol was, maar vroeg toch om hoeveel kamers het ging. Oneindig veel kamers, gaf de chauffeur als antwoord. De klerk trok nu wit weg, en verliet zijn plaats, de chauffeur verbouwereerd achter latend. Na dik een half uur kwam de klerk, zichtbaar opgelucht, terug. Hij vertelde de chauffeur dat het geen probleem was en dat al zijn passagiers een kamer konden krijgen. Hij sommeerde alle reeds ingecheckte hotelgasten naar een kamer te gaan met het nummer dat twee keer het huidige nummer was. Het gevolg was dat alle even kamers door de reeds aanwezige gasten werden bezet en dat alle oneven kamers vrij kwamen voor de passagiers. Een dag later ben ik weer vertrokken, een ervaring rijker.
Oneindige verzamelingen
Het verhaal van Hilberts-hotel gaat over een oneindige verzameling, dit betekent een verzameling met oneindig veel elementen. Een belangrijke rol in de theorie der oneindige verzamelingen speelt het begrip kardinaalgetal, dat we in het vervolg machtigheid zullen noemen. Het zal blijken dat oneindige verzamelingen die ogenschijnlijk een verschillend kardinaalgetal hebben toch dezelfde machtigheid hebben. Laten we eens beginnen met een eenvoudige oneindige verzameling die we allemaal kennen, de verzameling der natuurlijke getallen, dat zijn alle positief gehele getallen, eventueel met 0 erbij. Hoeveel elementen heeft deze verzameling? Het is eenvoudig aan te tonen dat deze verzameling oneindig veel elementen bezit. Ga maar eens van het feit uit dat de verzameling eindig is. Dan is er dus een grootste getal, laten we deze maar eens N noemen. Ik beweer nu dat er een grotere is, namelijk N+1. Hiermee heb ik aangetoond dat er altijd een groter element is aan te wijzen en dat er dus geen grootste element is en dat de verzameling dus oneindig groot is. Wiskundigen hadden begin 20e eeuw de behoefte om toch het kardinaalgetal van de verzameling der natuurlijke getallen te benoemen. Ze besloten, met name de wiskundige Cantor, om de machtigheid van deze verzamelingen te omschrijven als aftelbaar oneindig en kende er het symbool ℵ0 aan toe, uit te spreken als Alef-nul. Vervolgens ging men op zoek naar verzamelingen die even-machtig waren en naar verzamelingen die machtiger waren. Beide zijn ruimschoots gevonden. Laten we eens kijken naar een andere verzameling die ook Alef-nul is. We bekijken de verzameling van alle even getallen. Het blijkt dat deze verzameling ook Alef-nul is. Dat druist in tegen ons gevoel, want wanneer je de verzameling der natuurlijke getallen halveert dan moet je ook twee keer zo weining elementen over houden. Dat is ook zo! Maar het blijven er oneindig veel, met hetzelfde argument als gebruikt bij de verzameling der natuurlijke getallen. De vraag is echter of de verzameling der even getallen ook aftelbaar oneindig is.
Aftelbaar oneindig
We zeggen dat een oneindige verzameling aftelbaar oneindig is als we de elementen kunnen “nummeren” met de natuurlijke getallen. Dit is geen echte wiskundige definitie, maar we kunnen ons hier wel een voorstelling van maken. In het geval van de verzameling der even getallen kan ik alle even getallen een rugnummer of index geven, kijk maar: 2 is het eerste getal, 4 het tweede, 6 het derde et cetera. Ofwel 1 wordt gekoppeld aan 2, 2 aan 4, 3 aan 6, …. n aan 2n, waarmee ik alle even getallen aan de natuurlijke getallen heb gekoppeld. De, ietwat non-intuïtieve, conclusie moet nu luiden, dat de verzameling der even getallen evenveel elementen heeft als de verzameling der natuurlijke getallen. Dit zelfde geldt bijvoorbeeld ook voor de volgende verzamelingen: Alle verzamelingen der n-vouden, de verzameling der gehele getallen (dus alle positieve- en negatieve getallen en nul), en zelfs voor de verzameling der breuken! Ook de verzameling der priemgetallen is Alef-nul, in een volgende aflevering kom ik uitgebreid op priemgetallen terug. Zijn er nu ook verzamelingen die machtiger zijn dan Alef-nul-verzamelingen. Het antwoord is ja.
Overaftelbaar oneindig
De verzameling der reële getallen (alle getallen met een willekeurige oneindige decimale ontwikkeling) is machtiger dan Alef-nul. Om dit aan te tonen kijken we naar een deelverzameling van de verzameling der reële getallen, namelijk de verzameling van alle punten op een lijnstuk van lengte 1, wiskundig kijken we naar de verzameling <0,1>. Cantor bewees op een geniale manier dat het aantal punten op deze lijn meer is dan het aantal natuurlijke getallen. Het bewijs is de geschiedenis in gegaan als het “diagonaal bewijs van Cantor”.
Het diagonaal bewijs van Cantor
Stel dat er aftelbaar veel elementen zijn in de verzameling <0,1>. Dan kun je een tabel maken met alle getallen erin en wel als volgt:
0,0000000000000100010100…
0,1110001101123450452874…
0,7439871982349873498743…
0,8102938876428761243987…
0,9000000000000000000000…
.
Wanneer een getal een rationaal getal is (dit is een “echte” breuk, bv 1/2), dan vullen we dit getal aan met oneindig veel nullen (dus 1/2 = 0,500000…). Op deze manier zouden we alle getallen uit <0,1> kunnen opschrijven. De vraag is nu of we wel alle getallen hebben. Cantor bewees van niet. Hij paste de volgende truc toe: Verhoog de n-e decimaal van het n-e getal met 1,behalve als deze decimaal een 9 is, dan wordt deze decimaal 0. Dus de eerste decimaal van het eerste getal wordt in ons voorbeeld een 1, de tweede decimaal van het tweede getal in ons voorbeeld wordt een 2 et cetera. We krijgen nu het getal W = 0,12431…. . Het getal W kan niet in onze tabel staan om de volgende reden: W kan niet het eerste getal zijn, want de eerste decimaal verschilt, W kan ook niet het tweede getal zijn, want de tweede decimaal verschilt, W kan ook niet het n-e getal zijn, want de n-e decimaal verschilt. Conclusie: W staat niet in onze tabel, dus kunnen we niet een aftelbaar oneindige tabel maken zoals aangenomen en dus moet de verzameling <0,1> machtiger zijn dan Alef-nul. Maar dan is ook de verzameling der reële getallen machtiger dan Alef-nul, daar <0,1> slechts een deelverzameling was van de verzameling der reële getallen. De verzameling der reële getallen heeft een machtigheid die we Alef-een zullen noemen. Er resten ons nu drie vragen: Zijn er meer verzamelingen met machtigheid Alef-een?, zijn er verzamelingen met een nog hogere machtigheid dan Alef-een?, en zijn er verzamelingen met een machtigheid die ligt tussen Alef-nul een Alef-een? De eerste twee vragen zijn gemakkelijk met ja te beantwoorden, de laatste vraag is tot nog toe onbeantwoord gebleven.
Machtsverzamelingen
Een machtsverzameling van een verzameling is de verzameling van alle deelverzamelingen van die verzameling. De machtsverzameling van de verzameling A={0,1,2} is {leeg,{0},{1},{2},{0,1},{0,2},{1,2},{0,1,2}}. Het kardinaalgetal van de verzameling A is drie, die van {A} (de machtsverzameling van A) is 23=8. Het blijkt dat wanneer een verzameling X een kardinaalgetal heeft van x, dat de verzameling {X} een kardinaalgetal heeft van 2x. Verder heeft men aangetoond dat voor oneindige verzamelingen geldt dat de machtsverzameling altijd een hogere machtigheid heeft dan de verzameling zelf en in het bijzonder dat de machtsverzameling van een verzameling van Alef-nul een machtigheid van Alef-een heeft. Hiermee zijn de eerste twee vragen beantwoord.
Continuüm hypothese
De derde vraag is een eigen leven gaan leiden. Volgens Cantor zelf bestond er geen machtigheid die lag tussen Alef-nul en Alef-een (de continuüm hypothese), maar hij kon dit niet bewijzen. Vele wiskundigen gingen van ditzelfde principe uit, maar waren ook niet in staat het te bewijzen. Ook het tegendeel, dus er bestaat wel degelijk een machtigheid tussen Alef-nul en Alef-een, kon men niet bewijzen. Inmiddels heeft het genie Paul Cohen bewezen dat de continuüm hypothese onbeslisbaar is, dit betekent dat er simpelweg geen bewijs bestaat om de continuüm hypothese te bewijzen.