Ugrás a tartalomhoz

Matematikatörténet problémákon keresztül

Balka Richárd, Egri-Nagy Attila, Juhász Tibor

Kempelen Farkas Hallgatói Információs Központ

A kontinuumhipotézis

A kontinuumhipotézis

Hilbert első problémája halmazelméleti jellegű, melyet Georg Cantor vetett fel 1877-ben. Mielőtt közölnénk a problémát, kis betekintést adunk a halmazelméletbe. Cantor talán legfontosabb felfedezése a számosság fogalma volt, mely egy halmaz nagyságát írja le. A számosságot a következő ekvivalencia-relációval definiáljuk.

8.11. Definíció. Azt mondjuk hogy az és halmazok számossága egyenlő, ha létezik kölcsönösen egyértelmű megfeleltetés, azaz bijekció. Jelölje az halmaz számosságát .

Tehát véges halmazok számossága pontosan akkor egyenlő, ha azonos az elemszámuk, így természetesnek tűnik, hogy az elemű halmaz számosságát jelölje . Hasonlóan, hozzárendelésekkel lehet értelmezni a számosságok között a relációkat is.

8.12. Definíció. Az halmaz számossága kisebb vagy egyenlő mint a halmazé, jelöléssel , ha létezik injektív leképezés. Az halmaz számossága kisebb, mint a halmazé, jelöléssel , ha de , azaz van injekció, de nincsen bijekció.

A trichotómia elve azonban egyáltalán nem világos ebből a definícióból, azaz ha és , akkor következik-e ? Ezt a következő tétel igazolja, melyet Cantor 1883-ban mondott ki, de csak később igazolta Friedrich Schröder és Felix Bernstein. A tételt mi is csak kimondjuk.

8.13. Tétel. Ha az és halmazok között létezik injekció és injekció, akkor van bijekció is.

Az eddigiek összhangban vannak a véges halmazokról alkotott elképzelésünkkel, hiszen ha az halmaz a halmaz elemű, akkor a , leképezés injekció, azonban bijekció nyilván nincs, a halmaz egy elemének nem jut pár. Így definíció szerint -hez jutunk, az összefüggés természetesnek tűnik.

Végtelen halmazokra azonban már ennyi is paradox állításokhoz vezethet. Galilei 1632-es, Párbeszédek a két legnagyobb világrendszerről című művében például Salvieti és Sagredo vitatkozik, hogy több természetes szám van-e, mint négyzetszám? Sagredo amellett érvel, hogy a természetes számok többsége nem négyzetszám, így a válasz igen. Salviati azonban megmutatja, hogy a , leképezés párba állítja a számokat a négyzeteikkel, tehát a két halmaz ugyanakkora. Cantor óta ezt úgy mondanánk, hogy a két halmaz számossága azonos.

Hasonló az úgynevezett „Hilbert szálloda” paradoxona is, mely szerint egy végtelen szálloda szobái a természetes számokkal vannak indexelve, és minden szoba foglalt. Új vendég érkezik azonban, akit el kellene szállásolni. A vendég azt javasolja, hogy a sorszámú szoba lakója költözzön az -es sorszámú szobába, az -es lakója a -esbe, és így tovább, mindenki költözzön az eggyel nagyobb sorszámú szobába. Az új vendég így beköltözhet az üressé vált sorszámú szobába, a probléma megoldódott. Mindkét esetben az a paradox, hogy egy végtelen halmaznak egy valódi részhalmaza ugyanakkora számosságú.

8.14. Definíció. Az olyan halmazokat, melyek elemeit a természetes számokkal indexelve fel tudjuk sorolni, megszámlálhatóan végtelen halmazoknak hívjuk. A számosságukat alef-nullnak nevezzük, jelölése .

Az elmélet nem lenne túl érdekes, ha nem lennének más számosságú végtelenek. E célból is természetesnek tűnik megvizsgálni az egész, racionális, illetve valós számok számosságát. Az egész számok számossága szintén , hiszen felsorolhatók a következőképpen: . Nehezebb dió a racionális számok halmaza, erről szól a következő tétel.

8.15. Tétel (Cantor, 1873). A racionális számok halmaza megszámlálhatóan végtelen.

8.2. ábra. Háromszög átdarabolása téglalappá

Bizonyítás. Elég igazolni, hogy megszámlálható, ekkor nyilván is az. Írjunk minden számot alakba, ahol és . A , leképezés injekció, azaz , így elég igazolni, hogy megszámlálható. Ehhez fel fogjuk sorolni elemeit. Először azokat a párokat soroljuk fel, melyeknél a koordináták összege , majd amelyeknél és így tovább, a felsorolás tehát Ha -t koordinátarendszerben képzeljük el, akkor voltaképpen az pontból indulva cikk-cakkban jártuk be a jobb felső síknegyedet. □

