De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Aftelbaar of overaftelbaar?

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
Student universiteit België - vrijdag 20 december 2013

Antwoord

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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 20 december 2013



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3