Cantors eerste overaftelbaarheidsbewijs

wetenschappelijk artikel

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

De stellingBewerken

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.

BewijsBewerken

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.

VoetnotenBewerken

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