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.^[1]

Stelling

Laat ${\displaystyle \mathbf {R} }$ 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 ${\displaystyle \mathbf {R} }$ in twee partities ${\displaystyle A}$ en ${\displaystyle B}$ wordt verdeeld, zodanig dat ieder element van ${\displaystyle A}$ kleiner is dan ieder element van ${\displaystyle B}$, dat er dan een element ${\displaystyle c\in \mathbf {R} }$ is, zo dat ieder element dat kleiner is dan ${\displaystyle c}$ in ${\displaystyle A}$ is en ieder element dat groter is dan ${\displaystyle c}$ in ${\displaystyle B}$ is. Daarbij ligt ${\displaystyle c}$ ofwel in ${\displaystyle A}$ ofwel in ${\displaystyle B}$, zoals bij een dedekindsnede.

Dan is ${\displaystyle \mathbf {R} }$ overaftelbaar.

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.

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

Voetnoten

1. Cantor, 1874, Engelse vertaling: Ewald 1996, blz. 840-843