Cantor-tétel

A Cantor-tétel (ejtsd: kántor) egy fontos halmazelméleti eredmény. A tételt Georg Cantor német matematikusról nevezték el, aki először mondta ki és bizonyította azt a 19. század végén.

A tétel

Tétel (Cantor-tétel): Ha H halmaz, akkor nincs olyan H-n értelmezett f függvény, mely ráképez a H hatványhalmazára.

Következmény: Ha H halmaz, és ${\mathcal {P}}(H)$ jelöli a H halmaz hatványhalmazát, akkor

$|H|<|{\mathcal {P}}(H)|$,

vagyis H számossága kisebb, mint H hatványhalmazának számossága.

Ugyanis az E és F halmazokat akkor mondjuk azonos számosságúnak, ha létezik E és F között bijekció, azaz létezik E-ből F-be injekció, mely egyben szürjekció is, azaz ráképez F-re. Utóbbit viszont a Cantor-tétel kizárja H és ${\mathcal {P}}(H)$ esetében, így a

$|H|=|{\mathcal {P}}(H)|$

egyenlőség nem állhat fenn. Ellenben biztosan létezik H-ból injekció H hatványhalmazába (ilyen például ha H minden eleméhez hozzárendeljük az őt tartalmazó egyetlen elemű halmazt), ezért a

$|H|\leq |{\mathcal {P}}(H)|$

egyenlőtlenség teljesül.

Megjegyzés: Néha a következményt szokták Cantor-tételnek nevezni.

Bizonyítása

Indirekten bizonyítunk. Legyen

$f:H\rightarrow {\mathcal {P}}(H)$

olyan függvény, mely ráképez P(H)-ra. Definiáljuk az

$F:=\{x\in H\mid x\notin f(x)\}$

halmazt. Világos, hogy F ∈ P(H). Másrészt mivel f ráképezés, ezért van olyan h ∈ H elem, hogy f(h)=F. F definíciója miatt azonban ebből

$h\in f(h)\Leftrightarrow h\notin f(h)$

következik, ami ellentmondás. ■

Története

A tételt 1891-ben, Über eine elementare Frage der Mannigfaltigkeitslehre címen megjelent cikkében bizonyította Georg Cantor. Ebben cikkben jelent meg először a Cantor-féle átlós eljárás is, amivel bizonyította, hogy a valós számok nem megszámlálhatóak. (Ennek első bizonyítása 1874-ben jelent meg.)

A tétel egy szellemes interpretációja

Az alábbi történet Raymond Smullyantől származik. Jól érzékelteti a Cantor-tétel bizonyításában lévő jellegzetes érvelési módszert.

Valahol egy távoli galaxisban a lakosok nagyon szeretnek bizottságokba tömörülni. Minden lehetséges módon alkotnak egy-egy bizottságot. (Van olyan bizottság, amiben a galaxis összes lakója tag, és olyan is van, melyben egyáltalán nincsenek tagok /ebben a bizottságban bizonyára nem kerül sor éles vitákra/). A galaxis egy jegyzője elhatározta, hogy számba veszi a „megszámlálhatatlan” sok bizottságot, és úgy döntött, elnevezi őket a galaxis lakóiról.

Most már az a kérdés, hogy végére érhet-e a jegyző ennek a munkának, vagy akárhogy is igyekszik, nem tud minden bizottságnak nevet adni (az egyszerűség kedvéért tegyük fel, hogy végtelen idő áll rendelkezésére). A galaxis egy matematikusát kérte meg, hogy adjon erre választ.

A matematikus sejtette, hogy a jegyző nem tudja elnevezni a bizottságokat, ezért így okoskodott. „Tegyük fel, hogy a munkát el tudod végezni. Ekkor lesznek olyan galaxislakók, akik tagjai lesznek a saját magukról elnevezett bizottságnak, és lesznek olyanok, akik nem. Nevezzük a Szerények Bizottságának azt a bizottságot, mely azokból a lakosokból áll, akikről neveztek el bizottságot, de ők nem tagjai a róluk elnevezett bizottságnak. Feltevésünk szerint a Szerények Bizottságát is el tudnád nevezni valakiről. De vajon a Szerények Bizottságának névadója tagja a Szerények Bizottságának vagy nem? Ha tagja, akkor nem szerény, miközben a Szerények Bizottságának tagja. Ha nem tagja, akkor viszont tagja kell, hogy legyen a róla elnevezett bizottságnak. Mindenképpen ellentmondásra jutunk, és te nem fogod tudni ily módon rendbe szedni a bizottságokat.”

További információk

• A végtelenen túl, YOUPROOF