title: Stelling van Cantor
text: 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  
  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.
  
  Bewijs 
  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 
  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. 
  
  Kardinaalgetal
  Verzamelingenleer
  Wiskundige stelling