Aftelbare verzamelingen

Aftelbaarheid van een verzameling is een soort equivalent van de grootte van verzamelingen, want bij oneindige verzamelingen kun je niet met het aantal elementen rekenen: dat aantal is onverwacht … oneindig. De grootte van een verzameling noemen we ook wel de kardinaliteit.

De grootte van een oneindige verzameling

De grootte van een eindige verzameling bepalen is eenvoudig: we tellen het aantal elementen. De verzameling M = {a, b, c, d, e} heeft dus grootte 5, en dat schrijven we als |M| = 5.

Bij oneindige verzamelingen ligt het een stuk ingewikkelder. Hoe kunnen we de grootte van oneindige verzamelingen vergelijken? Kan dat wel, of zijn alle oneindige verzamelingen “even groot”?

Neem als voorbeeld de verzameling van de natuurlijke getallen en de verzameling van de even natuurlijke getallen. We hebben dan de verzamelingen ℕ = {1, 2, 3, 4, 5, 6, …} en S = {2, 4, 6, …}. Je zou zeggen dat de verzameling van de natuurlijke getallen groter is dan de verzameling van de even getallen, want de natuurlijke getallen bevatten alle even getallen en daarbovenop nog extra elementen: de oneven getallen.

We zouden dus kunnen opschrijven dat S ⊂ ℕ geldt: verzameling S is een echte deelverzameling van verzameling ℕ. En we zouden kunnen zeggen dat verzameling ℕ groter is als S ⊂ ℕ, want ze bevat toch meer elementen dan verzameling S.

Een van de redenen waarom we verzamelingen niet kunnen meten aan de hand van de deelverzamelingsrelatie, is dat verzamelingen verschillend van grootte kunnen zijn terwijl geen van beide een deelverzameling van de andere is. Dat kunnen we al laten zien met eindige verzamelingen: A = {1, 3, 4, 9} en B = {b, u, r, z, m}. Er geldt: |A| = 4 en |B| = 5. Verzameling B is groter dan verzameling A, maar toch geldt niet A ⊂ B. Bij oneindige verzamelingen zien we dat aan de even en de oneven getallen: geen van beide verzamelingen is een deelverzameling van de andere.

De deelverzamelingsrelatie is dus geen ideale kandidaat om te beslissen of de ene verzameling groter is dan de andere.

Bijectie

We proberen een andere aanpak. We hebben twee verzamelingen, A en B. We kunnen zeggen dat ze even groot zijn als er tussen beide een bijectieve afbeelding bestaat. Wat betekent dat? We nemen een element uit verzameling A en een element uit verzameling B en vormen daarmee het paar (a, b). Die elementen halen we uit de verzamelingen weg en we gaan verder. Als we beide verzamelingen kunnen “leegmaken”, hebben we een bijectieve afbeelding gevonden.

Een voorbeeld met eindige verzamelingen: A = {a, b, c} en B = {1, 2, 3}. Het eerste paar zou (a, 1) kunnen zijn, het volgende (b, 2) en tot slot (c, 3). We hebben alle elementen van beide verzamelingen opgebruikt, dus we hebben een bijectieve afbeelding gevonden. Belangrijk is dat dit niet de enige bijectieve afbeelding is. Dit is ook een geldige oplossing: (a, 3), (b, 1), (c, 2).

Bij oneindige verzamelingen wordt het al wat interessanter. We proberen de oneven en de even natuurlijke getallen. Intuïtief voelen we aan dat het er evenveel zouden moeten zijn. We proberen het. We nemen het eerste oneven getal en beelden het af op het eerste even getal: (1, 2). Dan het tweede oneven en het tweede even getal: (3, 4). Enzovoort. Zo krijgen we de paren (1, 2), (3, 4), (5, 6), (7, 8), … We zouden kunnen opschrijven dat elk oneven getal l wordt afgebeeld op het even getal l + 1 en dat elk even getal s het beeld is van het oneven getal s − 1. Voor elk oneven en voor elk even getal hebben we dus een paar dat dat getal bevat. De verzamelingen van de oneven en de even getallen zijn dus even groot.

Even versus natuurlijke getallen

Nu proberen we dezelfde aanpak en vergelijken we de verzameling van de natuurlijke getallen met die van de even getallen. We hebben dus de verzamelingen ℕ = {1, 2, 3, 4, 5, 6, …} en S = {2, 4, 6, …}. Intuïtief verwachten we dat de verzameling van de natuurlijke getallen groter is.

