Cantors eerste overaftelbaarheidsbewijs

Bewijs uit het ongerijmde 

Het is een bewijs uit het ongerijmde.

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

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

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

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

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

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

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

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

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

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

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

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