Overaftelbare verzameling

Een overaftelbare verzameling is in de wiskunde een verzameling waarvan de elementen niet kunnen worden afgeteld. Het is in ieder geval een oneindige verzameling, zelfs zo dat de kardinaliteit ervan groter is dan die van de verzameling $\mathbb {N}$ van de natuurlijke getallen. Een overaftelbare verzameling heeft wezenlijk meer elementen dan de natuurlijke getallen. Dit betekent dat er geen bijectie tussen een overaftelbare verzameling en $\mathbb {N}$ kan worden gegeven. Een verzameling die behalve alle natuurlijke getallen nog meer elementen bevat, kan daarentegen aftelbaar zijn, zoals de gehele getallen. De kardinaliteit van $\mathbb {N}$ is dezelfde als de kardinaliteit van de rationale getallen $\mathbb {Q}$, net zoals van de gehele getallen.

De kardinaliteit van $\mathbb {N}$ wordt $\aleph _{0}$ genoemd. Een voorbeeld van een overaftelbare verzameling vormen de reële getallen $\mathbb {R}$ groter dan twee en kleiner dan drie. Daarvan zijn er zo veel dat ze niet kunnen worden afgeteld, is die verzameling overaftelbaar, dus heeft een grotere kardinaliteit dan $\mathbb {N}$.

Het diagonaalbewijs van Cantor is een bewijs uit het ongerijmde dat $\mathbb {R}$ niet kan worden afgeteld, dus dat $\mathbb {R}$ overaftelbaar is. De verzameling van de transcendente getallen is overaftelbaar. Hun kardinaliteit is gelijk aan die van $\mathbb {R}$. Twee verzamelingen met dezelfde kardinaliteit worden gelijkmachtig genoemd.

Verzameling en machtsverzameling

Met een generalisatie van het diagonaalbewijs van Cantor kan worden bewezen dat de machtsverzameling ${\mathcal {P}}(S)$ van een oneindige verzameling $S$ overaftelbaar is. Algemeen geldt dat de machtsverzameling een hogere kardinaliteit heeft dan de verzameling zelf. Daarmee ontstaat de mogelijkheid steeds verzamelingen met een hogere kardinaliteit te construeren.

$\mathbb {R}$ wordt vanwege het verschil in kardinaliteit met $\mathbb {Q}$ wel het continuüm genoemd. Er is volgens de continuümhypothese geen overaftelbare verzameling met een kleinere kardinaliteit dan $\mathbb {R}$.

Om de kardinaliteit van verschillende oneindige verzamelingen met elkaar te kunnen vergelijken worden zij in transfiniete getallen ingedeeld.