Stelling van Cantor

Wiskundige stelling uit de verzamelingenleer

In de elementaire verzamelingenleer stelt de stelling van Cantor, dat voor elke verzameling de verzameling van alle deelverzamelingen van (de machtsverzameling van ) een strikt grotere kardinaliteit heeft dan zelf. Voor eindige verzamelingen kan de stelling van Cantor bewezen worden met een veel eenvoudiger bewijs dan voor oneindige verzamelingen. Voor een eindige verzameling met elementen kunnen de deelverzamelingen eenvoudig geteld worden: de lege verzameling, de deelverzamelingen met slechts één element, die met twee elementen, etc. Samen zijn dat deelverzamelingen, en voor natuurlijke getallen . Maar de stelling is ook waar voor oneindige verzamelingen. In het bijzonder is de machtsverzameling van een aftelbare oneindige verzameling overaftelbaar. De stelling is naar de Duitse wiskundige Georg Cantor genoemd, die de stelling opstelde en ook bewees.

Geschiedenis

bewerken

Cantor gaf in essentie het hierboven beschreven bewijs in een in 1891 gepubliceerd artikel Über eine Frage der elementare Mannigfaltigkeitslehre, waar zijn diagonaalargument voor de onaftelbaarheid van de reële getallen ook voor het eerst voorkomt (hij had de onaftelbaarheid van de reële getallen eerst op een andere methode bewezen). De versie van dit argument, die hij in het artikel gaf, werd geformuleerd in termen van de indicatorfuncties op een verzameling in plaats van in deelverzamelingen van een verzameling. Hij toonde aan dat als   een functie is die gedefinieerd is op  , waarvan de waarden 2-waardige functies op   zijn, dat dan de 2-waardige functie   niet in het bereik van   liggen.

Russell gaf een zeer vergelijkbaar bewijs in zijn Principles of Mathematics (1903, sectie 348), waar hij laat zien dat er meer propositionele functies dan objecten zijn. "Laten wij aannemen dat er een correlatie van alle objecten en propositionele functies bestaat en laat   de functie zijn die met   gecorreleerd is. Dan geldt "niet- ", dat wil zeggen dat "  geldt niet voor  " een propositionele functie is, die niet is opgenomen in deze correlatie; want deze propositionele functie is waar of onwaar met betrekking tot   naargelang   waar of onwaar is met betrekking tot  , en daarom verschilt het van   voor elke waarde van  ". Hij schrijft het idee achter zijn bewijs aan Cantor toe.

Ernst Zermelo beschreef een stelling, die hij de stelling van Cantor noemde, en die hetzelfde was als de hierboven beschreven vorm, in zijn in 1908 gepubliceerde artikel, dat de fundamenten legde voor de moderne verzamelingenleer, Untersuchungen über die Grundlagen der Mengenlehre I. Zijn Zermelo-verzamelingenleer werd bekend.

Twee verzamelingen zijn dan en slechts dan gelijkmachtig (dat wil zeggen dat zij dezelfde kardinaliteit hebben) als er een een-op-een correspondentie tussen hen bestaat. Om de stelling van Cantor te bewijzen volstaat het om aan te tonen dat gegeven enige verzameling   er geen functie   van   in de machtsverzameling   van  , surjectief kan zijn. Dat wil zeggen dat er bij een functie   van   in   ten minste één deelverzameling van   is die geen element is van het beeld van   onder  . Een dergelijke deelverzameling,  , wordt gegeven door de volgende constructie:

 

Voor alle   is  , want óf   óf  . Als   en  , dan  , en als   en  , dan  .

Er is dus geen   zodanig dat  ; met andere woorden   is niet in het beeld van  . Omdat   een element van de machtsverzameling van   is, heeft de machtsverzameling van   een grotere kardinaliteit dan   zelf.

Vanwege het dubbele voorkomen van   in de uitdrukking  , is dit Cantors diagonaalargument.

Toelichting

bewerken

Als   aftelbaar oneindig is, kan zonder verlies van algemeenheid  , de verzameling van natuurlijke getallen, genomen worden.

Stel nu dat   gelijkmachtig is met haar machtsverzameling   en laat   de bijectie zijn van   op  .   zou er zo uit kunnen zien:

 

Dan zijn sommige natuurlijke getallen gekoppeld aan deelverzamelingen die dat getal zelf bevatten. In het voorbeeld is bijvoorbeeld het getal 2 gekoppeld aan de deelverzameling {1, 2, 3}, die 2 als element bevat. Laten we dergelijke getallen 'egoïstisch' noemen. Andere natuurlijke getallen worden gekoppeld met deelverzamelingen die dat getal niet bevatten. In het voorbeeld is het getal 1 bijvoorbeeld gekoppeld aan de deelverzameling {4, 5}, die het getal 1 duidelijk niet bevat. Op gelijke wijze zijn de getallen 3 en 4 'niet-egoïstisch'.

Laat   de verzameling van alle niet-egoïstische natuurlijke getallen zijn. De machtsverzameling   bevat alle verzamelingen van natuurlijke getallen, en dus bevat deze verzameling ook   als een element. Daarom moet   het beeld onder   zijn van een natuurlijk getal, zeg  . Maar als   een element van   is, dan is   egoïstisch, omdat het in de corresponderende verzameling voorkomt. Als   egoïstisch is, kan   geen element van   zijn, aangezien   alleen niet-egoïstische getallen bevat. Maar als   geen element is van  , is   niet-egoïstisch en moet   in   voorkomen, wederom op basis van de definitie van  .

Dit is een tegenstrijdigheid en dus is de oorspronkelijke veronderstelling dat er een bijectie tussen   en   bestaat, tegengesproken.

Merk op dat de verzameling   leeg kan zijn. Dit zou betekenen dat elk natuurlijk getal   op een verzameling van natuurlijke getallen, die   bevat, afgebeeld wordt. Dan wordt elk getal afgebeeld op een niet-lege verzameling en wordt dus geen enkel getal afgebeeld op de lege verzameling. Maar de lege verzameling is een element van  , zodat de afbeelding geen bijectie is.

Uit het voorgaande volgt dat de kardinaliteit van   en   niet aan elkaar gelijk zijn. En omdat de kardinaliteit van   niet lager kan zijn dan de kardinaliteit van  , omdat   alle singletons bevat. Zo blijft er slechts de mogelijkheid over dat de kardinaliteit van   strikt groter is dan die van  . Dat is de stelling van Cantor.

Voor een gevolg van de stelling van Cantor, zie Beet-getallen.