Ugrás a tartalomhoz

A számítástudomány alapjai

Fleiner Tamás (2014)

8 A halmazelmélet alapjai

8 A halmazelmélet alapjai

A modern matematika alapjának manapság a halmazelméletet és a matematikai logikát szokás tekinteni. Mi ebben a fejezetben a halmazelméletnek egy speciális részét villantjuk fel, mégpedig a számosságok elméletét. Nincs arra mód, hogy számottevő mélységben foglalkozzunk az elméletnek akár ezzel a szeletével, de a tárgyalás talán elegendő ahhoz, hogy megértsünk valamit e a rendkívül absztrakt és mély tudományágban szokásos gondolkodásmódból.

E fejezet célja a számfogalomnak a komplex számoktól különböző irányú általánosítása: a végtelennek mint számnak a kezelése. Most nem a természetes szám, egész szám, racionális szám, komplex szám vonalon próbáljuk bővíteni a számkört, hanem azt figyeljük meg, hogy a véges halmazok bármelyikéhez egyértelműen hozzárendelhető egy természetes szám: az adott halmaz elemszáma. Más szóval, ha két halmazhoz ugyanazt rendeltük, akkor ugyanannyi elemük van. De vajon miért csak a véges halmazokhoz tudunk így elemszámot rendelni? Miért ne próbálkozhatnánk meg a végtelen halmazok elemszámának meghatározásával is? Ezt tesszük az alábbiakban.

8.1. Definíció Tegyük fel, hogy az f függvény az A halmaz elemeihez a B halmaz elemeit rendeli. Az f függvény injektív, ha különböző elemekhez különböző elemeket rendel, azaz xyf(x)f(y) teljesül tetszőleges x,yA esetén. Azt mondjuk, hogy f szürjektív (magyarul ráképezés), ha a B halmaz minden eleme előáll képként, vagyis bBaA:f(a)=b. Ha egy f függvény injektív és szürjektív, akkor f-t bijekciónak (magyarul kölcsönösen egyértelmű leképezésnek vagy egy-egyértelmű leképezésnek) mondjuk.

Ha f egy A és B közti bijekció, akkor f voltaképpen párokba rendezi A és B elemeit, így szemléletesen világos, hogy A-nak és B-nek ugyanannyi eleme van. Ha f injekció A-ból B-be, akkor B-nek nem feltétlenül áll elő minden eleme képként, tehát A-nak annyi eleme van, mint B egy részhalmazának, azaz B elemeinek száma legalább akkora, mint A-éié. Erről szól az alábbi definíció.

8.2. Definíció Azt mondjuk, hogy A számossága azonos B számosságával (jelölésben |A|=|B|), ha létezik A és B között bijekció. Ha létezik A-ból B-be injekció akkor A számossága kisebb vagy egyenlő, mint B-é, és ezt az |A||B| jelölés írja le.

8.3. Tétel (Cantor-Bernstein tétel) Ha |A||B| és |B||A|, akkor |A|=|B|.

Történelem: Cantor, Dedekind és a halmazok

Az időnként Schröder-Bernstein ill. Bernstein-Schröder néven emlegetett 8.3 Tételnek a története 1887-ben kezdődik, amikoris Richard Dedekind ezt bebizonyította magának. Akkortájt még lényegében nem létezett halmazelmélet, így szinte senkit sem érdekelt az eredmény. 1895-ben azonban a halmazelmélet másik nagy alakja, a Dedekinddel ekkor már haragban álló Georg Cantor ugyanezt sejtésként mondta ki. (Cantornak rosszul esett, hogy Dedekind visszautasította a neki szánt hallei professzori kinevezést, ezt követően a korábbi szoros együttműködésüknek vége szakadt, és nem tárgyaltak egymással.) Cantor sejtésére Ernst Schröder 1896-ban adott egy hibás bizonyítást, majd Felix Bernstein 1898-ban talált egy helyeset. A tételnek számos elnevezése forog közszájon, abban azonban mindegyik közös, hogy a "Dedekind" karaktersorozat egyikben sem fordul elő.

