Er zijn eindige en oneindige verzamelingen. Zoals eindige verzamelingen verschillend kunnen zijn in het aantal elementen, zo zijn er ook meerdere soorten oneindige verzamelingen te onderscheiden. Er zijn verzamelingen waarvan de elementen op een rijtje gezet kunnen worden en verzamelingen waarbij dat niet kan. De eerste groep noemen we aftelbare verzamelingen. De tweede niet aftelbare, ook wel overaftelbare, verzamelingen.
In het fragment Irrationaliteit en aftelbaarheid is aangetoond dat de verzameling van de natuurlijke getallen en die van de rationale getallen aftelbaar zijn en dat de verzameling van de reële getallen niet aftelbaar is. Is hiermee het hele verhaal over oneindige verzamelingen verteld? Dat is het onderwerp van dit wiskundefragment.
Het werken met oneindige verzamelingen heeft verrassende effecten. Een leuke toepassing is Hilberts Hotel. Dit hotel is vernoemd naar de beroemde wiskundige David Hilbert die in 1900 tien onopgeloste wiskundige problemen formuleerde die in de twintigste eeuw om een oplossing vroegen. Wat is Hilberts Hotel en wat kun je ermee?
Hilberts Hotel is een hotel met aftelbaar oneindig veel kamers genummerd 1, 2, 3, …
Het hotel is volledig gevuld met gasten. Elke kamer is bezet. Bij de balie meldt zich een nieuwe gast die vraagt of er een kamer vrij is. De eigenaar, een creatief denker, antwoordt: 'Op dit moment niet, maar over een uur wel'. Hij gaat vervolgens aan het organiseren. De gast uit kamer 1 wordt verzocht te verhuizen naar kamer 2, die van kamer 2 naar kamer 3. In het algemeen: de gast uit kamer `n` laat hij verhuizen naar kamer `n+1`. Daarmee is kamer 1 beschikbaar gekomen en is er ruimte voor de nieuwe gast.
Op zekere dag arriveert er een touringcar met aftelbaar oneindig veel mensen. Ook zij vragen om kamers in het hotel. De eigenaar van het hotel is inmiddels een gelauwerde organisator. Hij verplaatst elke zittende gast naar een kamer met een nummer dat het dubbele is van zijn oude kamernummer. Daarmee kunnen de kamers met een oneven nummer toegewezen worden aan de mensen uit de zojuist gearriveerde bus.
En nu wordt het interessant. Op een drukke dag arriveren er aftelbaar oneindig veel bussen die elk aftelbaar veel passagiers bevatten. Kunnen al deze nieuwe gasten een plaatsje krijgen in het hotel?
Welzeker! De eigenaar is bekend met de methode van Cantor en deelt de nieuwe en de oude gasten als volgt in:
Begin linksboven en volg de pijlen.
enzovoort.
Ga na dat de oude gast uit kamer 7 op deze manier in kamer 28 terechtkomt.
Onvoorstelbaar hoeveel gasten er in Hilberts hotel kunnen! Het blijft echter allemaal aftelbaar.
In het vervolg ga je een stap verder.
Zie het fragment irrationaliteit en aftelbaarheid.
De verzameling van de natuurlijke getallen (`NN`) en de verzameling van de rationale getallen (`QQ`) zijn aftelbaar, m.a.w. je kunt ze op een rijtje zetten en 'aftellen'. De verzameling van de reële getallen (`RR`) is niet aftelbaar (ook wel overaftelbaar genoemd). Dit houdt automatisch in dat de verzameling van de irrationale getallen overaftelbaar is. Hiermee is niet het hele verhaal verteld. Er blijken veel meer soorten oneindig te zijn dan de oneindigheid van de aftelbare en die van bijvoorbeeld de reële getallen. Hoe zit dat?
Om dat uit te leggen is het nodig enige begrippen te introduceren. Aan de orde komen verzamelingen en afbeeldingen van een verzameling naar een andere verzameling.
Bekijk twee verzamelingen `V` en `W`.
In dit hoofdstuk geldt dat het domein van een afbeelding van `V` naar `W` altijd de gehele verzameling `V` is! Het bereik hoeft niet de gehele verzameling `W` te zijn.
Voorbeeld
`V={1,2,3,4}` en `W={a,b,c,d,e}`
`f` is een afbeelding van `V` naar `W`, gegeven door `f(1)=a, f(2)=c, f(3)=e, f(4)=d`.
Merk op dat het element b geen origineel in `V` heeft en dus niet in het bereik van `f` zit.
`g` is een afbeelding van `V` naar `W`, gegeven door `g(1)=b, g(2)=b, g(3)=d, g(4)=d`.
Bij zowel `f` als `g` treden niet alle elementen van `W` als beeld op. Bij `f` is het bereik `{a,c,d,e}` en bij `g` is het bereik `{b,d}`.
Je kunt ook een afbeelding van `W` naar `V` maken.
`h` is een afbeelding van `W` naar `V`, gegeven door `h(a)=1, h(b)=2, h(c)=3, h(d)=4, h(e)=2`.
Het bereik van `h` is in dit geval de gehele `V`. Het element 2 uit `V` heeft twee originelen in `W`, namelijk `b` en `e`.
Enkele definities:
In het voorbeeld is `f` injectief, `g` en `h` zijn dat niet. `f` is een afbeelding van `V` in `W`.
`f` heet een injectie.
In het voorbeeld is `h` surjectief, het is een afbeelding van 'W' op `V`.
`h` heet een surjectie.
`V = {1,2,3,4}` en `W = {a,s,d,f}`
`k` is de afbeelding van `V` naar `W`, gegeven door `k(1)=f, k(2)=d, k(3)=s, k(4)=a`.
De afbeelding `k` is zowel injectief als surjectief en dus bijectief.
`k` heet een bijectie.
Merk op dat de afbeeldingen `f, g` en `h` uit het eerste voorbeeld geen van alle bijectief zijn.
Het omgekeerde is trouwens ook waar:
Het formele bewijs van deze stellingen mag je zelf proberen.
Interessanter wordt het bij afbeeldingen tussen oneindige verzamelingen.
Voorbeelden
De afbeelding `f` van de natuurlijke getallen naar de natuurlijke getallen wordt gegeven door het voorschrift:
`f(n)=2n+1` voor alle `n in NN`
dus `f(0)=1, f(1)=3, f(2)=5` enzovoort. Het bereik van `f` is de verzameling van de oneven getallen.
`f` is injectief.
`f` is niet surjectief, want de even getallen treden niet als beeld op.
De afbeelding `g` van de natuurlijke getallen naar de natuurlijke getallen wordt gegeven door het voorschrift:
`g(n)=n+1` als `n` even is.
`g(n)=n-1` als `n` oneven is
Ga zelf na dat `g` injectief en surjectief en dus bijectief is.
De afbeelding `h` van de natuurlijke getallen naar de natuurlijke getallen wordt gegeven door het voorschrift:
`h(n)=2n` als `n` oneven is.
`h(n)=n/2` als `n` even is
Is `h` injectief? Surjectief? Bijectief?
De afbeelding `k` van de reële getallen naar de reële getallen wordt gegeven door het voorschrift:
`k(x)=3x-5`
Is `k` injectief? Surjectief? Bijectief?
Nu komt het onderwerp waar het om begonnen is.
Voor eindige verzamelingen komt dit volgens de stellingen 1 en 2 neer op: Twee eindige verzamelingen zijn gelijkmachtig als ze evenveel elementen hebben.
Hoe zit het nu met oneindige verzamelingen?
De verzamelingen `NN, ZZ` en `QQ` zijn allemaal aftelbaar. Je kunt van elk van deze verzamelingen de getallen op een rijtje zetten. Het is dan eenvoudig om een bijectie te maken. Met behulp van het rooster in Aftelbare verzamelingen kun je een bijectie maken tussen `NN` en `QQ`.
De verzameling van de irrationale getallen is niet aftelbaar. Met andere woorden: er bestaat geen bijectie van `NN` op de irrationale getallen (en dus ook niet van `NN` op `RR`). `NN` en `RR` zijn dus niet gelijkmachtig.
Er zijn blijkbaar ten minste twee machtigheden voor oneindige verzamelingen. Maar is dit alles? Met andere woorden: Zijn er oneindige verzamelingen die niet gelijkmachtig zijn met `NN` en ook niet met `RR`? Zo ja, hoeveel verschillende soorten oneindigheid zijn er eigenlijk? Om deze vraag te beantwoorden kijk je naar de verzameling van alle deelverzamelingen van een verzameling.
Eerst een voorbeeld van een eindige verzameling: `V={1,2,3}`.
Voor elke deelverzameling van `V` geldt: elk element van `V` zit erin of niet, en er zitten geen andere elementen in.
Er zijn dan dus `2^3` mogelijke deelverzamelingen:
`Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}`
De verzameling van alle deelverzamelingen van `V` is dus: `{Ø, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}`
Deze wordt genoteerd met `cc "P"(V)`.
Je ziet onmiddellijk dat voor eindige verzamelingen `V` en `cc "P"(V)` niet gelijkmachtig zijn. Ze hebben immers een verschillend aantal elementen. Er kan dus nooit een bijectie bestaan.
Hoe zit het met oneindige verzamelingen?
Neem bijvoorbeeld de verzameling van alle deelverzamelingen van de natuurlijke getallen: `cc "P"(NN)`. Dat is een heel grote oneindige verzameling. Maar hoe groot? Is deze bijvoorbeeld aftelbaar en dus gelijkmachtig met `NN`?
De volgende stelling geeft het antwoord.
Voor elke verzameling `V` geldt: `V` is niet gelijkmachtig met `cc "P"(V)`.
Het bewijs volgt later. Als deze stelling juist is dan gelden in elk geval de volgende, wellicht verrassende, conclusies:
Er zijn dus oneindig veel machtigheden voor oneindige verzamelingen!!!
Nu het bewijs van stelling 3:
Voor eindige verzamelingen spreekt de stelling voor zich. Voor oneindige verzamelingen moet je een ingenieuze truc uithalen. Overigens geldt onderstaand bewijs ook voor eindige verzamelingen, maar daarvoor is niet zoveel moeite nodig.
Laat `f` een afbeelding van `V` naar `cc "P"(V)` zijn.
Bekijk de verzameling `S={x in V|x notin f(x)}`
Wat staat hier? De verzameling `S` bestaat uit de elementen `x` uit `V`, die zelf géén element zijn van hun beeldverzameling `f(x)`. `S` is dus een deelverzameling van `V` en zou dus moeten optreden als beeld van een element uit `V` als `f` een bijectie is. De bewering is dat `S` nooit als beeld kan optreden van een element `y` uit `V`.
Stel dat er wel zo'n `y` bestaat, dus `f(y)=S`.
Als `y in f(y)` dan `y in S` (immers `f(y)=S`). Maar `S` bevat precies die elementen `x` van `V` die geen element zijn van `f(x)`, dus is de conclusie dat `y notin S`. Dit is een tegenspraak.
`y` is blijkbaar geen element van `f(y)`. Maar dan geldt dat `y` juist wel een element is van `S` en dus moet `y` wel een element zijn van `f(y)`. Wederom een tegenspraak.
Conclusie: `S` kan niet als beeld optreden van een element van `V` en dus is `f` geen bijectie en is `V` niet gelijkmachtig met `cc "P"(V)`.
Je weet nu dat er oneindig veel machtigheden bestaan. Maar bestaat er een oneindige deelverzameling van de reële getallen `RR` die niet gelijkmachtig is met `RR` zelf, maar ook niet gelijkmachtig met `NN`?
Dit is de zogenaamde continuümhypothese van Georg Cantor:
Elke oneindige deelverzameling van `RR` is ofwel gelijkmachtig met `RR` ofwel met `NN`.
Vele wiskundigen en in het bijzonder zij die zich met de fundamenten van de wiskunde bezig hebben gehouden, hebben zich hier het hoofd over gebroken. De conclusie is dat de continuümhypothese niet te bewijzen is binnen de axioma's van de verzamelingenleer. Wel is aangetoond dat de continuümhypothese gelijkwaardig is aan diverse andere hypotheses of axioma's. Het voert veel te ver om hier nu nader op in te gaan.
Math4all Auteur: Rob Grünefeld
» irrationaliteit en aftelbaarheid.
» David Hilbert
» Georg Cantor
Ik wil mij aanmelden voor:
