Paradoxen van de verzamelingenleer

De naïeve verzamelingenleer bevat enkele interessante paradoxen, die uiteindelijk hebben geleid tot de ontwikkeling van een uitgebreidere verzamelingenleer. Die paradoxen berusten vaak op het feit dat het in de klassieke, naïeve verzamelingenleer mogelijk is dat een verzameling zichzelf als element bevat.

De paradox van Russell

Een van de bekendste paradoxen is de paradox van Russell. We kunnen die zo definiëren: neem een verzameling N die precies die verzamelingen bevat die zichzelf niet als element bevatten. Als een verzameling dus zichzelf als element bevat, hoort ze niet bij de verzameling N. Als ze zichzelf niet bevat, hoort ze wel bij de verzameling N.

De vraag is of verzameling N de verzameling N als element bevat, dus zichzelf?

Door de gevallen te onderzoeken komen we tot het volgende: als verzameling N de verzameling N niet bevat, dan is het een verzameling die zichzelf niet bevat en zou ze in verzameling N moeten zitten, dus er zou N ∈ N moeten gelden.

Maar als verzameling N het element N wel bevat, dan zou N ∈ N niet mogen gelden, want verzameling N bevat alleen verzamelingen die zichzelf niet als element bevatten.

De paradox is dus dat we altijd een van de voorwaarden schenden. Als N ∈ N, dan is dat in strijd met de definitie van verzameling N (die bevat alleen verzamelingen die zichzelf niet bevatten, en hier bevat N duidelijk N als element), en als niet geldt dat N ∈ N, dan schenden we de definitie van N opnieuw.

Zo'n verzameling kunnen we dus niet construeren, en dat zou in een goede verzamelingenleer niet mogen gebeuren.

De paradox van Russell heeft ook een paar natuurlijke interpretaties. Bijvoorbeeld de barbiersparadox. In een stad woont een barbier die precies die mensen scheert die zichzelf niet scheren. Dan dient zich de vraag aan: scheert de barbier zichzelf?

De paradox van Cantor

Een andere paradox is die van Cantor. Die berust op het feit dat als we een verzameling M hebben, de machtsverzameling P(M) ervan (de verzameling van alle deelverzamelingen van M) altijd een hogere kardinaliteit heeft, dus groter is. Bij eindige verzamelingen zie je dat meteen, voor oneindige verzamelingen is het gemakkelijk te bewijzen. Deze uitspraak heet overigens de stelling van Cantor, en de precieze formulering en het bewijs vind je op Wikipedia.

De paradox zelf is eenvoudiger dan de vorige. Stel je de verzameling van alle verzamelingen voor en noem die M. Voor elke verzameling N geldt dus dat N ∈ M. Maar volgens de stelling van Cantor is de machtigheid van de machtsverzameling P(M) groter dan de machtigheid van M. Dat is in strijd met het feit dat M alle verzamelingen bevat: als de verzameling P(M) groter is dan M, moet ze noodzakelijk elementen bevatten die verzameling M niet bevat.