Cantort számos személyes tragédia sújtotta, egyiknek magyar vonatkozása is van. 1904-ben Kőnig Gyula (Kőnig Dénes édesapja) tartott előadást a nemzetközi matematikai kongresszuson, amiben Cantor transzfinit halmazelméletét igyekezett alapjaiból cáfolni. Annak ellenére, hogy nem telt el egy nap, míg Zermelo kimutatta Kőnig érvelésében a hibát, a fiát már korábban elveszített Cantor úgy érezte, hogy kollégai és lányai előtt alázták meg. Ekkortól hatalmasodott el rajta a depresszió, került számos alkalommal szanatóriumba ahol élete utolsó öt évét is töltötte. Akárcsak Bolyainak, neki sem adatott meg, hogy munkájának jelentőségét még életében annak helyén értékeljék.

Bizonyítás.Feltehetjük, hogy az A és B halmazok diszjunktak. Legyenek f:AB és g:BA injekciók, amelyek a tétel feltételei szerint léteznek. Legyen AB a G (esetleg végtelen) gráf csúcshalmaza, és aA, bB esetén legyen abE(G), ha f(a)=b vagy ha g(b)=a. Világos, hogy a G gráf bármely csúcsából legfeljebb két él indul. Az A és B halmazok közötti φ bijekciót G minden egyes komponensén belül külön-külön definiáljuk. A G gráf komponensei ötfélék lehetnek:

(1) a,b egy komponens, ha f(a)=b és g(b)=a. Legyen ekkor φ(a)=b.

(2) Komponens lehet az a1,b1,a2,b2,,an,bn kör, ahol tehát bna1 is G éle. Definiáljuk ekkor a komponensen belül a φ leképezést a φ(ai)=bi-nek. Ezáltal φ bijekció a komponensen belül.

Ezzel a véges komponenseket elintéztük. Ha G egy komponense végtelen, akkor az egy végtelen út, ami vagy mindkét irányban végtelen, vagy csak az egyikben. Három eset van tehát:

(3) G egy komponense a ,a-2,b-2,a-1,b-1,a0,b0,a1,b1,a2,b2,, mindkét irányban végtelen út. Ekkor a φ(ai):=bi bijekció a komponensen belül.

(4) Ha G egy egyirányban végtelen út komponensének végpontja A-beli, azaz a komponens a1,b1,a2,b2, alakú, és a φ(ai):=bi ismét bijekció.

(5) Az az eset marad, amikor a komponens egy B-beli csúcsból induló végtelen út, azaz b1,a1,b2,a2,. Ekkor legyen φ(ai)=bi ismét bijekciót ad a komponensen.

A fenti öt eset valamelyike G bármely komponensére ráhúzható, ezért a φ leképezést az A minden elemére definiáltuk, és az is világos, hogy B minden eleme pontosan egy A-beli elem képe lesz. Más szóval φ egy A és B közti bijekció, nekünk pedig pontosan egy ilyen függvény létezését kellett igazolnunk. [QED]

A Cantor-Bernstein tétel ereje abban rejlik, hogy két halmaz számosságának egyenlőségét nem muszáj egy konkrét bijekció sokszor fáradságos megadásával igazolni. Elegendő mindössze két injekciót mutatni a két kérdéses halmaz között.

8.4. Definíció Azt mondjuk, hogy A számossága kisebb, mint B számossága (jelölésben |A|<|B|), ha |A||B| és |A||B| (azaz ha |A|=|B| nem teljesül).

Világos, hogy ha A és B két véges halmaz, akkor vagy ugyanannyi elemük van (azaz |A|=|B|), vagy az egyiknek több eleme van, mint a másiknak, más szóval az egyik halmaznak van a másik halmazzal egyező elemszámú részhalmaza (azaz |A|<|B| vagy |B|<|A|). Nem világos azonban, hogy végtelen halmazokra is általánosítható-e ez a megfigyelés. Elképzelhető éppenséggel, hogy az A és a B "annyira végtelen" halmazok, hogy egyiket sem lehet a másikba injektálni. Nos, hogy ez csakugyan megtörténhet-e, az a halmazelmélet leginkább vitatott ú.n. kiválasztási axiómáján múlik. Ez az 1904-ben Ernst Zermelo által megfogalmazott axióma a következőt mondja ki: Ha A egy halmaz, akkor létezik egy olyan f leképezés, amelyik az A halmaz nemüres részhalmazaihoz az A elemeit rendeli úgy, hogy tetszőleges XA esetén f(X)X teljesüljön. Más szóval az A halmaz összes részhalmazából szimultán kiválasztható egy-egy elem.

