Cantors eerste overaftelbaarheidsbewijs

Cantors eerste overaftelbaarheidsbewijs toont aan dat de verzameling van alle reële getallen overaftelbaar is. Dit bewijs verschilt van het meer bekende bewijs, waarin Cantor zijn diagonaalargument gebruikt. 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 aftelbaar is en een bewijs van het bestaan van transcendente getallen.

De stelling

Laat $\mathbf {R}$ een verzameling zijn die

• ten minste twee elementen bevat,
• totaal geordend is,
• dicht geordend is, d.w.z. dat tussen twee elementen altijd een ander is,
• geen gaten heeft, d.w.z.: als $\mathbf {R}$ in twee niet-lege deelverzamelingen $A$ en $B$ gepartitioneerd is, zodanig dat elk element van $A$ kleiner is dan elk element van $B$, dan is er een element $c$, zo dat elk element dat kleiner is dan $c$ in $A$ is en elk element dat groter is dan $c$ in $B$ is. Daarbij is $c$ ofwel in $A$ ofwel in $B$ (zie dedekindsnede).

Dan is $\mathbf {R}$ overaftelbaar.

De genoemde eigenschappen gelden in het bijzonder voor de reële getallen $\mathbb {R}$, en ook voor elk willekeurig gekozen interval in $\mathbb {R}$ (zoals $[0,1$), zodat ook de intervallen overaftelbaar zijn.

Bewijs

Allereerst moet worden opgemerkt dat uit de dichte en totale ordening volgt dat tussen twee elementen $a,b\in \mathbf {R}$ met $a<b$ een oneindig aantal elementen van $\mathbf {R}$ ligt. Waren er slechts eindig veel, dan was er een grootste, zeg $x$. Maar tussen $x$ en $b$ is weer een ander element $x<y<b$, wat in tegenspraak is met de maximaliteit van $x$.

Om de overaftelbaarheid te bewijzen, veronderstelt men dat $\mathbf {R}$ aftelbaar is, bijvoorbeeld door de aftelling $x_{1},x_{2},\ldots \in \mathbf {R}$. Zonder verlies van algemeenheid kan aangenomen worden dat $x_{1}<x_{2}$ (anders verwisselt men deze twee elementen). Definieer nu twee rijen $(a_{1},a_{2},\ldots )$ en $(b_{1},b_{2},\ldots )$ met:

$a_{1}=x_{1}$ en $b_{1}=x_{2}$.

Dan is $a_{1}<b_{1}$.

$a_{n+1}=x_{i}$

waarbij $i$ de kleinste index is groter dan de tevoren voor $b_{n}$ gekozen index en waarvoor geldt $a_{n}<x_{i}<b_{n}$. Dit is mogelijk omdat $\mathbf {R}$ dicht geordend is. Volgens de allereerst gemaakte opmerking zijn er oneindig veel indices $i$ met$a_{n}<x_{i}<b_{n}$ en hoogstens een eindig aantal hiervan worden door de vergelijking met de bij $b_{n}$ gekozen index uitgesloten.

$b_{n+1}=x_{i}$

waarbij $i$ de kleinste index is groter dan de tevoren voor $a_{n+1}$ geselecteerde index en waarvoor geldt dat $a_{n+1}<x_{i}<b_{n}$. Ook dit is mogelijk omdat $\mathbf {R}$ dicht geordend is.

De rij $(a_{n})$ is monotoon strikt stijgend en de reeks $(b_{n})$ is monotoon strikt dalend, en de twee rijen begrenzen elkaar weerzijds, aangezien $a_{n}<b_{n}$ voor elke $n$.

Laat nu $A$ de verzameling van elementen van $\mathbf {R}$ zijn die kleiner zijn dan alle $b_{n}$ en $B$ het complement van $A$. Dan bevat $A$ in ieder geval alle $a_{n}$ en $B$ alle $b_{n}$; de twee verzamelingen zijn dus niet leeg. Bovendien is elk element van $B$ groter dan elk element van $A$, want als $x\in A$ en $y\in B$ is, dan is er een $n$ met $b_{n}\leq y$ volgens de definitie van $B$; maar dan volgt $x<b_{n}\leq y$ volgens de definitie van $A$. Dus is $(A,B)$ een dedekindsnede en aangezien $\mathbf {R}$ dicht geordend is, bestaat er een $c$ waarvoor geldt $a_{n}<c<b_{n}$ voor elke $n$.

Daar $c$ net als elk element van $\mathbf {R}$ in de rij $(x_{i})$ optreedt, is er een index $j$ zodat $c=x_{j}$. Omdat c niet gelijk is aan $a_{1}$ en $b_{1}$, is $j>2$. Laat $n$ het kleinste natuurlijke getal met de eigenschap dat $a_{n+1}=x_{i}$ voor $i>j$ of $b_{n+1}=x_{i}$ voor $i>j$. In beide gevallen is er een tegenspraak met de keuze van $i$, aangezien $a_{n}<x_{j}<b_{n}$ en $a_{n+1}<x_{j}<b_{n}$ .

De veronderstelling dat $\mathbf {R}$ aftelbaar is, is dus niet correct. Dus is $\mathbf {R}$ overaftelbaar.