Aftelbare verzameling

Een aftelbare verzameling is in de wiskunde een verzameling waarvan de elementen afgeteld kunnen worden. Dat houdt in dat de elementen op een rij gezet kunnen worden met een eerste element, een tweede element, enzovoort, 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. Ze kunnen bijvoorbeeld als volgt op een rij gezet 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 overaftelbaar zijn, dat wil zeggen niet aftelbaar. Een verzameling is dus eindig, aftelbaar oneindig, of overaftelbaar.

Aftelbaar oneindige verzamelingen zijn in zekere zin "even groot", terwijl als de ene bestaat uit dezelfde elementen als de andere, en nog meer, die in een ander opzicht "groter" is.

Definitie

Een aftelbaar oneindige verzameling $S$ is een verzameling die gelijkmachtig is met $ℕ$ , d.w.z. dat er een bijectie $f : ℕ \to S$ bestaat.

De volgende definities zijn equivalent: Een verzameling $S$ is aftelbaar als:

$S$ eindig of aftelbaar oneindig is
er een surjectie $f : ℕ \to S$ bestaat
er een injectie $f : S \to ℕ$ bestaat
er een bijectie $f : ℕ \to S$ bestaat, of voor zeker geheel getal $n \geq 0$ een bijectie $f : {1, \dots, n} \to S$
$S$ gelijkmachtig is met $ℕ$ , of voor zeker geheel getal $n \geq 0$ gelijkmachtig met ${1, \dots, n}$

Eigenschappen

Als $R$ aftelbaar is en er bestaat een surjectieve functie $g : R \to S$ , dan is ook $S$ aftelbaar.

Een eindig product van aftelbare verzamelingen is aftelbaar. Dat kan als volgt ingezien worden:

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}

. Die surjectieve functies kunnen gecombineerd worden tot één surjectieve functie:

f : ℕ^{n} \to \prod_{i = 1}^{n} S_{i} : (x_{1}, x_{2}, \dots x_{n}) \mapsto f (x_{1}, x_{2}, \dots x_{n}) = (f_{1} (x_{1}), f_{2} (x_{2}) \dots f_{n} (x_{n}))

Daar

ℕ^{n}

aftelbaar is voor alle natuurlijke

n

, is ook

\prod_{i = 1}^{n} S_{i}

aftelbaar.

Voorbeelden

Een mogelijke aftelling van $ℕ^{2}$ is:

(0, 0), (0, 1), (1, 0), (2, 0), (1, 1) (0, 2), (3, 0), (2, 1), \dots

Eerst worden dus de paren met som 0 opgeschreven, dan die met som 1, daarna met som 2, enzovoort. Deze procedure kan uitgebreid worden naar een willekeurige eindige macht van

ℕ

.

De verzameling van de positieve rationale getallen $ℚ^{+}$ is aftelbaar, want elk positief rationaal getal correspondeert met een koppel natuurlijke getallen (teller, noemer). Door afwisselend een positief en een negatief rationaal getal te tellen, volgt ook dat de verzameling van alle rationale getallen aftelbaar zijn.

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