Ha ezt az axiómát bevesszük a halmazelmélet szokásos axiómarendszerébe, akkor egy hihetetlenül hatékony eszközt kapunk. Ez az axióma ekvivalens az ú.n. jólrendezési tétellel. E tétel szerint minden halmaz jólrendezhető, azaz tetszőleges H halmaz elemeinek létezik olyan sorrendje, amely szerint H tetszőleges K részhalmazának van a sorban legkisebb eleme. A valós számok szokásos rendezése pl nem jólrendezés, mert a valós számok {1,12,13,14,} részhalmazának nincs első (legkisebb) eleme. A kiválasztási axiómával ekvivalens a teljes indukció végtelen általánosításának, az ú.n. transzfinit indukciónak a létjogosultsága. Érdekes számunkra a kiválasztási axiómának az a következménye is, mely szerint tetszőleges vektortérnek létezik bázisa. (Végesen generált vektortérre ez világos, nem végesen generáltakra ez korántsincs így.) A számosságok összehasonlíhatósága kapcsán pedig azt érdemes megjegyezni, hogy a kiválasztási axióma ekvivalens a számosságok trichotómiájával is, ami pontosan azt mondja ki, hogy bármely két halmaz összehasonlítható, azaz létezik injekció valamelyikükből a másikba. Ha igaz a kiválasztási axióma, akkor tehát nem történhet olyasfajta csúfság, hogy két halmaz számossága ne volna összehasonlítható.

Felmerül tehát a kérdés: a kiválasztási axióma vajon igaz vagy sem. Ha a kiválasztási axiómát feltesszük, akkor igen erős tételek igazolhatók. Egy meglepő következmény például a Banach-Tarski paradoxon, mely szerint a háromdimenziós egységgömb szétdarabolható véges sok részre úgy, hogy a keletkező részekből (pontosabban azok eltoltjaiból és elforgatottjaiból) két (értelemszerűen tömör) egységgömb rakható össze (természetesen úgy, hogy minden darabot a két új gömb közül pontosan egyhez használunk fel). (Érdekes epizód a paradoxon történetéből a Scientific American 1989-es áprilisi száma Arlo Lipof levelével, mely egy közelebbről meg nem nevezett dél-amerikai ország szupertitkos akciójáról számol be: a Banach-Tarski tétel felhasználásával aranygömböket kettőznek. A kérdés persze csak az, hogy Arlo Lipof melyik angol kifejezés anagrammája.)

A kiválasztási axióma egy másik meglepő következménye az alábbi. Egy börtön összes rabjával közlik, hogy másnap reggel mindenkinek egy pozitív egész számot írnak a homlokára. Mindazokat, akik a többiek számainak ismeretében helyesen tippelik meg a saját számukat, szabadon engedik. Ekkor a rabok megállapodhatnak egy olyan "stratégiában", amivel elérhetik, hogy bármilyen számokat is kapnak másnap reggel, véges sok kivételtől eltekintve mindegyikük helyesen tippeljen. Más szóval, ha végtelen sok rab volt bezárva, akkor 100% fogja kitatlálni a saját számát.

Mi tehát a kiválasztási axióma státusza? Ha igaz, váratlan következményei vannak, ha nem igaz, akkor nincs pl. trichotómia. Kurt Gödel és Paul Cohen munkájának nyomán derült ki, hogy a kiválasztási axióma logikailag független a halmazelmélet szokásos Zermelo-Fraenkel féle axiómarendszerétől (röviden ZF-től), azaz sem a kiválasztási axióma, sem annak tagadása nem bizonyítható az említett axiómákból. Ezért akár a kiválasztási axiómát, akár annak tagadását vesszük hozzá a ZF-hez, pusztán ettől nem kapunk ellentmondást. Ha tehát a ZF ellentmondásmentes, akkor a kiválasztási axiómával együtt is az marad. Miután nem várható, hogy a kiválasztási axiómát bárki megcáfolná (hisz ez a ZF ellentmondásosságát jelentené), azért semmi hátrányunk sem származik abból, ha igaznak tekintjük. Így számos érdekes állítás eldönthetővé válik, amelyeket remekül be lehet bizonyítani.