Laten we toch proberen die bijectieve afbeelding te vinden. We kunnen zeggen dat elk natuurlijk getal n wordt afgebeeld op zijn dubbele, op 2n. Zo krijgen we de paren (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Voor elk natuurlijk getal n hebben we dus het paar (n, 2n) en voor elk even getal s hebben we het paar (s/2, s). We hebben een bijectieve afbeelding gevonden, dus de verzameling van de even getallen en de verzameling van de natuurlijke getallen zijn even groot: ze hebben dezelfde kardinaliteit.

Dit kan verwarrend lijken, want de natuurlijke getallen bevatten toch meer elementen dan de even getallen. De natuurlijke getallen bevatten alle even getallen en daarbovenop alle oneven getallen. Maar we kunnen een bijectie vinden, dus beide verzamelingen zijn even groot.

Vergelijken met de natuurlijke getallen

De natuurlijke getallen bepalen in feite de kleinste grootte van een oneindige verzameling. Of een andere verzameling even groot is als de verzameling van de natuurlijke getallen, is vaak vrij gemakkelijk na te gaan: we hoeven alleen een bijectie op de natuurlijke getallen te vinden. In de praktijk betekent dat dat we de elementen van onze verzameling M moeten kunnen nummeren, ordenen.

Als we de elementen van een verzameling dus zo kunnen rangschikken dat we kunnen bepalen welk element het eerste is, welk het tweede, derde, vierde, tiende enzovoort, dan is de verzameling even groot als ℕ. Van zo'n verzameling zeggen we dat ze aftelbaar is.

We zien gemakkelijk dat de even en de oneven natuurlijke getallen aftelbaar zijn, want we kunnen het eerste, tweede, derde enzovoort even/oneven getal aanwijzen. En de even gehele getallen? Dus de verzameling S = {…, −4, −2, 0, 2, 4, …}. Kunnen we die ordenen? Dat kan: we nemen dezelfde volgorde als daarnet en schrijven direct na elk positief even getal ook de negatieve variant op: S = {0, 2, −2, 4, −4, 6, −6, …}. Op dezelfde manier kan het bijvoorbeeld voor de gehele getallen.

De grootte van de rationale getallen

Een interessanter voorbeeld zijn de rationale getallen, de breuken. Kunnen we die ordenen? Dat kan, maar het wordt wat ingewikkelder. We maken een tabel met oneindig veel rijen en kolommen. In elke cel staat een breuk. In de n-de kolom en de m-de rij staat de breuk n/m. In de 1e kolom en de 2e rij staat dus $\frac{1}{2}$ en in de derde kolom en de vierde rij staat 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Hoe kunnen we deze getallen nu ordenen, nummeren? We kunnen ze niet rij voor rij of kolom voor kolom nummeren, want dan verdrinken we meteen in die ene rij of kolom. In plaats daarvan nemen we de getallen langs de diagonalen: (eerste diagonaal:) 1/1, (tweede diagonaal:) 2/1, 1/2, (derde diagonaal:) 3/1, 2/2, 1/3, (vierde diagonaal:) 4/1, 3/2, 2/3, 1/4, … Er staan nog veel dubbele breuken tussen, maar dat maakt niet uit. Erger is dat de negatieve getallen ontbreken. Dat is eenvoudig op te lossen: telkens als we een breuk opschrijven, zetten we er direct de negatieve variant achter. En dan ontbreekt helemaal aan het begin nog de nul. Dat is alles: we hebben alle rationale getallen in een rij.

In totaal krijgen we dus de rij: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

De grootte van de reële getallen

Zijn de reële getallen even groot als de natuurlijke getallen? De beslissing wordt nog ingewikkelder dan bij de rationale getallen. We voeren een bewijs uit het ongerijmde. We nemen aan dat de reële getallen aftelbaar zijn en dat er een bijectieve afbeelding op de natuurlijke getallen bestaat. We nemen dus aan dat ze geordend kunnen worden. En laten we zeggen dat de volgende afbeelding die ordening is:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

In de tabel staan de eerste zeven reële getallen van onze ordening. Die ordening kan natuurlijk willekeurig zijn: de getallen hoeven niet op grootte gesorteerd te zijn.

Volgens onze aanname staan in deze oneindige tabel alle reële getallen op volgorde. (De tabel is weer oneindig, hier staan maar de eerste zeven rijen.) We proberen nu een getal te vinden of te construeren dat reëel is maar niet in deze tabel staat. Als we zo'n getal vinden, is dat in tegenspraak met het feit dat alle reële getallen in de tabel staan, en daaruit kunnen we concluderen dat de verzameling van de reële getallen niet aftelbaar is.

Dat getal dat niet in de tabel staat, construeren we zo:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

We beginnen met het opschrijven van 0,… Zo begint ons nieuwe reële getal. Op de eerste decimaal komt dan een cijfer dat niet op de eerste plaats van het eerste reële getal van onze ordening staat (in de tabel is dat met een kader gemarkeerd). Daar staat het cijfer 3, dus we kiezen bijvoorbeeld 1 en we krijgen het getal 0,1…

We gaan verder. Op de tweede plaats komt een cijfer dat niet op de tweede plaats van het tweede reële getal staat. Daar staat 9, dus bijvoorbeeld 2. We krijgen het getal 0,12… Op de derde plaats komt een cijfer dat verschilt van het derde cijfer van het derde reële getal. Daar staat 3, dus we kiezen bijvoorbeeld 7. We krijgen 0, 127…

En zo gaan we door. Op de n-de plaats van het nieuwe getal komt altijd een cijfer dat verschilt van het cijfer op de n-de plaats van het n-de getal van onze ordening.

Wat levert dat op? We krijgen een getal dat van alle getallen in onze ordening in minstens één cijfer verschilt. Neem het laatste tussenresultaat: 0,127… Dit getal verschilt zeker van het eerste getal in onze ordening in minstens het eerste cijfer, omdat we het zo hebben opgebouwd. Van het tweede getal verschilt het in minstens het tweede cijfer. Van het derde in het derde cijfer. In het algemeen verschilt dit nieuwe getal van het getal dat op de n-de plaats in de ordening staat, in minstens het cijfer op de n-de plaats.

Dit nieuw geconstrueerde getal vinden we dus niet in de tabel, die de bijectie tussen de natuurlijke getallen en de reële getallen moest voorstellen. De reële getallen zijn dus groter dan de natuurlijke getallen. De reële getallen zijn niet aftelbaar, ze zijn overaftelbaar.

Meer informatie

• Are there more odd or even numbers?