Stelling van Cantor

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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 genoemd naar de Duitse wiskundige Georg Cantor, die de stelling opstelde en ook bewees.

Bewijs[bewerken]

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 een deelverzameling van is die geen element van het afbeelding van onder is. 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.

Omwille van de dubbele voorkomen van in de uitdrukking "", is dit Cantors diagonaalargument.

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

Laten wij, om greep op het bewijs te krijgen, dit bewijs onderzoeken voor het specifieke geval dat aftelbaar oneindig is. Zonder verlies van algemeenheid kan men , de verzameling van natuurlijke getallen, nemen.

Stel dat gelijkmachtig is met haar machtsverzameling .

bevat oneindige deelverzamelingen van , bijvoorbeeld de verzameling van alle even getallen {2, 4, 6,...} evenals de lege verzameling. bevat dus onder meer en .

Nu wij greep hebben op hoe de elementen van eruitzien, laat ons proberen elk element van aan elk element van te koppelen om zo aan te tonen dat deze oneindige verzamelingen bijectief zijn. Met andere woorden wij zullen proberen elk element van met een element uit de oneindige verzameling 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:

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 element bevat. Laten we dergelijke getallen egoïstisch noemen. Andere natuurlijke getallen worden gekoppeld met deelverzamelingen die dat getal 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 de verzameling van alle niet-egoïstische natuurlijke getallen zijn. Per definitie bevat de machtsverzameling alle verzamelingen van natuurlijke getallen, en dus bevat deze verzameling ook als een element. Daarom moet aan enig natuurlijk getal kunnen worden gekoppeld, zeg . Dit veroorzaakt echter een probleem. Als een element van is, dan is egoïstisch, omdat het in de corresponderende verzameling voorkomt. Als egoïstisch is, dan kan geen element van zijn, aangezien immers was gedefinieerd als alleen niet-egoïstische getallen te bevatten. 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, omdat het natuurlijke getal ofwel in ofwel niet in moet voorkomen, maar geen van de twee gevallen mogelijk is. Daarom is er geen natuurlijke getal dat kan worden gekoppeld met , en hebben wij onze 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, 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 , zodat de afbeelding nog steeds niet afdekt.

Via dit bewijs uit het ongerijmde hebben wij bewezen dat de kardinaliteit van en niet aan elkaar gelijk kunnen zijn. We weten ook dat de kardinaliteit van niet lager kan zijn dan de kardinaliteit van , omdat per definitie alle singletons bevat, en deze eenlingen van binnenuit een "kopie" van vormen. Zo blijft er slechts een mogelijkheid over, en dat is dat de kardinaliteit van strikt genomen groter is dan de kardinaliteit van , 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 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 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.