A halmazelmélet paradoxonai

A naiv halmazelmélet néhány érdekes paradoxont tartalmaz, amelyek végül a részletesebb halmazelmélet kidolgozásához vezettek. Ezek a paradoxonok gyakran arra a tényre épülnek, hogy a klasszikus, naiv halmazelméletben lehetséges, hogy egy halmaz önmagát tartalmazza elemként.

Russell-paradoxon

A legismertebb paradoxonok közé tartozik a Russell-paradoxon. Így fogalmazhatjuk meg: legyen az N halmaz, amely pontosan azokat a halmazokat tartalmazza, amelyek önmagukat nem tartalmazzák elemként. Tehát ha egy halmaz önmagát tartalmazza elemként, akkor nem tartozik az N halmazhoz. Ha önmagát nem tartalmazza, akkor az N halmazhoz tartozik.

A kérdés az, hogy az N halmaz tartalmazza-e elemként az N halmazt, vagyis önmagát?

Esetszétválasztással azt kapjuk, hogy: ha az N halmaz nem tartalmazza az N-et, akkor olyan halmazról van szó, amely önmagát nem tartalmazza, és benne kellene lennie az N halmazban, tehát igaznak kellene lennie, hogy N ∈ N.

Ha viszont az N halmaz tartalmazza az N elemet, akkor nem szabadna igaznak lennie, hogy N ∈ N, mert az N halmaz csak azokat a halmazokat tartalmazza, amelyek önmagukat nem tartalmazzák elemként.

A paradoxon tehát abban áll, hogy mindig megsértünk valamelyik feltételt. Ha N ∈ N, ez ellentmond az N halmaz definíciójának (csak olyan halmazokat tartalmaz, amelyek önmagukat nem tartalmazzák, itt viszont nyilvánvalóan az N tartalmazza az N-et elemként), ha pedig nem igaz, hogy N ∈ N, akkor ismét megsértjük az N definícióját.

Ilyen halmazt tehát nem tudunk megalkotni, aminek egy helyes halmazelméletben nem kellene megtörténnie.

A Russell-paradoxonnak több természetes értelmezése is van. Például a borbélyparadoxon. Egy városban van egy borbély, aki pontosan azokat az embereket borotválja, akik nem borotválják meg önmagukat. Felmerül a kérdés, hogy a borbély megborotválja-e önmagát?

Cantor-paradoxon

Egy másik paradoxon a Cantor-paradoxon. Ez arra a tényre épül, hogy ha van egy M halmazunk, akkor a P(M) hatványhalmazának (az M halmaz összes részhalmazának halmaza) mindig nagyobb a számossága, vagyis nagyobb. Véges halmazoknál ez első pillantásra látszik, végtelen halmazokra pedig könnyen bebizonyítható. Ezt az állítást egyébként Cantor-tételnek hívják, pontos megfogalmazása és bizonyítása a Wikipédián található.

Maga a paradoxon egyszerűbb, mint az előző. Képzeljük el az összes halmaz halmazát, jelöljük M-mel. Tehát bármely N halmazra igaz, hogy N ∈ M. A Cantor-tétel szerint azonban a P(M) hatványhalmaz számossága nagyobb, mint az M számossága. Ez viszont ellentmond annak, hogy az M az összes halmazt tartalmazza – ha a P(M) halmaz nagyobb, mint az M, akkor szükségszerűen tartalmaz olyan elemeket, amelyeket az M halmaz nem tartalmaz.