Cantor-tétel

A Wikipédiából, a szabad enciklopédiábó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.

A tétel[szerkesztés | forrásszöveg szerkesztése]

TételCantor-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

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

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

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

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

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

egyenlőtlenség teljesül.

A bizonyítás[szerkesztés | forrásszöveg szerkesztése]

A tétel 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[szerkesztés | forrásszöveg szerkesztése]

A tételt 1891-ben, Über eine elementare Frage der Mannigfaltigkeitslehre címen megjelent cikkében bizonyította 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 | forrásszöveg szerkesztése]

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.[1] 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á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, melyek nem tagjai a saját magukról 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."

Források[szerkesztés | forrásszöveg szerkesztése]

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

Lásd még[szerkesztés | forrásszöveg szerkesztése]