Ezek után talán meglepő Cantor következő tétele, mely szerint a valós számok halmaza nem megszámlálható! E fontos tételre két különböző bizonyítást is adunk.

8.16. Tétel (Cantor, 1873). A valós számok halmaza nem megszámlálhatóan végtelen.

Bizonyítás. Tegyük fel indirekt, hogy a valós számok halmaza megszámlálható. Ekkor a intervallumba eső számok halmaza is megszámlálható, legyen egy felsorolásuk . Adjuk meg számokat olyan végtelen tizedestört alakban, melyeknek nem végtelen sok a vége. Ez egyértelműen megtehető, például leírása . Tehát

Készítsük el a számot úgy, hogy és . Ekkor nyilván , és nem végződik végtelen sok -ra. Így az indirekt feltétel szerint fel van sorolva, azaz valamilyen -ra . Ekkor -nek a -adik számjegye , míg -nak a -adik számjegye , és . A tizedestört alakunk egyértelműsége miatt tehát , ellentmondás. □

A tételre adunk egy második, hasonlóan szellemes bizonyítást.

Bizonyítás. Tegyük fel indirekt, hogy a valós számok felsorolása. Válasszunk nemelfajuló, zárt intervallumot, melyre . Ezután válasszunk nemelfajuló, korlátos és zárt intervallumot, melyre . Általában az -edik lépésben válasszunk nemelfajuló, zárt intervallumot, melyre . Ekkor az analízisből jól ismert Cantor-féle közös pont tétel szerint az egymásba skatulyázott zárt intervallumok metszete nem üres, legyen . Mivel , így minden -ra, azaz az valós számot nem soroltuk fel, ellentmondás. □

8.17. Definíció. A valós számok halmazának számosságát Cantor után kontinuumnak nevezzük, és -vel jelöljük.

8.18. Definíció. Az halmaz hatványhalmazának nevezzük összes részhalmazának halmazát, jelölésben

Két végtelen számosságot már ismerünk, a következő tétel segítségével tetszőlegesen nagy számosságokat is konstruálhatunk.

8.19. Tétel. Minden halmazra .

Bizonyítás. Ha , akkor teljesül az állítás, tegyük fel, hogy . Az egyenlőtlenség világos, tegyük fel indirekt, hogy létezik bijekció. Elkészítjük következő részhalmazát:

Felhasználva, hogy bijekció, létezik , hogy .

Tegyük fel először, hogy . Ekkor definíciója miatt , ellentmondás.

Végül tegyük fel, hogy . Ekkor definíciója miatt , szintén ellentmondás. □

Ezek után nem nehéz belátni, hogy , lásd 4. feladat. Cantor azt sejtette, hogy nincs számosság a természetes számok és a valós számok végtelenje között, ez a kontinuumhipotézis.

Kontinuumhipotézis. Nem létezik számosság, melyre

A probléma nem várt módon oldódott meg. Kurt Gödel 1940-ben, a Gödel-féle konstruálható halmazok segítségével bebizonyította, hogy a kontinuumhipotézis nem cáfolható. Ez azt jelenti, hogy a kontinuumhipotézist hozzávéve a halmazelméleti axiómákhoz csak akkor juthatunk ellentmondásra, ha a halmazelméleti axiómáink már önmagukban is ellentmondásosak. Paul Cohen 1963-ban, a forszolás általa kifejlesztett módszerével pedig belátta, hogy nem is bizonyítható a halmazelmélet standard axiómarendszerében, tehát a kontinuumhipotézis tagadása sem okoz ellentmondást. A kérdés tehát nem válaszolható meg a hagyományos értelemben, az állítás független, azaz a halmazelméleti axiómákhoz való hozzávétele, illetve a tagadás hozzávétele sem okoz ellentmondást.

Feladatok

  1. Igazolja, hogy megszámlálható sok új vendég is elhelyezhető Hilbert szállodájában!

  2. Keressen bijekciót a intervallum és között!

  3. 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 bizottságokat és úgy döntött, elnevezi őket a galaxis lakóiról. Végére érhet-e a jegyző ennek a munkának, vagy akárhogy is igyekszik, nem tud minden bizottságnak nevet adni? (Raymond Smullyan)

  4. Bizonyítsa be, hogy !

  5. Mi a komplex számok halmazának számossága?

  6. (*) Egy valós számot algebrainak nevezünk, ha egy egész együtthatós polinom gyöke. Mi az algebrai számok halmazának számossága?

  7. (**) Mi a számossága

    a. az függvényeknek,

    b. a folytonos függvényeknek?

  8. Az és számosságok összegét a következőképpen definiálhatjuk. Vegyünk és halmazokat úgy, hogy , továbbá . Legyen . Igazolja, hogy ez az összeadás jóldefiniált, nem függ a választott és halmazoktól!