Aftelbare verzameling

In de wiskunde noemen we een verzameling aftelbaar als we de elementen ervan kunnen ‘aftellen’. Dat houdt in dat we de elementen op een rij kunnen zetten met een eerste element, een tweede element, enz., waarbij alle elementen aan de beurt komen. De eenvoudigste aftelbare verzamelingen zijn de eindige verzamelingen.

Een aftelbare verzameling is niet noodzakelijk eindig. Zo zijn ook de gehele getallen aftelbaar. We zetten ze als volgt in een rij om geteld te worden: 0, 1, -1, 2, -2, 3, -3, enz. Het tellen van de elementen stopt weliswaar nooit, maar elk element komt aan de beurt.

Er zijn ook verzamelingen die niet aftelbaar zijn. We zeggen dan dat deze verzamelingen overaftelbaar zijn.

Definitie

De bovenstaande uitleg van aftelbaarheid is natuurlijk niet erg exact . Daarom geven we een nette definitie van aftelbaarheid, waarin we het bovenstaande idee over aftelbare verzamelingen verwerken.

Het aftellen van de elementen van een verzameling S kunnen we opvatten als een functie f die een relatie legt tussen de rangnummer in de aftelling en de elementen van S. Die functie moet dus surjectief zijn. Het maakt niet zoveel uit of de beelden elkaar overlappen, maar het is wel belangrijk, dat alle elementen van S in het beeld van f liggen. Kortom:

Een verzameling S heet aftelbaar als er een deelverzameling M van de natuurlijke getallen en een surjectieve functie

$f: M \to S$

bestaat.

Als $M=\mathbb{N}$ en f bijectief is, wordt S aftelbaar oneindig genoemd en f een aftelling van S. Intuïtief wil dit zeggen dat we de elementen van S op een rijtje kunnen zetten, waarbij elke element zijn eigen unieke nummer heeft.

Opmerking

Men definieert aftelbaarheid ook wel als het bestaan van een injectie van S in de natuurlijke getallen. Dit lijkt meer voor de hand te liggen, men geeft immers elk element van S z'n rangnummer. Deze definitie is equivalent met de bovenstaande.

Eigenschappen

• Als R aftelbaar is en er bestaat een surjectieve functie g tussen R en een bepaalde verzameling S, dan is S ook aftelbaar.

• Een eindig product van aftelbare verzamelingen is aftelbaar. Dat kan men als volgt inzien:

Stel dat $S_1$ tot en met $S_n$ aftelbaar zijn, met n een natuurlijk getal. Dan zijn er n surjectieve functies $f_i$ tussen de natuurlijke getallen en $S_i$. We kunnen die surjectieve functies combineren tot één surjectieve functie:

$f: \mathbb{N}^{n} \to \prod_{i=1}^{n} S_i: (x_1,x_2, \ldots x_n) \to f((x_1,x_2, \ldots x_n)) = (f_1(x_1), f_2(x_2) \ldots f_n(x_n))$

Daar $\mathbb{N}^{n}$ aftelbaar is voor elke natuurlijke n, zal ook $\prod_{i=1}^{n} S_i$ aftelbaar zijn.

Voorbeelden

• De verzameling van de gehele getallen $\mathbb{Z}$ is aftelbaar. Een voor de hand liggende aftelling is de volgende:

$0,-1,1,-2,2,-3,3, \ldots$

• Een mogelijke aftelling van $\mathbb{N}^{2}$ is de volgende:

$(0,0),(0,1),(1,0),(2,0),(1,1)(0,2),(3,0),(2,1),\ldots$

Eerst schrijven we dus de koppeltjes op met som 0, dan die met som 1, 2 enzovoort. Deze procedure kan men uitbreiden naar een willekeurig eindige macht van $\mathbb{N}$.

• De verzameling van de positieve rationale getallen $\mathbb{Q}^+$ is aftelbaar, want met elk positief rationaal getal correspondeert een koppel natuurlijke getallen (teller, noemer). Voor de volledige verzameling rationale getallen, wordt het iets ingewikkelder:

• Voor $\mathbb{Q}$ kijken we naar alle getallen van de vorm a/b, met a een natuurlijk getal, en b een van nul verschillend natuurlijk getal. Deze getallen kunnen door een bijectie afgebeeld worden op een deelverzameling van de geordende tripletten (a,b,c), met a ≥ 0, b > 0, a en b copriem, en c = 0 als a/b > 0, anders is c = 1.

Zo wordt 0 afgebeeld op (0,1,0), 1 (= 1/1) op (1,1,0), -1 op (1,1,1), 1/2 op (1,2,0), -1/2 op (1,2,1), 2 op (2,1,0), enz...

• Georg Cantor heeft bewezen dat de verzameling van de reële getallen niet aftelbaar is. Dit bewijs staat bekend als het diagonaalbewijs van Cantor.