Vraag:
Is de verzameling van de deelverzamelingen van al de natuurlijke getallen aftelbaar of overaftelbaar?
Antwoord: Ik moet een bijectie vinden van de verzameling van de natuurlijke getallen naar de verzameling van de deelverzamelingen van de natuurlijke getallen, indien de verzameling aftelbaar zou zijn. Ik vind deze niet, dus ik veronderstel dat de verzameling overaftelbaar is.
Heeft iemand hier echter een bewijs of goede redenering voor die als bewijs kan gelden?
Alvast bedankt!Dries
20-12-2013
Beste Dries,
De machtsverzameling van de natuurlijke getallen is inderdaad overaftelbaar, en dat kan je op de volgende manier bewijzen: Stel dat de machtsverzameling van de natuurlijk getallen, genoteerd door $P(\mathbb{N})$, wel aftelbaar is. Dan bestaat er dus een bijectie tussen $\mathbb{N}$ en $P(\mathbb{N})$, maw we kunnen met elk natuurlijk getal $n$ een verzameling $A \subseteq \mathbb{N}$ associëren, en zo hebben we ook alle verzamelingen van natuurlijke getallen bereikt. Merk op dat we een verzameling van natuurlijke getallen, kunnen noteren als een oneindige rij van nullen en enen: Bijvoorbeeld de verzameling {0,2,4,5} kunnen we noteren als {1,0,1,0,1,1,0,0,0,...}: op plaats 0, 2, 4 en 5 staat een 1, en op de andere plaatsen staat een 0. En elke dergelijke rij van nullen en enen, komt op zijn beurt ook overeen met een verzameling van natuurlijke getallen.
Nu kunnen we een rij A definiëren op de volgende manier: Met het getal 0 wordt een rij van enen en nullen geassocieerd. Kijk nu naar het getal op de "nulde" plaats van die rij: als het een 0 is, dan laten we het nulde getal in de rij A een 1 zijn, en als het een 1 is, dan laten we het nulde getal in de rij A een 0 zijn. En zo gaan we verder: voor elk natuurlijk getal k, kijken we naar het k-de getal in de rij die geassocieerd wordt met k, en als het een 1 is dan zetten we op de k-de plaats in A een 0, en omgekeerd.
Zo krijgen we dus een rij A, en volgens onze veronderstelling (dat we een bijectie hebben tussen $P(\mathbb{N})$ en $\mathbb{N}$) kan deze rij A (die dus ook een deelverzameling van natuurlijke getallen voorstelt) geassocieerd worden met een natuurlijk getal, stel met het getal k. Maar dit kan natuurlijk niet, want we hebben A zodanig geconstrueerd dat op de k-de plaats van A een ander getal (1 of 0) staat dan op de k-de plaats van de rij geassocieerd met k. Dus hoort A niet bij k! Bijgevolg is A een rij (of verzameling van natuurlijk getallen) die niet wordt bereikt door onze functie, waarvan we dachten dat het een bijectie was! Dus kan er helemaal geen dergelijke bijectie zijn.
Ik besef dat die uitleg mogelijk nogal ingewikkeld/vergezocht overkomt. Aarzel dus zeker niet om het te laten weten als het nog niet helemaal duidelijk is, dan kan ik het misschien nog wat gedetailleerder uitleggen.
Groeten,
Christophe
cs
20-12-2013
#71700 - Verzamelingen - Student universiteit België