Stelling van Cantor

In de elementaire verzamelingenleer stelt de stelling van Cantor, dat voor elke verzameling $A$ de verzameling van alle deelverzamelingen van $A$ (de machtsverzameling van $A$) een strikt grotere kardinaliteit heeft dan $A$ 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 $n$ elementen kunnen de deelverzamelingen eenvoudig geteld worden: de lege verzameling, de deelverzamelingen met slechts één element, die met twee elementen, etc. Samen zijn dat $2^{n}$ deelverzamelingen, en $n<2^{n}$ voor natuurlijke getallen $n$. 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 $f$ een functie is die gedefinieerd is op $X$, waarvan de waarden 2-waardige functies op $X$ zijn, dat dan de 2-waardige functie $G(x)=1-f(x)(x)$ niet in het bereik van $f$ 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 $\phi (x)$ de functie zijn die met $x$ gecorreleerd is. Dan geldt "niet-$\phi (x)$", dat wil zeggen dat "$\phi (x)$ geldt niet voor $x$" een propositionele functie is, die niet is opgenomen in deze correlatie; want deze propositionele functie is waar of onwaar met betrekking tot $x$ naargelang $\phi (x)$ waar of onwaar is met betrekking tot $x$, en daarom verschilt het van $\phi (x)$ voor elke waarde van $x$". 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 $A$ er geen functie $f$ van $A$ in de machtsverzameling $P(A)$ van $A$, surjectief kan zijn. Dat wil zeggen dat er bij een functie $f$ van $A$ in $P(A)$ ten minste één deelverzameling van $A$ is die geen element is van het beeld van $A$ onder $f$. Een dergelijke deelverzameling, $B\in P(A)$, wordt gegeven door de volgende constructie:

$B=\{x\in A:x\notin f(x)\}$

Voor alle $x\in A$ is $f(x)\neq B$, want óf $x\in f(x)$ óf $x\notin f(x)$. Als $x\in f(x)$ en $f(x)=B$, dan $x\notin f(x)$, en als $x\notin f(x)$ en $f(x)=B$, dan $x\notin B$.

Er is dus geen $x$ zodanig dat $f(x)=B$; met andere woorden $B$ is niet in het beeld van $f$. Omdat $B$ een element van de machtsverzameling van $A$ is, heeft de machtsverzameling van $A$ een grotere kardinaliteit dan $A$ zelf.

Vanwege het dubbele voorkomen van $x$ in de uitdrukking $x\notin f(x)$, is dit Cantors diagonaalargument.

Toelichting

Als $X$ aftelbaar oneindig is, kan zonder verlies van algemeenheid $X=\mathbb {N}$, de verzameling van natuurlijke getallen, genomen worden.

Stel nu dat $\mathbb {N}$ gelijkmachtig is met haar machtsverzameling ${\mathcal {P}}(\mathbb {N} )$ en laat $f$ de bijectie zijn van $\mathbb {N}$ op ${\mathcal {P}}(\mathbb {N} )$. $f$ zou er zo uit kunnen zien:

$\mathbb {N} {\begin{Bmatrix}1&\Longleftrightarrow &\{4,5\}\\2&\Longleftrightarrow &\{1,2,3\}\\3&\Longleftrightarrow &\{4,5,6\}\\4&\Longleftrightarrow &\{1,3,5\}\\\vdots &\vdots &\vdots \end{Bmatrix}}P(\mathbb {N} )$

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 $D$ de verzameling van alle niet-egoïstische natuurlijke getallen zijn. De machtsverzameling ${\mathcal {P}}(\mathbb {N} )$ bevat alle verzamelingen van natuurlijke getallen, en dus bevat deze verzameling ook $D$ als een element. Daarom moet $D$ het beeld onder $f$ zijn van een natuurlijk getal, zeg $D=f(d)$. Maar als $d$ een element van $D$ is, dan is $d$ egoïstisch, omdat het in de corresponderende verzameling voorkomt. Als $d$ egoïstisch is, kan $d$ geen element van $D$ zijn, aangezien $D$ alleen niet-egoïstische getallen bevat. Maar als $d$ geen element is van $D$, is $d$ niet-egoïstisch en moet $d$ in $D$ voorkomen, wederom op basis van de definitie van $D$.

Dit is een tegenstrijdigheid en dus is de oorspronkelijke veronderstelling dat er een bijectie tussen $\mathbb {N}$ en ${\mathcal {P}}(\mathbb {N} )$ bestaat, tegengesproken.

Merk op dat de verzameling $D$ leeg kan zijn. Dit zou betekenen dat elk natuurlijk getal $n$ op een verzameling van natuurlijke getallen, die $n$ 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 ${\mathcal {P}}(\mathbb {N} )$, zodat de afbeelding geen bijectie is.

Uit het voorgaande volgt dat de kardinaliteit van $\mathbb {N}$ en ${\mathcal {P}}(\mathbb {N} )$ niet aan elkaar gelijk zijn. En omdat de kardinaliteit van ${\mathcal {P}}(\mathbb {N} )$ niet lager kan zijn dan de kardinaliteit van $\mathbb {N}$, omdat ${\mathcal {P}}(\mathbb {N} )$ alle singletons bevat. Zo blijft er slechts de mogelijkheid over dat de kardinaliteit van ${\mathcal {P}}(\mathbb {N} )$ strikt groter is dan die van $\mathbb {N}$. Dat is de stelling van Cantor.

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