Cantor-tétel

A Wikipédiából, a szabad lexikonból.

A halmazelmélet Cantor-tétele a hatványhalmaz számosságának a halmaz számosságához képesti nagyobb számosságát állító eredmény.

[szerkesztés] 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, akkor

Megjegyzés - Néha ez utóbbi tételt szokták Cantor-tételnek nevezni. Mivel 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 ráképez F-re, ezért a tétel meggátolja, hogy a

egyenlőség fennálljon. Ellenben létezik H-ból injekció H hatványhalmazába ezért a

egyenlőtlenség teljesül.

[szerkesztés] A bizonyítás

A tétel bizonyítása - Indirekten bizonyítunk. Legyen

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

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

következik, ami ellentmondás. ■ Ezt Russel féle paradoxonnak hívjuk.

[szerkesztés] A tétel egy szellemes interpretációja

Ez a 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 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ára). 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ár hogy 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 a elnevezni a bizottságokat ezért így okoskodott. "Tegyük fel, hogy a munkát el tudod végezni. Ekkor leszenek 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, melyek nem tagjai a saját magukról elnevezett bizottságnak. Feltevésünk szerint a Szerények Bizottságát is meg 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 az róla elnevezett bizottságnak. Mindenképpen ellentmondásra jutunk és te nem fogod tudni íly módon rendbe szedni a bizottságokat."