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 bewerken
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 kan worden verdeeld, dus in twee niet-lege deelverzamelingen en , zodanig dat ieder element van kleiner is dan elk element van , dat er dan een element is, zo dat ieder element dat kleiner is dan in is en ieder element dat groter is dan in is. Daarbij ligt ofwel in ofwel in , zoals bij een dedekindsnede.
Dan is overaftelbaar.
De genoemde eigenschappen gelden in het bijzonder voor de reële getallen en ook voor ieder willekeurig gekozen interval in zoals , zodat ook de intervallen overaftelbaar zijn.
Het is een bewijs uit het ongerijmde.
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 |