Machts­verzamelingen

B is een deel­verzameling van A als B louter elementen heeft die ook in A zitten. De lege verzameling is daarmee een deelverzameling van alle verzamelingen, en iedere verzameling is een deelverzameling van zichzelf.

De verzameling van alle deelverzamelingen van A heet de machtsverzameling van A, en wordt aangeduid als M(A).

De Stelling van Cantor zegt dat de cardinaliteit van M(A) altijd groter is dan de cardinaliteit van A. Voor eindige verzamelingen is dat gemakkelijk in te zien, want voor ieder element a van A zit de eenheids­verzameling {a} in M(A) — dus dat maakt M(A) al minstens zo groot als A —, en daarenboven zit ook de lege verzameling {} in M(A), wat M(A) strict groter maakt dan A.

Voor oneindige verzamelingen valt het aan te tonen met een diagonaal­argument. Dat gaat als volgt. ((Nog uitleggen waarom dit een diagonaalargument is: AxA uitzetten.))

Stel dat het mogelijk was aan ieder element van M(A) een uniek element van A te koppelen — dat er een (oneindige) lijst zou bestaan met links alle elementen van M(A), en daarnaast rechts steeds een uniek element van A. Dan zijn er voor iedere a uit A drie mogelijkheden:

A⁺
a hoort bij een element van M(A) waar a zelf inzit.
Bijvoorbeeld: bij {a₁, a₂, a₅, a₆} hoort a₁.
A⁺
a hoort bij een element van M(A) waar a niet inzit.
Bijvoorbeeld: bij {a₁, a₂, a₄} hoort a₃.
A⁰
a hoort bij geen enkel element van M(A).

Het is duidelijk dat A⁺∪A⁻∪A⁰ = A.

Ergens op die lijst moet A⁻ voorkomen, want A⁻ is een element van M(A), en alle elementen van M(A) staan op de lijst. Laat a het element van A zijn waar A⁻ bij hoort, dan moet a in A⁰ of in A⁻ of in A⁰ zitten — maar alle drie zijn onmogelijk:

Stel dat a in A⁺ zit
Als a in A⁺ zou zitten verwijst het naar zichzelf, dus dan moet het ook in A⁻ zitten — maar dat kan het alleen als het niet naar zichzelf verwijst.
Stel dat a in A⁻ zit
Als a in A⁻ zit kan het het niet naar zichzelf verwijzen — maar het verwijst naar A⁻, waar het dus niet in mag zitten.
Stel dat a in A⁰ zit
Als a in A⁰ zit verwijst er geen enkel element van M(A) naar, en dus ook A⁻ niet.

De Cantors paradox luidt als volgt: Zij A de verzameling die alles (of op zijn minst alle verzamelingen) bevat. Dan is volgens Cantors stelling de cardinaliteit van M(A) strikt groter dan die van A. Anderzijds omvat A alles, dus ook ieder element van M(A), zodat de cardinaliteit van A minstens zo groot moet zijn als die van M(A). Conclusie: er bestaat geen verzameling die alles bevat.