TU/e
Mike Boldy en Hans Cuypers

Oneindige verzamelingen

Op de vorige pagina hebben we gezien dat een verzameling oneindig is als een nummeringsprocedé niet eindigt. Voor oneindige verzamelingen geldt de volgende belangrijke eigenschap:

Stelling

Als A een oneindige verzameling is, en A\subset B, dan is B ook oneindig.

Voor oneindige verzamelingen zijn er twee mogelijkheden:

In het eerste geval spreken we van een aftelling van de verzameling, en de verzameling heet aftelbaar. In het tweede geval zeggen we dat de verzameling overaftelbaar is. Merk op dat we bij een aftelling bij 0 beginnen, terwijl we voor nummeringen van eindige verzamalingen bij 1 beginnen.

Stelling

De machtsverzameling van een aftelbare verzameling is niet aftelbaar:
Stelling

Als A een aftelbare verzameling is, dan is \cal{P}(A) overaftelbaar.

Deze stelling is afkomstig van Georg Cantor, een beroemd Duits wiskundige die leefde van 1845 tot 1916. Hij was de eerste wiskundige die besefte dat er meerdere soorten oneindigheid bestonden.

Voorbeeld

De verzameling \mathbb N is aftelbaar: nummer ieder natuurlijk getal met zichzelf. Hieruit volgt onmiddellijk dat \mathbb Z, \mathbb Q, \mathbb R en \mathbb C oneindige verzamelingen zijn. Het is niet meteen duidelijk of ze aftelbaar dan wel overaftelbaar zijn.

Voorbeeld

De verzameling \mathbb Z is aftelbaar. Een aftelling is bijvoorbeeld

0_0,1_1,-1_2,2_3,-2_4,3_5,-3_6,\ldots
Je kunt ook als volgt te werk gaan: \mathbb Z=\{0,1,2,3,\ldots\}\cup\{0,-1,-2,-3,\ldots\}. Zowel \{0,1,2,3,\ldots\} als \{0,-1,-2,-3,\ldots\} zijn aftelbaar, dus de vereniging van beide verzamelingen is ook aftelbaar.

Voorbeeld

De verzameling \mathbb Q is aftelbaar. Dit is als volgt in te zien. Kijk eerst naar de verzameling V=\{(m,n)|m\in\mathbb Z,n\in\mathbb N\setminus\{0\}\}=\mathbb Z\times\mathbb N\setminus\{0\}. Een breuk m/n\in\mathbb Q komt overeen met het paar (m,n)\in V, dus geldt in zekere zin \mathbb Q\subset V. De verzameling V is aftelbaar, dus \mathbb Q is eindig of aftelbaar. Maar \mathbb Q is niet eindig, want bijvoorbeeld \mathbb N\subset\mathbb Q.

Voorbeeld

De verzameling \mathbb R is overaftelbaar. Het bewijs gaat op dezelfde manier als het bewijs van de stelling van Cantor. Als je meer wilt weten van dit bewijs zoek dan op internet met als zoekterm ``Cantor's diagonaal argument''.