Cantors eerste overaftelbaarheidsbewijs

Cantors eerste overaftelbaarheidsbewijs toont aan dat de verzameling van alle reële getallen een overaftelbare verzameling is. Dit bewijs is anders dan het diagonaalbewijs van Cantor. Het eerste overaftelbaarheidsbewijs van Cantor werd in 1874 gepubliceerd, in een artikel dat ook een bewijs bevat dat de verzameling van de reële algebraïsche getallen een aftelbare verzameling is en een bewijs van het bestaan van transcendente getallen.

Stelling

Laat $𝐑$ een verzameling zijn die

• ten minste twee elementen bevat,
• totaal geordend is,
• dicht geordend is, dat wil zeggen dat er tussen twee elementen altijd een ander ligt,
• geen gaten heeft, dat wil zeggen dat als $𝐑$ in twee partities $A$ en $B$ wordt verdeeld, zodanig dat ieder element van $A$ kleiner is dan ieder element van $B$, dat er dan een element $c\in 𝐑$ is, zo dat ieder element dat kleiner is dan $c$ in $A$ is en ieder element dat groter is dan $c$ in $B$ is. Daarbij ligt $c$ ofwel in $A$ ofwel in $B$, zoals bij een dedekindsnede.

Dan is $𝐑$ overaftelbaar.

De genoemde eigenschappen gelden in het bijzonder voor $ℝ$, de verzameling van de reële getallen. Ze gelden ook voor elk interval in $ℝ$, zoals $[0,1⟩$, zodat ook deze intervallen overaftelbaar zijn. Voor $\mathbb{Q}$, de verzameling van rationale getallen, gelden weliswaar de eerste drie eigenschappen, maar niet de vierde, vanwege het volgende tegenvoorbeeld: $A=\{q\in \mathbb{Q}\mid q<\sqrt{2}\}$ en $B=\{q\in \mathbb{Q}\mid q>\sqrt{2}\}$ vormen een partitie van $\mathbb{Q}$, maar $\sqrt{2}\notin \mathbb{Q}$.