Pontosan ugyanarról van itt is szó, mint amit a geometriában a párhuzamossági axiómának a "többi" axiómához való viszonya kapcsán feszegettek évszázadokon keresztül. Sokan és sokáig próbálkoztak eredménytelenül a párhuzamossági axióma bizonyításával a maradék axiómák segítségével (köztük Bolyai Farkas is), majd (az atyai tiltás ellenére ezzel foglalkozó) Bolyai János és az orosz Nyikolaj Lobacsevszkij egymástól függetlenül demonstrálták, hogy a párhuzamossági axióma tagadását feltéve egy éppoly mély és érdekes geometriát kapunk, mint amilyen a megszokott euklideszi. Később aztán szigorúan matematikai eszközökkel is sikerült igazolni, hogy a párhuzamossági axióma logikailag független a többi axiómától, és akár az axiómát, akár annak a tagadását vesszük hozzá a többihez, ez nem hoz ellentmondást a rendszerbe.

8.5. Definíció Az A halmaz megszámlálható, ha |A||N|. Az N halmaz számosságát 0 (alef null) jelöli.

8.6. MegjegyzésAz (alef) a héber ABC első betűje. Követi a (bet), (gimel), (dalet), és 18 további betű. Ne nézzünk bután, hogy csak az alefet ismerjük.

8.7. ÁllításHa az A halmaz megszámlálható, akkor A véges, vagy A megszámlálhatóan végtelen halmaz, és ekkor |A|=0.

Ha egy A halmaz megszámlálható, akkor létezik belőle az N halmazba injekció, vagyis A elemeinek különböző természetes számokat tudunk megfelelteni. Ezzel egyúttal sorba is rendezzük A elemeit: A={a1,a2,}. Az is világos, hogy ha A={ai:iN}, akkor A megszámlálható halmaz. Vagyis egy halmaz pontosan akkor megszámlálható, ha elemei felsorolhatók (sorba rendezhetők) úgy, hogy a felsorolásban mindegyik elem előbb-utóbb sorra kerüljön.

8.8. Következmény A négyzetszámok halmaza vagy a prímszámok halmaza bár valódi részhalmaza a természetes számok halmazának, számosságuk mégis 0, azaz ugyanannyi van belőlük, mint a természetes számokból. Az egész számok Z halmaza tartalmazza N-t, de számossága annak sem több 0-nál, hisz az egészek felsorolhatók: 0,1,-1,2,-2,3, .

A 8.8 Következményben szereplő legutolsó állítás általánosítása következik.

8.9. ÁllításHa A és B megszámlálható halmazok, akkor AB is megszámlálható.

Bizonyítás.Tudjuk, hogy A és B elemei felsorolhatók, azaz A={a0,a1,} és B={b0,b1,}. Ekkor AB={a0,b0,a1,b1,a2,b2,}, tehát |AB|0. [QED]

8.10. KövetkezményVéges sok megszámlálható halmaz uniója is megszámlálható.

Ennél azonban több is igaz.

8.11. Tétel Megszámlálható sok megszámlálható halmaz uniója megszámlálható, azaz, ha |Ai|0 minden iN esetén, akkor |iNAi|0.

Bizonyítás. Feltehetjük, hogy Ai={a(i,0),a(i,1),a(i,2),} az elemek egy sorbarendezése. Ekkor iNAi={a(0,0),a(1,0),a(0,1),a(2,0),a(1,1),a(0,2),a(3,0),a(2,1),a(1,2),a(0,3),}, azaz először azokat az elemeket soroljuk fel, ahol az zárójelen belüli számok összege 0, majd azokat, ahol 1, majd 2, s.í.t. (Ezt gyakran úgy teszik szemléletessé, hogy az a(i,j) elemet a koordinátarendszer pozitív síknegyedének (i,j) pontja reprezentálja, és a nemnegatív rácspontokat kell sorba rendeznünk, amit számos módszerrel meg tudunk tenni, két lehetséges példát mutat az ábra.) Azt kaptuk, hogy iNAi elemei sorba rendezhetők, ezért a halmaz megszámlálható. [QED]

