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  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  in twee niet-lege deelverzamelingen  en  gepartitioneerd is, zodanig dat elk element van  kleiner is dan elk element van , dan is er een element , zo dat elk element dat kleiner is dan  in  is en elk element dat groter is dan  in  is. Daarbij is  ofwel in  ofwel in  (zie dedekindsnede).

Dan is  overaftelbaar.

De genoemde eigenschappen gelden in het bijzonder voor de reële getallen , en ook voor elk willekeurig gekozen interval in  (zoals ), zodat ook de intervallen overaftelbaar zijn.

Bewijs
Allereerst moet worden opgemerkt dat uit de dichte en totale ordening volgt dat tussen twee elementen  met  een oneindig aantal elementen van  ligt. Waren er slechts eindig veel, dan was er een grootste, zeg . Maar tussen  en  is weer een ander element , wat in tegenspraak is met de maximaliteit van .

Om de overaftelbaarheid te bewijzen, veronderstelt men dat  aftelbaar is, bijvoorbeeld door de aftelling . Zonder verlies van algemeenheid kan aangenomen worden dat  (anders verwisselt men deze twee elementen). Definieer nu twee rijen  en  met:

 en .

Dan is .

waarbij  de kleinste index is groter dan de tevoren voor  gekozen index en waarvoor geldt . Dit is mogelijk omdat  dicht geordend is. Volgens de allereerst gemaakte opmerking zijn er oneindig veel indices  met en hoogstens een eindig aantal hiervan worden door de vergelijking met de bij  gekozen index uitgesloten.

waarbij  de kleinste index is groter dan de tevoren voor  geselecteerde index en waarvoor geldt dat . Ook dit is mogelijk omdat  dicht geordend is.

De rij  is monotoon strikt stijgend en de reeks  is monotoon strikt dalend, en de twee rijen begrenzen elkaar weerzijds, aangezien  voor elke .

Laat nu  de verzameling van elementen van  zijn die kleiner zijn dan alle  en  het complement van . Dan bevat  in ieder geval alle  en  alle ; de twee verzamelingen zijn dus niet leeg. Bovendien is elk element van  groter dan elk element van , want als  en  is, dan is er een  met  volgens de definitie van ; maar dan volgt  volgens de definitie van . Dus is  een dedekindsnede en aangezien  dicht geordend is, bestaat er een  waarvoor geldt  voor elke .

Daar  net als elk element van  in de rij  optreedt, is er een index  zodat . Omdat c niet gelijk is aan  en , is . Laat  het kleinste natuurlijke getal met de eigenschap dat  voor  of  voor . In beide gevallen is er een tegenspraak met de keuze van , aangezien  en  .

De veronderstelling dat  aftelbaar is, is dus niet correct. Dus is  overaftelbaar.

Voetnoten

Geschiedenis van de wiskunde
Verzamelingenleer