Cantor-tétel

halmazelméleti állítás
Ez a közzétett változat, ellenőrizve: 2023. szeptember 4.

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.

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   jelöli a H halmaz hatványhalmazát, akkor

 ,

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   esetében, így a

 

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

 

egyenlőtlenség teljesül.

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

Bizonyítása

szerkesztés

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.

Története

szerkesztés

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

szerkesztés

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.[1]

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.”

  1. Simonovits András: Válogatott fejezetek a matematika történetéből (Typotex, 2009), 134–135. oldal. ISBN 978-963-279-026-8

További információk

szerkesztés