8.12. Következmény|Q|=0 .

Bizonyítás.Világos, hogy a Q halmaz előáll Q=i=1Qi alakban, ahol Qi:={ni:nZ} az i nevezőjű törtek halmaza. Világos, hogy |Qi|=|Z|=0, ezért uniójuk (Q) is megszámlálható. [QED]

Az órán a fenti tétel alábbi bizonyításával illusztráltuk a Cantor-Bernstein tétel alkalmazását.

Bizonyítás.[2. bizonyítás:] Mivel NQ, ezért 0=|N||Q|. Az egyenlőség bizonyításához azt kell megmutatnunk, hogy |Q||N|, azaz Q elemeihez különböző természetes számokat kell rendelnünk. Ezt az alábbiak szerint tehetjük meg. Tetszőleges rQ felírható r=pq alakban, ahol 0<qN és (p,q)=1, azaz p és q relatív prímek. Legyen ekkor

Világos, hogy minden racionális számhoz egyértelműen rendelünk természetes számot, és különböző racionálisak képe (a prímfelbontás egyértelműsége miatt) különböző lesz. [QED]

A következő célunk, hogy megszámlálhatónal nagyobb számosságú halmazt találjunk.

8.13. DefinícióA H halmaz hatványhalmazának elemei a H halmaz részhalmazai: P(H):={X:XH}.

8.14. Állítás |P(N)|=|(0,1)|, ahol (0,1) a valós számegyenes 0 és 1 végű nyílt intervallumát jelöli.

Bizonyítás. A Cantor-Bernstein tételt alkalmazzuk, azaz mindkét irányba megadunk egy-egy injekciót. Ha tehát AN akkor legyen f(A):=aA10-(a+1). Más szóval az A részhalmaznak az a szám fog megfelelni, amit úgy kapunk, hogy leírunk egy 0-t, és utána sorra 1-t vagy 0-t írunk a szerint, hogy az N soron következő eleme benne van-e az A halmazban. (Pl. ha A a prímszámok halmaza , akkor f(A)=0,00110101000101-nak adódik.) Világos, hogy különböző részhalmazokhoz különbözőképpen felírt számok tartoznak, raádásul minden f(A) pozitív és 0,2-nél nem nagyobb lesz. f tehát injekció.

Legyen most x(0,1) tetszőleges szám, melynek 2-es számrendszerbeli alakja x=0,x1x2. Legyen g(x):={nN:xn=1}. Mivel különböző számok 2-es számrendszerbeli alakja különböző, ezért a g függvény is injekció. [QED]

8.15. Megjegyzés A fenti bizonyításban a g függvény nem bijekció, ugyanis jópár olyan AN halmaz van, ami nem áll elő g(x) alakban. Konkrétan azok az A halmazok tartoznak ide, amelyekre létezik olyan N küszöb, hogy minden N-nél nagyobb szám A-ban van. Az ilyen halmaz az olyan 2-es számrendszerbeli alaknak felelne meg, amiben egy helyiértéktől kezdve csupa 1-esek állnak. Márpedig ilyen szám nincs, ahogyan 10-es számrendszerben sincs olyan szám, ami a tizedesvessző után valahonnantól csupa 9-esből áll.

Az f függvény konstrukciójakor is pontosan a fenti anomáliát igyekszünk elkerülni: 10-es számrendszerben nincs olyan szám, ami "tizedesvessző" után valahonnantól csupa 9-eseket tartalmaz. Persze ilyen számot nem is konstruáltunk.

8.16. Definíció A P(N) halmaz számosságát kontinuum számosságnak nevezzük, és (ritkábban) c-vel (gót "c"-vel) vagy (gyakrabban) 20-lal jelöljük.

8.17. Megjegyzés A 8.16 Definícióban használt jelölés összhangban van azzal, hogy egy n elemű halmaznak 2n részhalmaza van.

