Stelling van Cantor

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de elementaire verzamelingenleer stelt de stelling van Cantor, dat voor enige verzameling A, de verzameling van alle deelverzamelingen van A (de machtsverzameling van A) strikt genomen een grotere kardinaliteit heeft dan A zelf. Voor eindige verzamelingen kan aangetoond worden dat de stelling van Cantor waar is met een veel eenvoudiger bewijs dan voor oneindige verzamelingen. Dit omdat naast deelverzamelingen van A met slechts een lidmaat, er nog anderen zijn, en sinds n < 2 n voor alle natuurlijke getallen n. Maar de stelling is ook waar voor oneindige verzamelingen. In het bijzonder is de machtsverzameling van een aftelbare oneindige verzameling overaftelbaar oneindig. De stelling is genoemd naar de Duitse wiskundige Georg Cantor, die de stelling opstelde en ook bewees.

Bewijs[bewerken]

Twee verzamelingen zijn gelijkmachtig (dat wil zeggen dat zij dezelfde kardinaliteit hebben) dan en slechts dan als er een een-op-een correspondentie tussen hen bestaat. Om de stelling van Cantor vast te stellen volstaat het om aan te tonen dat gegeven enige verzameling A er geen functie f van A in en op P(A), de machtsverzameling van A, surjectief kan zijn, dat wil zeggen het laten zien van het bestaan van ten minste een deelverzameling van A, die geen element van het afbeelding van A onder f is. Een dergelijke deelverzameling, B \in P(A), wordt gegeven door de volgende constructie:

B=\left\{\,x\in A : x\not\in f(x)\,\right\}.

Dit betekent, per definitie voor alle x in A, dat dan en slechts dan xB geldt als xf(x). Voor alle x kunnen de verzamelingen B en f(x) niet hetzelfde zijn, omdat B was geconstrueerd uit elementen van A, waarvan de afbeeldingen (onder f) zichzelf niet includeerden. Beschouw meer in het bijzonder enige xA, dan geldt of xf(x) of xf(x). In het eerste geval kan f(x) niet gelijk zijn aan B, omdat door aanname geldt dat xf(x). In het laatste geval kan f(x) niet gelijk zijn aan B, omdat door aanname geldt dat xf(x) en dat geldt xB door de constructie van B.

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

Een andere manier om over het bewijs na te denken is dat B, leeg of niet-leeg, altijd de machtsverzameling van A is. Voor f om op en naar ("upto") te zijn, moet enig element van A afbeelden op B. Maar dat leidt tot een tegenstrijdigheid: geen element van B kan afbeelden op B, omdat dan het criterium van lidmaatschap van B wordt tegengesproken, het element dat afbeeldt op B mag dus geen element van B zijn, wat betekent dat het element voldoet aan het criterium voor lidmaatschap van B, een andere tegenstrijdigheid. De veronderstelling dat een element van A afbeeldt op B moet dus onjuist zijn; f kan niet "op en naar" ("upto") zijn.

Omwille van de dubbele voorkomen van x in de uitdrukking "xf(x)", is dit Cantors diagonaalargument.

Een gedetailleerde uitleg van het bewijs wanneer X aftelbaar oneindig is[bewerken]

Laten wij, om greep op het bewijs te krijgen, dit bewijs onderzoeken voor het specifieke geval, wanneer X aftelbaar is. Zonder verlies van algemeenheid kan men X = N = {1, 2, 3,...}, de verzameling van natuurlijke getallen, nemen.

Stel dat N bijectief is met haar machtsverzameling P(N). Laat men nu een voorbeeld beschouwen van hoe P( N) eruitziet:

P(\mathbb{N})=\{\varnothing,\{1, 2\}, \{1, 2, 3\}, \{4\}, \{1, 5\}, \{3, 4, 6\}, \{2, 4, 6,\dots\},\dots\}.

P(N) bevat oneindige deelverzamelingen van N, bijvoorbeeld de verzameling van alle even getallen {2, 4, 6,...} evenals de lege verzameling.

Nu wij greep hebben op hoe de elementen van P(N) eruitzien, laat ons proberen elk element van N aan elk element van P(N) te koppelen om zo aan te tonen dat deze oneindige verzamelingen bijectief zijn. Met andere woorden wij zullen proberen elk element van N met een element uit de oneindige verzameling P(N) te paren, zodat geen enkel element uit de oneindige verzameling ongekoppeld blijft. Een dergelijke poging om elementen te koppelen 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}).

Gegeven een dergelijke koppeling, zijn sommige natuurlijke getallen gekoppeld aan deelverzamelingen, die dat getal zelf bevatten. In ons voorbeeld is bijvoorbeeld het getal 2 gekoppeld aan de deelverzameling {1, 2, 3}, die 2 als lidmaat bevat. Laten we dergelijke getallen egoïstisch noemen. Andere natuurlijke getallen worden gekoppeld met deelverzamelingen die dat geval niet bevatten. In ons 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.

Laten wij door gebruik te maken van dit idee een bijzondere verzameling van natuurlijke getallen construeren. Deze verzameling zal het bewijs uit het ongerijmde, dat wij zoeken, leveren. Laat D de verzameling van alle niet-egoïstische natuurlijke getallen zijn. Per definitie bevat de machtsverzameling P(N) alle verzamelingen van natuurlijke getallen, en dus bevat deze verzameling ook D als een element. Daarom moet D aan enig natuurlijk getal kunnen worden gekoppeld, zeg d. Dit veroorzaakt echter een probleem. Als d een element van D is, dan is d egoïstisch, omdat het in de corresponderende verzameling voorkomt. Als d egoïstisch is, dan kan d geen element van D zijn, aangezien D immers was gedefinieerd als alleen niet-egoïstische getallen te bevatten. Maar als d geen lidmaat is van D, dan is d niet egoïstisch en moet d in D voorkomen, wederom op basis van de definitie van D.

Dit is een tegenstrijdigheid, omdat het natuurlijke getal d ofwel in D ofwel niet in D moet voorkomen, maar geen van de twee gevallen mogelijk is. Daarom is er geen natuurlijke getal dat kan worden gekoppeld met D, en hebben wij onze oorspronkelijke veronderstelling, dat er een bijectie tussen N en P(N) bestaat, tegengesproken.

Merk op dat de verzameling D leeg kan zijn. Dit zou betekenen dat elk natuurlijk getal x op een verzameling van natuurlijke getallen, die x bevat, afbeeldt. Dan beeldt elk getal af op een niet-lege verzameling en beeldt geen enkel getal af op de lege verzameling. Maar de lege verzameling is een lidmaat van P(N), zodat de afbeelding nog steeds P(N) niet afdekt.

Via dit bewijs uit het ongerijmde hebben wij bewezen dat de kardinaliteit van N en P(N) niet aan elkaar gelijk kunnen zijn. We weten ook dat de kardinaliteit van P(N) niet lager kan zijn dan de kardinaliteit van N, omdat P(N) per definitie alle singletons bevat, en deze eenlingen van binnenuit een "kopie" van P(N) vormen. Zo blijft er slechts een mogelijkheid over, en dat is dat de kardinaliteit van P(N) strikt genomen groter is dan de kardinaliteit van N, waarmee de stelling van Cantor wordt.

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 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 een correlatie van alle objecten en enige propositionele functies geraakt is en laat phi-x de correlator van x zijn. Dan geldt "niet-phi-x(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 identiek was aan 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"); zie Zermelo-verzamelingenleer.

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