Létezik-e vajon nem megszámlálható halmaz? Az alábbi tétel szerint a válasz igen.

8.18. Tétel|P(N)|>|N|, avagy c>0.

Ennél azonban jóval több igaz.

8.19. Tétel (Cantor tétele)Tetszőleges H halmazra |P(H)|>|H|.

Bizonyítás.Az alábbi bizonyítás a híres Cantor-féle átlós módszer. Indirekt bizonyítunk, tegyük fel, hogy valamely H halmazra |P(H)||H|, azaz a trichotómia miatt |H||P(H)|. Mivel létezik H-ból P(H)-ba injekció (H tetszőleges h elemének a {h} részhalmazt feleltetjük meg), ezért |H||P(H)| teljesül. A Cantor-Bernstein tétel szerint ebből |H|=|P(H)| következik.

Létezik tehát egy f:HP(H) bijekció. Legyen A:={hH:hf(h)}, vagyis azon H-beli elemek halmaza, amelyeket a nekik megfelelő részhalmaz nem tartalmaz. Világos, hogy A a H halmaz egy jól meghatározott részhalmaza, és így az f bijektív volta miatt létezik egy olyan aH elem, amire A=f(a). Két eset lehetséges. Az a elem vagy A-ban van, vagy nem.

Ha aA, akkor A definíciója miatt af(a)=A, ami ellentmondás. Ha pedig aA, akkor a azért nem eleme az A halmaznak, mert af(a) nem teljesül, tehát af(a)=A, ami szintén nem lehetséges. Az ellentmondás az indirekt feltevés hamis voltát bizonyítja, ez pedig Cantor tételét igazolja. [QED]

A Cantor tételnek egy következménye, hogy nem létezik a számosságok között legnagyobb, azaz minden halmaznál van nagyobb számosságú halmaz (például a hatványhalmaza). Innen adódik, hogy nem létezhet olyan halmaz sem, aminek minden halmaz eleme, hiszen ennél a halmaznál nem volna nagyobb számosságú halmaz. Ugyanennek a ténynek egy ravaszabb megfogalmazása a Russel paradoxon. Álljon az R halmaz mindazon halmazokból, amelyek nem tartalmazzák önmagukat elemként: R:={A:AA}. Kérdés, hogy vajon R eleme-e R-nek. Ha igen, akkor RR, ha nem, akkor pedig R definíciója szerint nem teljesül, hogy RR, azaz RR. Ejnye.

Bertrand Russel a paradoxont 1901 körül vette észre (éppen a fenti Cantor tétel kapcsán), és a matematikusoknak jópár évnyi fejtörésébe került, míg sikerült tisztázni a látszólagos ellentmondást. Russel eredménye számos formában lett közismert. Ezek egyike a borbélyparadoxon: tegyük fel, hogy egy városban egyetlen borbély van, és igaz, hogy pontosan azokat a férfiakat borotválja ez a borbély, akik maguk nem borotválkoznak. Borotválkozik-e a borbély, vagy sem? (Nem az a megfejtés, ami a következő feladványé. Hazamegy a favágó, és így szól a fiához: "Te az én fiam vagy, de én nem vagyok az apád.". Na, hogy lehet ez, ha a favágó igazat mond?)

A paradoxont a halmazelmélet axiomatikus megalapozása oldotta meg. Ahogyan a világ összes halmaza nem lehet egyetlen halmaz eleme, úgy a paradoxonban definiált halmazok osztálya (azaz R) sem alkot halmazt. A halmaz a matematikában alapfogalom, nem definiáljuk, de nem igaz az az intuitív kép, hogy minden, amiről beszélni tudunk, az egyúttal halmaz is.

8.20. Tétel |(0,1)×(0,1)|=20, azaz a nyílt egységnégyzetnek kontinuum sok pontja van. Más szóval kontinuum sok kontinuum méretű halmaz uniója is (csak) kontinuum számosságú.

8.21. KövetkezményMegszámlálhatóan sok kontinuum méretű halmaz uniója kontinuum számosságú. Kontinuum és megszámlálható halmaz uniója kontinuum.

Bizonyítás.Világos, hogy |(0,1)|=|(0,1)×12|, és (0,1)×12(0,1)×(0,1), ezért |(0,1)||(0,1)×(0,1)|. A Cantor-Bernstein tétel szerint tehát elegendő egy f:(0,1)×(0,1)(0,1) injekciót adni. Legyen tehát (x,y)(0,1)×(0,1) tetszőleges. Legyenek mondjuk x=0,x1x2x3 és y=0,y1y2y3 a tízes számrendszerbeli alakok. Legyen f(x,y):=0,x1y1x2y2. Világos, hogy f(x,y) egy jól meghatározott (0,1)-beli szám (hiszen nem lehet, hogy valahonnan kezdve csupa 9-est tartalmaz). Az is világos, hogy ha f(x,y) adott, akkor abból x és y meghatározható, vagyis f injektív. Nekünk pedig éppen erre van szükségünk. [QED]

Érdemes meggondolni, hogy a fenti bizonyításban szereplő f miért is nem bijekció. (Ha ugyanis az volna, nem lett volna szükség a Cantor-Bernstein tétel alkalmazására.)

8.22. KövetkezményAz R és C egyaránt kontinuum számosságú halmazok.

Bizonyítás.R előáll megszámlálható sok (0,1) intervallummal azonos számosságú halmaz egyesítéseként. C-nek annyi pontja van, mint az R2 síknak, és R2 előáll kontinuum sok egyenes uniójaként. [QED]

Igazán szuper, hogy a kontinuum több, mint megszámlálható, de vajon van-e olyan halmaz, aminek a számossága szigorúan e két számosság közé esik? A kérdés jogos és érdekes, Cantor vette fel először. Kerestek ilyen halmazt, de senki nem talált. Próbálták hát bebizonyítani, hogy nem létezhet ilyen, ám ez sem járt sikerrel. 1900-ban Párizsban a nemzetközi matematikai kongresszuson David Hilbert, az akkori idők egyik legbefolyásosabb matematikusa tartott előadást arról, hogy mik az akkori matematika előtt álló legfontosabb problémák. Itt 10 probémát ismertetett, később a lista 23-ra bővült. Olyan problémák szerepeltek a listán, mint a mindmáig megoldatlan Riemann sejtés és Goldbach sejtés. Hilbert legelső problémája pedig éppen ez a kérdés volt. Azaz, igazoljuk az alábbiakat.

8.23. (Kontinuum hipotézis) Nem létezik olyan H halmaz, amire 0<|H|<20 teljesül.

A 8.23 kontinuum hipotézis általánosan is megfogalmazható.

8.24. (Általánosított kontinuum hipotézis) Ha X egy végtelen halmaz, akkor nem létezik olyan H halmaz, amire |X|<|H|<|P(X)| teljesül.

Igaz vagy sem a kontinuum hipotézis? Ha tudjuk, akkor miért nem tétel? Ha nem tudjuk, akkor miért nem sejtés? Nos, Kurt Gödel és Paul Cohen egy-egy eredménye együtt adja meg az egészen váratlan választ. Gödel azt igazolta, hogy a halmazelmélet szokásos axiómáiból (akár a kiválasztási axiómát is beleértve) nem lehet a kontinuum hipotézist cáfolni, így semmiképp sem várható, hogy valaki egy megszámlálható és kontinuum közötti halmazt konstruál. Cohen eredménye pedig azt mutatja, hogy a kontinuum hipotézis a szokásos axiómarendszerben nem bizonyítható. Ez azt jelenti, hogy a kontinuum hipotézis eldönthetetlen a halmazelméleten belül: akár a kontinuumhipotézist, akár annak cáfolatát (de csak az egyiket) felvesszük az axiómák közé, akkor ettől nem kerül ellentmondás a halmazelmélet axiómarendszerébe. Más szavakkal: a kontinuumhipotézis éppúgy logikailag független ZFC-től (azaz a kiválasztási axiómával kiegészített Zermelo-Fraenkel axiómarendszertől), mint ahogyan a kiválasztási axióma volt logikailag független a ZF-től vagy ahogyan a párhuzamossági axióma független a geometria maradék axiómáitól.