A szerkesztendő részhez

I. RÉSZ

1. Jelölések, megállapodások

Az alábbiakban használni fogjuk a következő "gyorsírásos" rövidítéseket: ∀ a "minden", ∃ a "van olyan", ⌉ a "nem", ∧ az "és", ∨ a "vagy", ⇒ a "ból következik, hogy", ⇔ az "akkor és csak akkor" szavak helyett állhat. Itt is, a továbbiakban is a magyarázatot kívánó részletek kijelölésével, majd a jobb egérgombbal magyarázat jelenik meg. Ezen kívül az egyedileg kommentált részletek pirosak. Ha valamihez nem tartozik ilyen, de szükséges lenne, kérem, kattintson ide, s a levélszövegbe helyezze el a kijelölt és magyarázatot kívánó részletet!
1. A halmaz fogalmát és az "elemének lenni" tulajdonságot nem definiáljuk, ezeket alapfogalomnak tekintjük. A halmazokat - általában - latin nagybetűkkel A, B, . . . , elemeiket latin kisbetűkkel x, y, . . . jelöljük. Ha A egy halmaz, akkor minden elképzelhető x dologra vagy az igaz, hogy x hozzátartozik az A halmazhoz, vagy az igaz, hogy x nem tartozik az A halmazhoz. Az első esetben azt mondjuk, hogy x eleme A-nak, a másodikban, hogy x nem eleme A-nak. Ezt rendre x ∈ A-val, ill. x ∉ A-val jelöljük.
Úgy képzeljük tehát, hogy egy halmaz tetszőleges dolgokból vagy más szóval elemekből állhat, pl. kutyákból, számokból, függvényekből, sőt - természetesen - halmazokból is. Célszerű megállapodni abban, hogy x ∈ y bármely két dolog között értelmezve van, és x ∈ y hamis állítás, ha y nem halmaz. London város és nem halmaz, így semmi sem eleme, s például [0, 1] ∉ London.
2. A nemnegatív egészek, a racionális számok és a valós számok halmazát rendre ω-val, Q-val és R-rel jelöljük.
3. Ha A és B két halmaz, melyeknek ugyanazok a dolgok az elemei, akkor A és B egyenlő, azaz ha ∀x-re x∈A⇔x∈B, akkor A=B.
4. Feltételezzük, hogy van olyan halmaz, melynek nincs eleme. A 3. megállapodás szerint egyetlen ilyen halmaz van. Ezt a halmazt üres halmaznak nevezzük és ∅-val jelöljük.
5. Ha x0, . . ., xn-1 elemek, akkor {x0, . . ., xn-1} jelöli azt a halmazt, melynek pontosan ezek az elemek az elemei. Például {x} az a halmaz, melynek egyetlen eleme x, {x, y} az a halmaz, melynek elemei x és y.
Megállapodunk abban, hogy egy halmazt úgy is jelölünk, hogy kapcsos zárójelben felsoroljuk az elemeit. Ha egy halmaz elemeit felsorolni ugyan nem lehet, de eléggé egyértelműen tudunk utalni rájuk, akkor is használjuk ezt a jelölésmódot. Például a nemnegatív egészek halmaza: {0, 1, . . .,n,. . . }.

1.1. DEFINÍCIÓ. Legyenek A és B halmazok. Az A halmazt a B részhalmazának nevezzük, ha ∀x∈A-ra x∈B is igaz. Azt, hogy A része B-nek, így jelöljük : A⊂B.
Ha A⊂B és ∃x∈B, amelyre x∉A, akkor A-t B valódi részének nevezzük, jelekben: A⊊B.
A 3. megállapodásból könnyű belátni a következőt:


1.1. TÉTEL. Ha A⊂B és B⊂A, akkor A=B.

A matematikában járatos olvasó számára nyilvánvaló, hogy a következő megállapodás nélkülözhetetlen.
6. Ha A halmaz és Φ(x) egy tulajdonság, mely minden x dologra igaz vagy hamis, akkor A azon elemei, amelyekre Φ(x) igaz, halmazt alkotnak, melyet {x∈A:Φ(x)} -szel jelölünk. A páros számok halmazát tehát például így jelöljük: {x∈ω:x osztható 2-vel}. Ha f   valós függvény, és Φ(x) az a tulajdonság, hogy f   az x helyen értelmezve van és ott folytonos, akkor az {x∈R:Φ(x)} halmaz az f   folytonossági pontjainak halmaza.
E megállapodásban használtuk, de nem definiáltuk a tulajdonság fogalmát. Ez az axiomatikus felépítésben - matematikai logikai segédeszközökkel - pontosan körülhatárolható. A mi nem teljesen axiomatikus felfogásunkban ez tetszőleges értelmes, a matematikában szokásos tulajdonság lehet, ahogy ezt a matematika más, nem szigorúan axiomatizált ágaiban is érteni szoktuk.
Az eddig tett néhány megállapodásunkból már bebizonyíthatjuk, hogy nem létezik az összes dolgok vagy az összes halmazok halmaza. Ez nyilvánvalóan ellentmond annak a már említett korai felfogásnak, hogy minden "elképzelhető" halmaz létezik. Erre az ellentmondásra először Bertrand Russel angol filozófus és matematikus mutatott rá 1905-ben. Ezért az irodalomban ezt az ellentmondást Russel-féle antinómiának nevezik.


1.2. TÉTEL. Nincs olyan A halmaz, melynek minden halmaz eleme.

Bizonyítás: Tegyük fel az állítással ellentétben, hogy létezik olyan A halmaz, melynek minden halmaz eleme. Definiáljuk a Φ(x) tulajdonságot így: x halmaz és x∉x. Ez kétségtelenül értelmes "matematikai" tulajdonság. Ekkor a 6. megállapodás szerint létezne a B={x∈A:Φ(x)} halmaz. B az összes olyan halmazból áll, amely nem eleme önmagának. Ha B∈B teljesülne, akkor a B halmaz Φ tulajdonságú lenne, és így B∉B állna, ami lehetetlen. Ha B∉B, akkor Φ(B) igaz lenne, és az A-ra tett feltevés szerint B∈A is igaz volna. Ekkor B definíciója szerint B∈B teljesülne. Ez ismét lehetetlen. Az indirekt feltevésből ellentmondásra jutottunk, tehát a tétel igaz.

Az 1.2. tétel mutatja, hogy általában nem beszélhetünk az összes Φ(x) tulajdonságú dolgok halmazáról. Ennek ellenére használjuk majd az {x:Φ(x)} jelölést is, ha igazolható, hogy az adott Φ-re létezik olyan A halmaz, melynek minden Φ(x) tulajdonságú dolog eleme, hiszen ekkor
{x:Φ(x)}={x∈A:Φ(x)} .
Amikor a továbbiakban nem adjuk meg ezt a „majoráns" A halmazt, akkor létezésének igazolása nem nehéz, és ezt az olvasóra bízzuk.
A következő két megállapodás egy adott A halmazhoz olyan további halmazok létezését biztosítja, melyekhez az eddigi megállapodások alapján nem tudnánk „majoráns" halmazt találni.
7. Ha A egy halmaz, akkor A összes részhalmazai is halmazt alkotnak, melyet P(A)-val jelölünk, és A hatványhalmazának nevezzük. Ha például A= {0, 1, 2}, akkor
P(A)={ø, {o}, {1}, {2}, {o, 1}, {o, 2}, {1, 2}, {o, 1, 2}}.
Nyilván P(A)= {x:x⊂A} . P(A) elemei maguk is halmazok. Azokat a halmazokat, melyeknek elemei is halmazok, gyakran halmazrendszereknek nevezik. Mi ezt a megkülönböztetést nem alkalmazzuk következetesen, mert a legtöbb halmaz, amelyet vizsgálni fogunk, halmazokból áll majd.
8. Ha A egy halmaz, akkor ∪A-val jelöljük és A uniójának nevezzük A azon elemeinek egyesítését, melyek maguk is halmazok.
Például, ha A={Duna, {0}, {1}}, akkor
∪A={0, 1}.
9. A függvény fogalma könnyen visszavezethető a halmaz fogalmára. Ehhez először a rendezett pár fogalmát kell definiálni.
1.2. DEFINICIÓ . Ha x, y két tetszőleges dolog, az {{x}, {x, y}} halmazt az x-ből és y-ból alkotott rendezett párnak nevezzük, és 〈x, y〉-nal jelöljük.
Azt, hogy 〈x, y〉 valójában megfelel a rendezett pár intuitív fogalmának, a következő tétel mutatja.

1.3. TÉTEL. Tetszőleges x, y, x', y' elemekre 〈x, y〉=〈x', y'〉 akkor és csak akkor igaz, ha x=x' és y=y'.
Bizonyítás: A feltétel nyilván elégséges. A szükségesség igazolásához tegyük fel, hogy
{{x}, {x,y}}={{x'}, {x',y'}} .
A {x} halmaz a jobb oldali halmaz valamelyik elemével egyenlő. Ebből az következik, hogy {x}={x'}, x=x' és {{x}, {x,y}}={{x}, {x,y'}}. Ebből viszont (x, y}={x, y'}, és így y=y' következik.
10. Most definiáljuk a függvény fogalmát.
1.3. DEFINÍCIÓ. Függvénynek nevezünk egy rendezett párokból álló f halmazt, ha minden x-hez legfeljebb egy olyan y van, melyre 〈x, y〉∈f. Azon x elemek halmazát, melyekre ∃y(〈x, y〉∈f), az f függvény értelmezési tartományának nevezzük és D{f}-fel jelöljük.
Ha x∈D(f), akkor azt az egyetlen y-t, melyre 〈x, y〉∈f, az f függvény x helyen felvett értékének nevezzük és f(x)-szel jelöljük.
Egy függvény tehát a D(f) értelmezési tartomány minden x eleméhez egy egyértelműen meghatározott f(x) értéket rendel.
Az {f(x):x∈D(f)} értékek halmazát az f függvény értékkészletének nevezzük, és R(f)-fel jelöljük.
Megállapodásainkból következik, hogy az f és g függvények akkor és csak akkor egyenlőek, ha D(f)=D(g) és minden x∈D(f)-re, f(x)=g(x).
Az f függvényt kölcsönösen egyértelműnek - vagy röviden egy-egy-értelműnek - nevezzük, ha x≠y esetén f(x)≠f(y).
A függvényeket leképezéseknek is nevezzük. Az f függvény az A halmazt a B halmazba képezi le, ha D(f)= A, R(f)=B. Ezt a tényt néha a következő jelsorozattal írjuk le: f:A→B.
Az f függvény az A halmazt a B halmazba képezi le, ha D(f)=A és R(f)⊂B.
Ha f egy-egy-értelmű függvény, akkor f -1 - az f inverz függvénye - az a g függvény, melyre D(g)=R(f) és ∀y∈R(f)-re f(g(y))=y.
Ha f és g olyan függvények, melyekre R(f)⊂D(g), akkor g๐f a közvetett függvény, az a függvény, melyre D(g๐f)=D(f) és (g๐f)(x)=g(f(x)) minden x∈D(f)-re.
Használni fogjuk a következő jelölést: Ha f egy függvény és A⊂D(f) egy halmaz, akkor az
{y:y∈R(f)∧∃x∈A(f(x)=y)}={f(x):x∈A}
halmazt f"A-val jelöljük. Ezt a halmazt általában f(A)-val szokták jelölni. Ez azonban félreérthető, hiszen A eleme is lehet D(f)-nek. Ezért van szükség a matematika többi ágában nem használt új jelölésre. Ha a félreértés veszélye nem áll fenn, akkor az olvasó dolgának megkönnyítésére a szokásos jelölést is használni fogjuk.
Ha f függvény és A⊂R(f), akkor
f -1(A)={x∈D(f):y∈A(f(x)=y)} . Ezt a jelölést akkor is használjuk, ha az f -1 függvény nincs értelmezve.
11. Léteznek olyan egyértelmű hozzárendelések, melyeket az előző megállapodások miatt nem tekinthetünk függvényeknek. Például minden x dologhoz hozzárendeltük {x}-et. Ez a hozzárendelés nem lehet függvény, hiszen egy függvény értelmezési tartománya halmaz. Ha ez a hozzárendelés függvény lenne, akkor értelmezési tartományának minden halmaz eleme lenne, ami az 1.2. tétel szerint lehetetlen. A halmazelmélet felépítésekor azonban ilyen hozzárendelések is előfordulnak. Ezért ezekre a hozzárendelésekre elnevezést vezetünk be. Ha minden x dologhoz valamely értelmes matematikai kifejezéssel hozzárendelünk egy F(x) dolgot, akkor ezt az F hozzárendelést operációnak nevezzük.
Az operáció fogalmát éppúgy nem definiáltuk, mint a tulajdonságét (6. pont); alkalmazására ugyanazok a megjegyzések vonatkoznak, mint a tulajdonság fogalmának használatára. Megjegyezzük, hogy az operáció fogalma a tulajdonság fogalmára visszavezethető. Egy F(x) operációt olyan kétváltozós Φ(x, y) tulajdonsággal definiálhatunk, amely minden x-hez pontosan egy y-ra teljesül, és ezt az egyetlen y értéket nevezhetjük F(x)-nek.
Megállapodunk abban, hogy ha F operáció és A halmaz, akkor az A halmaz x elemeihez rendelt F(x) értékek is halmazt alkotnak, melyet {F(x):x∈A} -val jelölünk.
Például, ha A={0, 1, 2}, akkor {{x}:x∈A}={{0}, {1}, {2}}.
Gyakran előfordul, hogy valamely operációt értelemszerűen csak bizonyos tulajdonságú elemeken értelmezünk. A 10. pontban például értelmeztük a D, R operációkat, melyek egy f függvényhez az f függvény D(f) értelmezési tartományát, illetve R(f) értékkészletét rendelik hozzá. Megállapodhatunk abban, hogy az ilyen operációk minden olyan halmazon, melyeken nem értelmeztük őket, az ∅-t vegyék fel értékként.
12. Mi is használjuk a halmazrendszerekre szokásos { A γ : γ ∈ Γ } jelölést (a pontosabb 〈 A γ : γ ∈ Γ 〉 jelölés helyett, amelyet az indokolna, hogy ez olyan A függvény, melyre D(A)=Γ és A(γ)=A γ , ha γ ∈ Γ .
innen szerkesztendő
Használni fogjuk a megszokott
γ ∈ Γ
A γ
és
γ ∈ Γ
A γ
jelöléseket:

γ ∈ Γ
A γ = { x : ∃ γ ∈ Γ ( x ∈ A γ ) }
γ ∈ Γ
A γ = { x : ∀ γ ∈ Γ ( x ∈ A γ ) }

U AY és (~ AY jelöléseket
vEr rEr
Ha A és B két halmaz, akkor A\B jelölje az {xEA : x~B} halmazt.
A halmazműveletek egyszerű tulajdonságait nem soroljuk fel, ezeket ismertnek tekintjük. A matematikában járatlan olvasó ezeket több, magyar nyelven is megjelent könyvben megtalálhatja. Használni fogjuk a (lA= n a jelölést tetszőleges A halmazrendszerre. Emlékeztetjük aEA
az olvasót, hogy A=l~ esetén (lA csak akkor van értelmezve, ha egy adott X alaphalmaz részhalmazaival dolgozunk. Ebben az esetben fl~=X.
A fejezet végére jutva felhívjuk a figyelmet arra, hogy a 6. pontban mondottak szellemében, már a 10. ponttól kezdve definiáltunk halmazokat anélkül, hogy {x:~(x)} alakú definíciókhoz megfelelő majoráras halmazt kerestünk volna. A lelkiismeretes olvasó pótolhatja ezt, ha megoldja az alábbi feladatokat.
Feladatok
Igazoljuk a következő állításokat!
1. Ha A halmaz és x, ~°EA, akkor {x}, {x, y}EP(A), (-~, y)EP[P(A)].
2. Ha A halmaz, akkor létezik az A-ból alkotott rendezett párok B halmaza.
3. Ha A halmaz és {x, y}EA, akkor x, yE UA. 4. Ha~A halmaz és ~x, y)EA, akkor x, yE U UA. 5. Ha f függvény, akkor D(f), R(f)c U Uf. 6. Ha A, B halmazok, akkor A U B= U {A, B}.
7. Ha f olyan függvény, mely az A halmazt a B halmazba képezi le,
akkor f~P(P(U{A, B})).
8. Halfüggvény, akkorf_1cP(P(U{D(f), R(f)})).
9. Ha A a 12. pontban leírt függvény, akkor U A = U R(A). YE r
19
   Az első fejezetben cgy kivétellel felsoroltuk mindazokat a megállapodásokat, amelyeket használni fogunk. A kimaradt megállapodás a kiválasztási axióma, amelyet ebben a fejezetben fogalmazunk meg. Már az eddigi megállapodásaink birtokában is leírhatjuk azonban Cantor alapötletét, amely a halmazelmélet kialakulásához vezetett. Definiálunk a halmazok között egy tulajdonságot, az ekvivalencia tulajdonságát. Ez megmondja, hogy két halmaznak mikor van „ugyanannyi" eleme. Ez az első lépés abba az irányba, hogy definiáljuk, mikor van az egyik halmaznak „több" eleme, mint a másiknak.
   2. 1. DEFnvíció. Azt a tényt, hogy az ('függvény az A halmazt kölcsönösen P'egyértelműen a B halmazra képezi le, az A~ fB jellel jelöljük, és így olvassuk : A ekvivalens azf függvény szerint B-vel. Az A és B halmazok ekvivalensek, ha van olyan f függvény, melyre A~~B. Jelölése: A~B. Ha A nem ekvivalens B-vel, akkor az A-AB jelet használjuk.
   Az egymással ekvivalens halmazokat „ugyanakkorának" tekintjük. Ennek jogosságát igazolja a következő
   2.1. TÉTEL. Az ~ tulajdonság ekvivalenciatulajdonság, azaz -kielégíti a következő három feltételt:
   !. rész
   2. Az ekvivalencia definíciója. A számosság fogalma.
   A kiválasztási axióma
   Ha A, B, C tetszőleges halmazok, akkor 1. A~A, azaz ,., reflexív;
   2. ha A~B, akkor B~A, azaz „, szimmetrikus;
   3. ha A~B és B,.,C, akkor A~C, azaz ,.J tranzitív.
   Bizonyítás:
   1. Legyen Ida az identitásfüggvény az A halmazon, vagyis az a függvény, melyre D(IdA)=A és minden xEA-ra IdA(x)=x. Ekkor A~,,,,,A.
   z•
   
   2. "Tegyük fel, hogy A~ B és f olyan függvény, melyre A~ ~ B. Ekkor f-1 olyan függvény, melyre B~t-~ A, és így B~A is teljesül.
   3. Tegyük fel, hogy A~B és B~C. Legyenek f, g olyan függvények, melyekre A~~ B és B~~ C. Ekkor A~~otC, tehát AtiC is igaz.
   Már tudjuk tehát, hogy két halmazt mikor nevezünk „ugyanakkorának". A továbbiakban arra törekszünk, hogy belássuk: létezik olyan operáciö, mely „ugyanakkora" halmazokhoz ugyanazt, „nem ugyanakkora" halmazokhoz pedig különböző dolgokat rendel. Az ile~en operációkra elnevezést is vezetünk be.
   2.2. DEtmícó. Az F operációról azt mondjuk, hogy kompatíbilis az ti tulajdonsággal, ha bármely két A, B halmazra
   b'(A)= I ~(B) ~ AN B.
   Mielőtt kitűzött célunk irányába továbbmennénk, egy kis kitérőt teszünk. Az alábbi példa mutatja, hogy két ekvivalens halmaz lehet olyan, hogy az egyik valódi részhalmaza a másiknak. Tgy egy (végtelen) halmaz ekvivalens lehet egy valódi részhalmazával.
   Példa: l.eg,~en A=au-{0}={1, 2, ...} és f' olyan függvény, melyre D(f)=or ésf~(n)=rtT l, ha nEc:o. Ekkor u~~ f A.
   A következő tétel bizonyításához szükséges a teljes indukcióval való bizonyítás ismerete. Ez a bizonyítási mód a matematika számos ágá ban használatos. A 9, fejezetben bebizonyítjuk a teljes indukcióval ;való bizonyítás jogosságát. Addig minden további nélkül használni fogjuk, ha szükséges. Itt jegyezzük meg azt is, hogy néhány későbbi bizonyít ósban fel kell használni    Most visszatérünk kitűzött célunkhoz. Először megmutatjuk, hogy a most definiálandó véges halmazokra létezik az ti reláciöval kompatiblis operáció.
   2.3. Dv,vmíc!ó. Tetszőleges nco~ elemre jelöljüi< rt-tal a {0, i, .. , rz-1} halmazt (n=0 esetén 0=fh). Az A halmazt véges halmaznak nevezzük, ha létezik olyan nEc~, melyre Atin. Az A halmazt végtelért halrnaznak ,levezzük, ha nem véges. 2~
   2.2. Tr`rEr,. Ha a és m az o> különböző elemei, akkor a ~-m.
   Az állítás az ~z és m maximuma szerinti teljes indukcióval könnyen bizonyítható. Ennek elvégzését az olvasóra bízzuk.
   A 2.2. tételből következik, hagy véges halmaz nem lehet ekvivalens egy• valödi részhalmazával. Ha A véges halmaz, A elemeine~. száma a véges halmazokon értelmezett olyan operáció, amely a 2.2. tétel szerint a vég es halmazokon kompatibilis az v re?ációval. Ezt szeretnénk végtelen halmazokr« i:; v tala;nositani.
   Yla létezne olyan A halmaz, amely az ö•.szes halmazból áll, akkor ezt könnyen elvégezhetnénk. Az algebrából ismeretes, "c'gy az ti eke-i~e-aienciareláció A-t cüszjankt ekvivalenciao.sztályokra bontaná, iev minden halmazhoz hozzárendelhetnénk az dt tartalmazó ekvivalenci_iosztáiyt. 'l-ermészetesen az 1.2. tétel nai:at? ez r,em járható út.
   t4, további állitások mc~7fogalmaaásához már szükségünk lesz a kiválasztási axiómára. Ez az axióma az, amely a halmazelmélet felépítése soré: ~.~ matematiki,sok körében a legtöbb vitát váltotta ki. A matematika legtöbb ágazóan elfogadják és alkalmazzák a kiválasztási axiómát, illetve következtetényeit. Nem mindig közlik vagy ismerik fel azonban, ha alkalmazására sor kerül. Mint említettük, a halmazelmélet részben felépíthető a kiválasztási axióma nélkül is, de ez számos felesleges nehézséget okoz. Így mi ezzel nem foglalkozunk, hanem elfogadjuk és alkal7nazzuk a kiválasztási axiómát. A bevezető fejezetekben (a lű. fejezetig) azonban minden esetben fel fogjuk hívni a figyelmet rá, ha alkalmazására sor kerül.
   2.4. LFrt~fcró. Az f függvényt az {,qY: yE r} halmazrendszerhez tartozó kiválasztási függvénynek nevezzük, ha L~(f)=I' és I' minden y elemére f (Y) E A,..
   Természetesen ahhoz, hogy létezzék ilyen kiválasztási függvény, szükséges, hogy. ,az AY halmazok ne legyenek üresek. A kiválasztási axióma azt posztulálja, hogy ez a feltevés elegendő is.
   KtvALASZTdst nxré~an. Nemüres halmazok bármely {Ay: yEI'} rendszeréhez létezik kiválasztási függvény.
   Megjegyezzük, hogy véges I' indexhalmazra a kiválasztási axióma előző megállapodásainkból könnyen bizonyítható. Végtelen I' indexhalmazra a feltevés nem bizonyítható a halmazelmélet többi szokásos Í axiómájából.
   2.3. 1'r~TFt,. Létezik olyan operáció, mely kompatibilis az ~ Culajdonsággal.
   A tétel Neumann Jánostól származó bizonyítása a kiválasztási axiómát felhasználva, a rendezett és jólrendezett halmazok elméletén alapul. Ezért a bizonyítást későbbre halasztjuk. (Lásd a i0.1. tételt.) A kiválasztási axióma feltételezése nélkül az eddigi megállapodásokból ilyen operáció létezése nem bizonyítható; ha a kiválasztási axiómát nem tennénk fel, akkor ~i számossági most definiálandó fogalmát új alapfogalomnak kellene Cekinteni és az ekvivalenciával való kompatibilitását axiómak érat kellene elfogadni.
   2.5. Dc~mícró. A továbbiakban IAI-val jelölünk és A számosságának nevezünk egy - a 2.3. tétel szerint - létező, az ti tulajdonsággal kompatibilis operációt.
   A 2.2. tétel szerint feltételezhetjük, hogy ha A véges halmaz, akkor A~=n arra az nFw elemre, melyre n~~A. (Valóban, ha LvL egy, az ~•-val kompatibilis operáció, akkor könnyen alkothatunk olyan F~ operációt, mely egyáltalán nem vesz fel co-beli értékeket. Például ilyen az Hz{A1=(Fr{A), o,j
   operáció. fűzek után, ha F'-et úgy definiáljuk, hogy ('(A)-FZ(A), ha A nem véges,
   és
   F(A)= rr , ha A véges és A-~~ n ,
   akkor az így kapott operáció a 2.2. tétel miatt kompatibilis lesz az ~tulajdonsággal, és ~A~E~u, ha A véges.) Az ~A operáció értékeit nevezzük számosságoknak. A nemnegatív egészeket véges szárrrosságokrrak, a végtelen halmazok számosságait végtelen s~ámo.sságoknak nevezzük.
   A végtelen számosságokat a természetes számok általánosítósainak tekinthetiüi~:. .~ következő négy fejezetben megmutatjuk, hog-y nagyon sok végtelen számosság van, továbbá hogy a nemnegatív egész számokon értelmezett összeadás, szorzás, hatványozás és nagyság szerinti rendezés kiterjeszthető a számosságokra úgy, hogy e műveletek és a nagyság szerinti rtindezés számos tul:~jdonsága továbbra is érvényes maradjc•n.
   . rész
   3. Megszámlálható számosság, kontínuum számosság
   A nercnegatív egész számok a~ halmaza a 2.2. tétel szerint végtelen halmaz, nem ekvivalens a-tal egyetlen nE_cu-ra sem.
   3.1. DEFINÍCIÓ. Az cu-val egyenlő számoságú halmazokat megszámlálhatóan végtelen halmazoknak nevezzük.
   a~ számosságát itő val jelöljük. Ezt a jelölést még G. Cantor vezette be. (Az tZ (alef) betű a héber ábécé első betűje.)
   Az A halmazt megszámlálható halmaznak nevezzük, ha véges vagy megszámlálhatóan végtelen.
   Ebben a fejezetben bebizonyítjuk a megszámlálható halmazokra vonatkozó jól ismert elemi tételeket. Először a kiválasztási axiómát nem igénylő bizonyításokat ismertetjük.
   3.1. TÉTEL. ~o végtelen számosság. Bizont~ílás: cu végtelen halmaz.
   3.e. i'í:°rEi. Megszámlálható halmag minden részhalmaza is megszámlálhatcí.
   Bizonyítás: Az ~ tulajdonság tranzitivitása miatt elegendő bizonyítani, ho~~y ua minden részhalmaza megszámlálható. Legyen ACCO. Ha A véges, akkor nincs mit bizonyítani. Feltehető, hogy A végtelen. Definiáljunk egy A-n értelmezett f függvényt az
   f (n)= ~ A (1 n;
   megkötéssel, tetszőleges nEA-ra: Szavakban: f(n) az A halmaz a-néi
   kisebb elemeinek száma. Miután véges halmaz minden részhalmaza véges,
   f(n)E~p, ha nEA. Ha m    és így f(m)    3.1. KövErxEZVtÉtvv. Az A halmaz akkor és csak akkor megszámlálható, ha vagy A=~, vagy létezik olyan f függvény, mely c~-t A-ra képezi le. Ez utóbbi állítás éppen azt fejezi ki, hogy A= {cT„ : n E ~} sorozat alakban írható.
   Bizonyitás: Az állítás „csak akkor" része nyilvánvaló. Tegyük fel, hogy f az ~-t A-ra képezi le. Definiáljunk az A halmazon egy olyan g függvényt, amelyre
   Ekkor g az A halmazt egy-egyértelműen ~ egy részhalmazára képezi le. A tehát, az előző tétel szerint, megszámlálható.
   A következőkben néhány, az w-nál látszólag „nagyobb" halmazrót is bebizonyítjuk, hogy megszámlálható.
   3.3. T~TEC. Legyen B={(n, m): n, mEw~, azaz a nemnegatív egészekből alkotott rendezett párok halmaza. B megszámlálhatóan végtelen halmaz. A tételre két bizonyítást adunk.
   l: Bizonyitás: Definiáljuk az f függvényt a következőképpen: Ha (n, m)EB, akkor
   Az egyértelmű prímfelbontási tétet szerint f egy-egyértelmű, és B-t ca-ba képezi le. B tehát a 3.2. tétel szerint megszámlálható. Megjegyezzük, hogy az egyértelmű prímfelbontási tétel teljes indukcióval könnyen bizonyítható, és így az aggályos olvasó éppoly elfogadhatónak kell, hogy tekintse az 1. bizonyítást, mint a következőt.
   2. Bizonyítás: Az alábbi elrendezés szemlélteti a B halmaz elemeit (o, o), (o, 1), ~o, 2), . . ., (o, n), . . .
   (1, 0), (1, 1), (1, 2), .. ., (1, n), ... (n, > (n, ), (n, 2), . . ., (n,~, . . .
   A B halmazt a következőképpen rendezhetjük sorozatba: ao=(0, Oi a sorozat első eleme. al=(o, 1), a.,=(1, 0) a sorozat következő két eleme. n+ 1'
   Ha már megadtuk az a„ sorozat első ~ 2 ~ elemét, akkor a követ:cező n~-1 lépésben felsoroljuk az (n-i-1)-ellik mellékátló elemeit az áUrán nyíllal jelzett irányba haladva. Ebben az átlóban azok a (k, 1) párok állnak, melyekre k-f-1=n+1, sorrendjüket a felsorolásban az határozza meg, hogy melyiknek kisebb az első eleme.
   A következő tétel bizonyításában már fel kell használni a kiválasztási axiómát.
   3.4. TÉTEL. Megszámlálható sok megszámlálható halmaz egyesítése is megszámlálható, azaz ha {A„:nEco} olyan halmazsorozat, melyre A,~ minden nEco esetén megszámlálható, akkor U A„ is megszámlálható nEm
   halmaz.
   Bizonyítás: Feltehető, hogy A„~~, ha nEw, hiszen az A„ halmazok növelésével egyesítésük is növekszik. Tetszőleges n E ~ elemre legyen
   Bn={ f; ffügg~ény nD(f)=~nR(f)=An}~
   Feltevésünk szerint a {B„ : n E cu) halmazrendszer nemüres halmazokból áll. Ezért a kiválasztási axióma szerint tartozik hozzá egy f kiválasztási függvény. Az f függvény a helyen felvett értékét jelöljük fn-nel. Ekkor i5 An= {fn(k) ~ kE co}
   minden i1E~-ra. Legyen g olyan függvény, melynek értelmezési tartománya az cu-ból alkotott rendezett párok halmaza, és
   g((n, k )=1n(k), ha n, kEu~.
   Ekkor
   Így a 3.2. és 3.3. tételek szerint U A„ is megszámlálható.
   Már emutettük, hogy nemüres halmazok bármely véges rendszeréhez a kiválasztási axióma feltételezése nélkül is található kiválasztási függvény. A 3.4. tétel bizonyítása e megjegyzés alapján mutatja: az, hogy véges sok megszámlálható halmaz egyesítési halmaza megszámlálható, a kiválasztási axióma felhasználása nélkül is bizonyítható.
   3.5. "ffTet. A racionális számok halmaza megszámlálható. Bizonyítás: Legyen Q+ és Q__ a pozitív, illetve a negatív racionális számok halmaza. Ekkor
   Minden rE Q+ egyértelműen írható fel q egyszerűsített tört alakban, ahol p, qEu~. Ezért Q+ a 3.2. és 3.3. tételek szerint megszámlálható. Hasonlóan, Q' is megszámlálható, és igy -- a 3.4. tétel szerint - Q is megszámlál ható.
   3.ó. Tt ~ t ~. Ha A végtelen h~ilmaz, akkor van ~o számoságú részhalmaza.
   Bizonyítás: Legyen f olyan függvény. mely tetszőleges .k'EP(A), X' ~ halmazhoz annak egy f~( ~';) elemét rendeli. Ilyen .f l üg~wény aa kiválasztási axióma szerint létezik.
   Definiálunk egy, az c~rn értelmezett g függvényt ú:;y, hogy 8(n)E K(g) értékeit nEo~ szerinti rekurzióval adjuk meg. Legyen g(Ú)=J.(A). Ez értelmes, hiszen A nem üres, mert nem véges. Tegyük fel, hogy ir~0, továbbá 8(i)-t már definiáltuk tnínden ion értékre. A {g(o), ..., g(n-I)} nemüres, véges halmaz, így
   nem üres, különben A véges (enne. Legyen Sin)-1(A ,iS(t>), ..., g(n-1)})~ Ezzel g(n~et minden nEa~-ra értehueztük. Ha i    Ezért g egy-egyértelmű függvény. Legyen A'= R(g). g definíciója szerint A'e A és co ~ ~ A', tehát
   Eddig csak véges és megszámlálhatóan végtelen halmazokról szóló eredményeket láttunk. A következő tétel az első, amely egy nem megszámlálható halmaz létezését biztosítja. Ennek bizonyítása során fedezte fel Cantor a halmazelmélet legalapvetőbb ötletét, az „átlós módszert". 3.7. TÉ-reL. R nem megszámlálható.
   Bizonyítás: Elegendő igazolni, hogy tetszőleges nemüres, megszániláiható A c R halmazhoz található egy yE R`,A valós szám. A megszámlálható halmaz, ezért
   A=(a„ : nEa~} alakban írható.
   Az a„ valós számnak létezik olyan egyértelmű tizedeltört-előállítása, melyben nem áll bizonyos helytől kezdve csupa kilences jegy. Jelölje a„,x az ca„ szám k-adik tizedesjegyét a fenti tizedeltört-előállításban. Definiáljuk az,ty sorozatot így:
   y.„=U, ha a„,,,, ~ U, és ~'„= 1, ha u~, „=0.
   Ekkor t), 3'0, . . ., t'„, . . ., egy ), valós szám olyan tizedeltört-előállítása, melyben nem áll bizonyos helytől kezdve csupa kilences számjegy. Ekkor tetszőleges nE ~»-ra az v és az a„ szám a-edik tizedesjegye különböző, és így a tizedeltört-előállítás egyértelműsége miatt hr a„. Ezért y~<4.
   R számosságát c-vel jelöljük, és kontinuum szúmossúgnak nevezzük.
   3.8. TfTFL. Ha (a, b)cR tetszőleges, nemüres nyílt intervallum, akkor
   Bizonyítás: Ha f tetszőleges, szigorúan monoton folytonos függvény (a, b)-n, akkor az elemi analízisből ismert Bolzano-tétel szerint f az (a, b)-t kölcsönösen egyértelműen képezi le arra az (a., (3) nyílt szakaszra, melyre
   a= lim f (x), ~= lim f (.x).
   x--a-() x-~6-0
   Ezért
   ahol f alkalmas lineáris függvény, .Í(x)=b~ax-2~bL~. .z ~ 1
   Tudjuk azt ij, hogy ~ - 2 , 2 ~ ~~ tclZ, ahol tg a tangens függvényt jelöli. a
   Az eddig bizonyftott tételek szerint nEc~> sZo és ~ különböző számosságok. Most érdekes lehetne különböző egyszerű halmazok számosságát kiszámítani. Mi ezt később tesszük meg - általános tételek birtokában - a 6. fejezetben. Már láttuk, hogy legalább két különböző végtelen számosság van. Most megvalósítjuk programunkat, a számosságokra kiterjesztjük a roveleteket és a nagyság szerinti rendezést.
   rész
   4. Számosságok összehasonlítása A nagyság szerinti rendezés kiterjesztését a számokról a számosságok
   ra avval kezdjük, hogy először megmondjuk: mikor kisebb vagy egyenlő egy számosság egy másiknál.
   4.1. DEFt:víctó. Legyenek: a, b tetszőleges számosságok. Azt modjuk, hogy az a számosság kisebb vagy egyenlő, mint a b számosság, ha találhatók olyan A és B halmazok, melyekre (A~=a, jB~=b, és található A-nak egy-egyértelmű f leképzése B egy részhalmazára. Ezt a tényt a következőképpen jelöljük: a-b.
   A definíció helyességéhez meg kell mutatnunk, hogy a - tulajdonság nem függ az A és B halmazok választásától.
   4.1. "I'ÉTLL. Legyenek a és b tetszőleges számosságok és A, A', B, B' olyan halmazok, melyekre ~ A ~ _ ~ A' i = a, ~ B j = B' Í = b. Ha létezik olyan egy-egyértelmű f függvény, melyre D(f)=A és R(f)cB, akkor létezik olyan egy-egyértelmű g függvény is, melyre D(g)=A' és R(g)~B'.
   Bizonyítás: Mivel jAj=~A'i és ~B~=~B'~, így léteznek olyan h, k leképezések, melyekre A'-„h A és B~k B'.
   Legyen g=k o ( f o h). Ekkor D(g)= A', R(g)~ B'. A g függvény-az f, h, k függvények egy-egyértelműsége miatt - egy-egyértelmű.
   Könnyű igazolni a következőt:
   4.1. Kövr~rxEZMÉNY. Tetszőleges a, b számosságokra asb akkor és csak akkor teljesül, ha léteznek olyan A=B halmazok, melyekre ~A~=a és ~Bj=b.
   29
   E megjegyzés alapján már tudjuk, hogy m= n, ha »r, nEa> és m a számok rendezésében nem nagyobb, mint n, továbbá, hogy rrWtZo, ha n<_m és ti„-c. Valóban, az rncrr. a=cf~, c~~R tények rendre adják az állításokat.
   4.2. l >    Bizorryírcís:~A reflexivitás nyilvánvaló, hiszen tetszőleges A halmazra Ac A. A tranzitivitás igazolásához te~__>yük fel, hogy a, b, c olyan számosságok,'"melyekre
   a-- b é.s b- c.
   Válasszunk olyan A, B. C halmazokat és,/; g egy-egyértelmű függvényeket, melyekre
   yA~=a, ;BI=-b, jCj=c,
   D(~ = A, R(~ )c_ B, D(g)= B és R(g)c C.
   Ekkor a ir=,~ v 1 függvény az A halmazt egy-egyértelműen C-be képezi. Felidézünk egy algebrai segédtételt. Erre a segédtételre azért van szükségünk, mert feltételt ad arra, hogy egy „= jellegű" tulajdonságból mikor lehet egy „~ jellegŰ" tulajdonságot kapni.
   SEGFll ~ er~L. Legyen - reflexív, tranzitív és antiszimmetrikus tulajdonság. Ez utóbbi azt jelenti, hogy x-y és y-.Y-ből .z=y következik. nefiniáljuk az my tulajdonságot az .Y-y és x>1y kikötésekkel. Ekkot a < tulajdonság`irreflexív és tranzitív.
   Bizorryítá.s: ~ C ~-~ r), hiszen .v= ~.
   A tranzitivitás bizonyításához tegyük fél, hogy az x, y, z elemekre .Y    Ebből a - tulajdonság tranzitivitása miatt .Y=z következik. Ha z=.Y, akkor y--.- miatt
   )' :=- .Y
   is áll. Ezt x-y-nal összevetve, az antiszimmetriából .x=y következik. ami ellentmond az .my feltevésnek. Ezért x~z, és így x~ ~.
   A segédtétel szerint tehát a következő tételre van szükségünk 4.3. BExivsrEt'v Exvivnt_FVCmTiTSt_E. A számosságokon definiált tulajdonság antiszimmetrikus.
   Ehhez a -= definíciója szerint a következő, halmazokra vonatkozó állítást kell bebizonyítanunk
   Ha A, 13 olyan halmazok és .f g olyan egy-egyértelmű függvények. melyek re
   D(f)=A, R(_f )`B, D(g)=B és R(g)cA,
   akkor
   A~B,
   azaz található olyan h függvény, melyre A~,, B.
   Mielőtt megfogalmaznánk egy valamivel általánosabb tételt - melynek a fenti állítás következménye - egy függvényekkel kapcsolatos jelölést vezetünk be.
   4.2. DEFrNfctó. Ha f egy függvény és A halmaz,.f~A-val jelöljük és f függvény A-re. való megszorításának nevezzük azt a függvényt, melynek értelmezési tartománya D( f ) (1 A, és D( f ) n A bármely .v- elemére (f I A) (~)=f.(.x).
   Hasonló jelölést alkalmazunk akkor is, ha F operáció, megjegyezve, hogy megállapodásaink szerint FIA már függvény.
   A 4.3. tétel helyett a következti tételt bizonyítjuk.
   4.4. TÉTEL. Tegyük fel, hogy A, B, f és g kielégíti a 4.3. tételben tett feltevéseket. Ekkor találhatók olyan A', B', A", B" halmazok, melyekre
   A=A'UA", A'oA"=~, B=B'uB", B'nB"=~1 és amelyekre
   A~,.,flA'B~, B~~~xls„A~~.
   Ennek következményeképpen A~B. Valóban, A-nak egy kölcsönösen egyértelmű h leképezését B-re így definiálhatjuk:
   h(x}=~f(x)' ha xEA'~
   Bizonyítcfs: A matematikában járatos olvasó számára a következő tények jól ismertek: Ha f tetszőleges függvény és {Ay: yEl'} olyan halmazrendszer, melyre A,;c D( f ) minden y E r esetén, akkor (1}f"UA=Uf"A
   vEr y ~Er v.
   Továbbá, ha f egy-egyértelmű is, akkor (2) f " n Ay= (~ f"Ay is teljesül.
   -Er vEr
   (1) és (2) állítások bizonyítása egyszerű, ezért az olvasóra bízzuk. Ha az A', B', A", B" halmazok kielégítik a tétel követelményeit, akkor fennállnak a következő összefüggések:
   B' = f "A'
   Az utolsó összefüggés indokolja, hogy tekintsük a h(X)= A\g"(B\.f"X ) leképezést - mely A tetszőleges X részhalmazának egy h(X}cA halmazt feleltet meg -, és keressük a h leképezésnek egy „fixpontját", azaz olyan XcA részhalmazt, melyre h(X)=X.
   Ezt „iterálással" keressük. Rekurzióval definiáljuk az Anc A halmazokat
   Legyen A'= a An, és B'=.f "A'. Ekkor (2) szerint nEm
   B'= a J r'An . nEc~
   Legyen B"=B\B'. A de Morfian-azonosság szerint nEm
   Legyen A"=g''B". Ekkor (1) alapján ~4"= nU g"(B\J'r/Art)'
   Ismét a de Nlorgan-azonosság szerint FigyelenWe véve, hogy Aa=A,
   n A„+t= a An=A'. ~w nE~u
   AZt kaptür;, h0°V
   Miután B'=,f"A' és A"=-g"B", az íQy konstruált halmazok kielégítik a tétel követelményeit.
   4.3. DEFiNÍC1ó. Azt mondjuk, hogy az a számosság kisebb, mint a b .számosság, és ezt a    Az alábbi következmények mutatják, hogy definíciónk célszerű, és a < tulajdonság a számok rendezésének általánosítása.
   4.2. KÖVErKEZhtÉNY. Tetszőleges a, b számosságokra a~ b akkor és csak akkor igaz, ha bármely A, B halmazpórra, melyre ~A~=a, ~B~=b, található olyan B'`B, melyre A~B', de A-AB.
   Bizonyítás: A feltétel első fele a~b definíciójával ekvivalens, második fele pedig az a=b állítással.
   4.3. 1CövErx~zvaÉxY. A < tulajdonság irreflexív és tranzitív a számosságokon.
   Bizonyítás: A ~ tulajdonság a 4.2. tétel szerint reflexív és tranzitív, a 4.3. ekvivalenciatétel szerint pedig antiszimmetrikus. Így az állítás a segédtételből következik.
   4.4. KöverxEZV~É~Y. A számosságokon értelmezett < tulajdonság 33 a számok nagyság szerinti rendezésének kiterjesztése.
   3
   Bizonyítás: Figyelembe véve a 2.2. tételt, könnyen látható, hogy mindkét rendezésben, tetszőleges n, mEr~-ra az „n kisebb m" állítás azzal ekvivalens, hogy nem.
   Az eddig megismert számosságokra 0    4.5. TÉTEL. tZo a legkisebb végtelen számosság.
   Bizonyítás: Legyen a végtelen számosság és A olyan halmaz, melyre ~A~ -a. A 3.6. tétel szerint o~ ekvivalens A egy részhalmazával, és így Megemlítjük, hogy a 3.6. tétel bizonyításában kihasználtuk a kiválasztási axiómát, és sem a 3.6. tétel, sem a 4.5. tétel nem bizonyítható a kiválasztási axióma feltételezése nélkül.
   A következő, G. Cantortól származó tétel biztosítja, hogy végtelen sok végtelen számosság van, sőt azt is, hogy bármely számossághoz található nála nagyobb számosság.
   4.6. "TÉTEL (Cantof~ tétele). Bármely A halmazra ~ A; < ~P(A)~. Bizonyítás: ~ A ~ - I P(A) I , mert az {x} ~ A függvény ,A-t e.~y-egyértelműen P(A)-ba képezi le. Ezért elegendő bebizonyítani, hogy A~.P(A). Indirekt módon bizonyítunk. Tegyük fel az állítással ellentétben, hogy létezik olyan f függvény, melyre A~ fP(A).
   Legyen B={aEA: a~ f(a)}. Ekkor BCA, és így BEP(A). Létezik tehát olyan bEA, melyre f(b)=B. Ekkor B definíciója szerint tetszőleges aE A-ra
   aE flb)~aff.f(a)~ a74
   Mivel h E A, így a helyébe b-t helyettesítve, a bF f'(b)bbs f(b)
   állítást kapjuk. Ez ellentmondás. Az indirekt feltevés hamis, így A ~ P(A). A tétel következménye például, hogy
   ahol Pn(cu) halmazokat rt szerinti rekurzióval definiáljuk:
   Ebben at fejezetben megemlítünk még egy tételt. Megjegyezzük, hogy ez a tétel sea~ bizonyítható be a kiválasztási axióma felhasználása nélkül.
   4.7. T~rEt. Ha az f függvény az A halmazt a B halmazra képezi le, akkor ~,B~=~A~.
   BizorTrítás: Tetszőleges yEB-re legyen Ay={xEA:.f'(x)=y}. A feltevés szerint az {Ay: yE B} halmazrendszer nemüres halmazokból áll. A kiválasztási axióma szerint létezik egy g kiválasztási függvény: g(y)EAy tetszőleges yEB-re. Nyilvánvaló, hogy g a B halmazt egy-egyértelműen képezi le az A egy részhalmazára.
i. rész
   5, Műveletek haimazokkai és számiosságokkai
   IZá~tér aa~ a számokon értelmezett műveletek számosságokra való hiterjesztésére. Elvhez szükséQünn lesz néháov. a halmazműveletekre vonatkozó eredményre.
   ~.1. ®r~mícró. Legyen {AY:;~;1'} egy halu~azrendszer. A halmazren.lszer cfdreri~t s_orzatár3ak vagy Descartes-s_r~azatánaknevezzük és )( Ay val jeltiljü'~l: :~z
   { f': f függvény és D(Í)=~ és , T=r(.f{Y)=A,,)} halmazt. azaz a halmazrendszerhez tartozó összes kiválasztási függvén~ek halmazát.
   l~elinlciónk jogos, hiszen a X A~ halinaz elemei a ;:r
   P~P(P(I'~~ ~-? A~))~ ,,E t halmazból ~,-alók.
   Speciális esetként a fenti definíció két haUnaz direkt szorzatát is adja. Ha A~ . .ar két halmaz, akkor AoX A1= X A; . Ez izomorf, de nem azonos.
   i E.-'_
   az Afl ból és A~ ből nett rendezett párok halmazával. Értelmezésünk szerint AoXA1=A,?~A~. Továbbiakban, lia ez nem vezet félreértésre, akkor a rendezett párokból álló halmazra is c.z Ar,XA-jelölést használjuk.
   A szá;rosságműveletek tulajdonságainak igazolásakor nagyon hasznos lesz a k~wetkező ..asszociatív" törvény.
   5.1. TfTEL. Legyen f AY : }~ ~i} halmazrendszer. Teg~.üan. fel, ho-~y P=UI'ó.
   őE G
   ahol a í''h halmazok páronként közös pont nélkiiliek. azaz diszjunktak. 36
   Ekkor
   x~~-~ x % .~.,~.
   .,EF b,~ . ,~rh
   Bizonyítás: Jelöljük a bal oldalt T-~-e1, a jobb oldalt S-sel. ~ea~niáljuk T egy ~ leképezését ígv
   és legyen
   Könnyű ellenőrizni, hogy Tti~S.
   A ~ leképzést a T és S halmazok közötti „kanonikus" meg VeleCtetésnek nevezik.
   Ha a félreértés veszélye nélkül megtehetjük, akkor az 5.1. tétemben szereplő két izomorf halmazt .;azonosítani" fogjuk.
   5.2. 1W~r_sieió. Legyen A, B két halmaz. i~efiniáijuk az A r~ B-~:ufkera halmazt (vagy A ad B halmazt), így:
   Ezt a halmazt B,1-val jelöljük. Furcsa jelölésünknek az az oka. hogy a későbbiekben mea kell különböztetnünk a halmazok most bevezetett hatványozását a később bevezetendő számossághatt ányozástól. A dei?nícióból azonnal következik. hogy BA= )( Ab, ahol Ao=,~ minden bEB
   b c B-re.
   5.3: 1~EFt~íctó. Egy halmazművelet kompatibilis az ekrizc'rier~ti~ncrlajdonságga~'. ha argumentumait ekvivalens halmazokkal pótolva a:~i~ etet eredménye ekvivalens marat az eredeti eredménnyel.
   5.2. TFrEL. A direkt szorzás, a hatványozás és a disz;t~nkt ttriió ~ompatibilis az ekvivalenciatui:tjdonsággal.
   Bizormito.s-: Lewenek
   3~ ..~ , =r? ~ ,í , .r~
   olyan halmazrendszerek, melyekre AY^-A;, minden yF_P-ra. Alkalmazva a kiválasztási axiómát, minden yEl' elemre választhatunk olyan ~r függvényt, melyre
   Ay,., v^ Av .
   Most belátjuk a direkt szorzatra vonatkozó állítást. Legyen A= X ~„ ~ A'= X AÍ .
   YéT :'E I'
   Definiáljuk A egy ~ leképezését A'-re: .fE A-ra cÁ(.f) az A'-nek az az f' eleme, melyre
   teljesül minden yE 1'-ra. Legyen fi , f=,E A, f~ ~ f L és f; _~( f ), f ; _~( f ). Ekkor van olyan yEI', melyre ~i(y)~f2(y). Mivel `~,v egy-egyértelmű. ezért f`i{y)~f:.(Y), és így .f~~f,~. ~ tehát egy-egyértelmű. De R(fi)= =A' is teljesül, mert ha Í"E A' és,faz A-nak az az eleme, melyre 'dyEj' elemre
   f(~')=m;n{f~(Y)), akkor ~(f)=f~~
   (gy.
   A~,,A'.
   A diszjunkt unitra vonatkozó állítás bizonyításához tegyük fel, hogy az AY, ill. A, halmazok páronként diszjunktak. Jelölje A és A' rendre az U Ay, U A., halmazokat. Ekkor egy, az A^~„,A' teltételnek eleget tevő l,El, iEr
   leképezést a következőképpen definiálhatunk: Ha xEA, akkor legyen ~(x)=cr~,(x) arra az egyetlen y-ra, melyre _rEA.,. cÁ tulajdonságainak ellenőrzését az olvasóra bízzuk.
   Végül tegyük fel, hogy A, A', B, B' olyan halmazok és 4~, ~~ olyan függvények, melyekre
   A^,QA', Bti~,B'.
   Definiáljuk a uA halmaz egye leképezését így: fEEA-ra legyen Könnyű igazolni, hogy
   c~A ~, ~,c~,A,.
   Megjegyezzük, hogy véges sok argumentumú művelet esetén az 5.2. tétel bizonyításához nem kell a kiválasztási axióma.
   5.4. DeFrvíció. Legyen {ay.: yET} számosságok egy rendszere.
   I. Válasszunk olyan {Ay,:yEl'} halmazokat, hogy minden yFP-ra ~ AY~ =a},. A X A,r halmaz számosságát ~ aY val jelöljük, és az {aY : yET} )'E I•
   .számo.s,ságok .szorzatának nevezzük.
   2. Válasszunk olyan, páronként diszjunkt {A~: yET} halmazokat, hogy minden yEP-ra ~A~ ~=a! . Az (J A~ halmaz számosságát ~ ay val ;,ET vET
   jelöljük, és az {agy: yET} számosságok összegének nevezzük.
   3. Legyenek a, b számosságok. Válasszunk olyan A, B halmazokat, melyekre I A~ =a, jBj=6. Az BA halmaz számosságát ab-vel jelöljük, és az a számosság b-edzk lrawárryának nevezzük.
   A definíciók értelmességét csak a I0. fejezet egy tételének felhasználásával tudjuk igazolni. Ott bebizonyítjuk, hogy a számosságoperáció úgy definiálható, hogy minden a számosság maga is egy a számossápú halmaz. Ez biztosítja, hogy számosságok tetszőleges {aY: yEI'} rendszeréhez t    Végü! az ~.2. ~tétel~ biztosítja, hogy egyik operáció értéke sem függ    Ha ao, a, tetszőleges számosságok, akkor az ao+ar= L a;,
   a0.C7i =aoat= av jelöléseket is használjuk.
   "természetesen a+b és a~b definíciójához nem kell a kiválasztási axiómát alkalmazni, végtelen sok argumenturnű művelet esetén viszont igen. Erre azonban a későbbiekben már nem hívjuk fel a figyelmet. Példák:
   al ~to-r\„=~„. 9 b~ cos„-~~.
   a) és b) a 3.3. és a 3.4. tételből következik.
   c) 2~~>l`to. Ennek igazolásához csak azt kell tudni. hogy 2~~= _ ~ ~2 ~ és `°2 ~ P(~), hiszen az co-n értelmezett, 0 és 1 értéket felvevő, ún. karakterisztikus függvények halmaza és az u~ összes részhalmazaiból álló halmaz között létezik kanonikus egy-egyértelmű megfeleltetés.
   Minden nehézség nélkül igazolható a következő tétel is.
   5.3. TÉTEL. Az összeadás, a szorzás és a haty°ányozás a nercnegatív egész számok között értelmezett megfelelő műveletek kiterjesztése. Bizonyítás: Legyenek A, B olyan véges halmazok, meh~ekre ,A,=n, ~B~=m. Ekkor
   ~AXB~=m~n, ~BA~=nn. Továbbá, ha Af1 B=~ is teljesül, akkor ~AUB~=m-1-n.
   5.4. TÉTEL.
   1. Az összeadás és a szorzás kommutatív műveletek. 2. Az összeadás és a szorzás asszociatív műveletek.
   3. Az összeadás, a szorzás és a hatványozás gyenge értelemben monoton:
   Bizonyítás: Az 1. állítás az unió és a direkt szorzat kommutativitásából következik. A 2. állítás az összeadásra az unió asszociativitásából következik, a szorzásra pedig a direkt szorzat asszociativitását pótló 4.1. tétel következménye. A 3. állítás bizonyítására tegyük fel, hogy ar. a~ (y~r), és a, a', b, b' olyan számosságok, melyekre
   aysaY, ama', b-b'. Azt kell bebizonyítani, hogy
   av- ~ ars vEr vEr
   7-~ c ~-~Alar- llav~ vEr vEr
   és
   ab - a b~.
   A bizonyítást csak az összeadásra mutatjuk be, a másik két bizonyítás ehhez hasonló. Választunk olyan AY, AY halmazokat, melyek rendre páronként diszjunktak, és amelyekre teljesül, hogy minden ~ _T elemre iAYi-a,., ~Av~=aY.
   Felhasználva. hogy aY~ ay, választunk olyan AY' ~ Ay halmazokat, melyekre Al,~A~'. Az 5.2. tétel szerint
   '.Er !:Er rEr vEl'
   Megemlítjük a kiválasztási axióma egy következményét: Ha A= U AY, akkor 1,41,E ~ ~AY~.
   YEr ;Er
   Valóban, megválasztva az A,, páronként diszjunkt halmazokat és a cpY leképezéseket, melyekre A~„,4_ AY, és A'-vel jelölve az ,,U A~ halmazt, a ~X= U cpY leképezés az A' halmazt A-ra képezi le,
   : ~r
   fA'j= ~ AY~= ~ ~AY~. Er YEr
   A 4.7. következmény szerint ~ A I, ~ j A' ~ .
   Az 5.4. definíciókban meghatározott műveletekre a szigorú monotonitás nem igaz. Ezt mutatják a következő példák:
   a) ~o+U=~o+1=~0~--~0=~0, b) X0.1=`0.2=~0~~o=~to.
   A hatványozásra a 6. fejezetben adunk példát.
   Az összeadás és a szorzás disztributivitásának bizonyításához a megfelelő halmazműveletek közötti disztributivitásra van szükségünk. Ezt mondja ki a következő tétel.
   5.5. TÉTEL (Álta/áno.s disztributív törvény). Ha {AY, a : S;J.,} tetszőleges halmazrendszerek ,y I'-ra, akkor
   X U AY, ő U ~ X `4Y. ~ iY>) .
   ;'Er (óE 1Y ) ~ E X dY vEr vE r
   Továbbá, ha az egyes halmazrendszerek minden ~-ra páronként diszjunkt halmazokból állnak, akkor a jobb oldalon páronként diszjunkt összeadandók szerepe:aek.
   Bizonyírás: Jelöljük a bal oldalon álló halmazt P-vel, a jobb oldalon állót R-rel.
   .Í~p~dyEr~Í(1')E U AY,a)a hE ~1y
   a d y El' ~ S(.f (Y) E Ay, a)~
   Használva a kiválasztási axiómát, ez azzal ekvivalens, hogy Ez pedig ekvivalens az fE R állítással.
   Tegyük fel, hogy
   A3,,anA,,h.=~, ha b, S'E~Jy, SAS' és yE1'.
   Legyen
   ~~~'E X 4Y. vE r Ekkor
   ~YEr ~~Y)~~~Y)~
   Ha most fE X Av. ~ (Y) és , f' E )( A1,, ~, (Y), akkor vE t' vEr
   .Í ~i') E Ay. a (v)' % ~Y ) E Ay. ~' (v)'
   és így f~f'. Ezért az R halmaz összeadandói diszjunktak.
   Hasonló általános disztributív törvény bizonyítható, ha az X, U pár helyére az (1, U vagy az U, () párt írjuk. Ezekre azonban most nincs szükségünk.
   ~.1. KÖVETKEZMÉNY. Ha (ay, a : SE 4y} számosságrendszerek yE I'-ra, akkor
   ~ al =
   vE r `e~ av~ ~ E ~ `w ~ s,Éi, aY. ~ (Y)~, 5'E r
   azaz érvényes az általános disztributív törvény a számosságok összeadására és szorzására.
   Bizonyítás: Válasszunk olyan páronként diszjunkt AY, ~ halmazokat, melyekre
   ~A,,,a~=axs, ha SE4y és yEP. Ekkor az 5.5. tételt alkalmazva kapjuk az állítást.
   42
   Végül belátjuk, hogy érvényesek maradnak a hatványozás nemnegatív egész számokra vonatkozó ismert azonosságai is.
   5.6. TÉTEL. Legyenek a, b, c (aY, bY: yEr} tetszőleges számosságok. Ekkor érvényesek a következő azonosságok:
   l. ab`=(ab)`.
   2. Ha b= ~ bY, akkor an= ~ abY. ;'E L' i'E T
   3. Ha a= ~ aY, akkor ab= rl a!'.
   Bizonyítás: Válasszuk meg az A, B, C halmazokat úgy, hogy ~ A ~ = a, jB~=6, ~C~=c legyen.
   I. an`=lBxc,gl, Az 5.1. tétel szerint (Y,z)E BXC zEC yEB Az utolsó halmaz számossága (ab)`.
   2. Legyenek a BY halmazok páronként diszjunktak, melyekre 8= U BY, és jBY~=bY, ha yEI'.
   ,Er
   Az 5.1. tétel szerint BA~XAtiX(XA1=XByA. xEL: :'E I' xEB 7E[.
   Az utolsó halmaz számossága ~ abc. ~ET
   3. Válasszuk meg az AY halmazokat (yF_I') úgy, hogy A ti X Agy, és ~ AY j = ay
   ~'E L.
   teljesüljön d)'EI'-ra. Ekkor ab= ~BAI.
   Az 5.1. tétet szerint
   BA= X A ti X ~ X AY~ ~ X ~ X A,,)= X (BAy). xEB xE6 rEi. '-EP xEBy vET
   Az utolsó halmaz számossága a,',
   ;'E 1'
   1
   5.2. KÖVETKEZMÉNY. A szorzás „ismételt" összeadás. A hz~tvánvozás „ismételt" szorzás. Ezen azt értjük, hogy ha a számosság és ;~#,=b, akkor
   a=ab és ~ a=ab.
   xEB ~~e Bizonyítás: Alkalmazva a disztributivitást: a=a~ ~ 1=a~b.
   x13 xEe
   A második állítást bizonyínja a ~i
   ,~ a= a~=B = a; .,B
   egyenlőség.
   • f é5Z
   ~6. Példák
   A 3. e~'ezet végén tett í`7éretünkhöz híven, most az általános tételek se~ítségé~-al számos egyszerű összefüggést bizonyítunk. Tanulságos lenne. ha az ol~:~só ezeket i:özaet(enül (az általános tételei; segítsége nélkül) is bebizonví:::~~á.
   6.3. .~rt.ir.~s. Ha kim és /c_=0, akkor f: _ ,
   :;a -Zo•
   Bi.-oaayítcís: Az állítást teljes indukcióval bizonyítjuk: k= I-re az állítás tri~rális. (,egyen k> I. Az indukciós feltevés szerint
   Az ~~,=_ ~,s állítást viszont már bizonyítottuk. 6.?. At t,íi_~s. C=2~J.
   Bi~omyírti;: Azt kell belátnunk, ho~~y R =?gin. A 3.;5, tétel szerint ~ R, _` {+~, 11 . hekintsük a tetszőleges x ~ [0, 1 j valós számnak azt az x=[0. a-n w . . . .v . . . ]y diadikus tört előállítását, melyben nem áll bizonyos helytől kezdve csupa 1-es.
   Az ell~állítás indukálja [0, 1) egy-egyértelmű leképzését '2-be. Ezért ~R~ ~ 2~ •. ~~ásrészt, tetszőleges , fF `-'_2 Cüggvénynek f-eleltessü!: me;~ azt az aI valós számot, melynek tizedeltört előállítása :~j=(-), f;i))j(1)... . Ezzel ~-t egy--egyértelműen R-be kéneztük. lgy _sü- ; R, is i,az.
   45
   6.3. Áttírds. Ha a végtelen számossá~~, okkor a+~~=a.
   Bizoltyitás: Legyen A olyan halnrtz, melyre ~A~=a. A 3.6. tétel szerint létezik olyan A'~--A halmaz, melyre ~A'I=~„. Legyen B=A\A', és jBj=b. Ekkor a=b+~„. Ezért
   6.4. Átt_irds. Az E° n-dimenziós euklideszi térre ~E"I=C. B1ZOnVÍI~I.S': ~E°!=1'?~1=~t=(2N°~n=2K°'n=2H°=C.
   6.5. Áttírds. Az összes valós számsorozatok halmaza c számossápú. Bizon yi tás
   _ _ _
   6.6. Át.tírds. Jelölje.;y- az összes valcSs függvények halmazát. Ekkor f i ,x~
   =2~ -C.
   BiZOtI j ítá.r:
   - _ _
   hiszen a 6.4. allítaís szerint C--~oC=C''-=c.
   6.7. Átl_ÍTÁS. Lef;yen C(i~) a folytonos valós függvények halmaza. Ekkor IC(R)', _- C.
   Bi~oltyítás: Az elemi analízis egy közismert tétele szerint, ha f folytonos valós függvény, akkor)=et a racionális helyeken felvett értékei meghatározzák. Ezért
   Másrészt a konstí~ns függvények folytonosak, így c-= !C(R)
   is teljesül.
   6.8. Á~LfTÁS. Definiáljuk a {c„:nEco}számosságsorozatot rekurzióval a következőképpen:
   Cantor tétele szerint Co    c~=c„> ha nEu~.
   Bizorwítcís: Az állítást teljes indukcióval bizonyítjuk. m=0-ra Cő=~ő=~o=Co.
   Tegyük fel, hogy nEa~ és a-re már tudjuk az állítást, azaz Cn- Ca .
   Ekkor
   Cn~Cn•2-Cn• C„=Cn=Cn.
   Ezért
   ni-!
   Az összes ed~3i~ me Yismert vé 7telen számosság a fenti cn-ek valamelyike. Ezért a 6.8. állítós alakján felmerül az a kérdés, hogy igaz-e tctszőle Les vet=telep számo:~saí`~ra az a~=cr összefüg<~és? A válasz i~~enlő. Ezt a fontos tényt a sztímossá~aritmetika alaptútelének is szokás nevezni (lásd 10.3. tétel). Ez ismét olyan állítás, amely csak a kiválasztási axióma segítségével bizonyítható. Megemlítjük bizonyítás nélkül, hogy ez az állítás ekvivalens is a kiválasztási axiómával.
   6.9. ÁLLíTÁS. Legyen a d számosság az előbbi Cr=-ek összege. Belátjuk d-re is a d2=d összefüggést.
   B1ZOi11~1 tci.S
   = S Cx(2Co-F- . . . -1-2Ck_1-~ C,;)= ~ Ck= ~ C;;=d. kE~. kEw
   A számolás során a disztributív törvényt és a 6.8. állítást használtuk. A d számosság nyilván valamennyi cn-nél nagyobb, hiszen Cn< Cn-i~d teljesül. J
   6.10. ÁLLíWS. Az előző pontban definiált d szá3nosságra fennáll a d~~=2'' összefüe°és.
   Bizonyítás:
   F+ ~n
   2d=2^E~ _ ~ ZC"= ~ Collo d=d~o. nEco nEm nEa~ Ezért 2d-d•e. Továbbá
   és így a gyenge monotonitás miatt ~`o c ~L~d= 2d
   A 6.10. állítással példát nyertünk arra, hogy a hatványozás az erős értelemben nem monoton.
   Végül bebizonyítjuk a 4.6. Cantor-tétel következő általánosítását.
   6.1. "í~rEt. Számosságok tetszőleges {ay: ycT} rendszerél.ez létezik olyan számosság, mely valamennyinél nagyobb.
   Bizonyítás: Legyen á = ~ ay és a=2°'. Ha ,~''-_P. akkor ay~á    A 6.1. tétel biztosítja, hogy nagyon sol< számosság van, hiszen nem
   létezik olyan halmaz, amely az összes számosságot tartalmazza. 40
   Összefo<7laljuk, hogy melyek azok a tételek, amelyeknek bizonyításával adósak maradtunk. Először is ilyen a teljes indukcióval való bizonyítás és a rekurzióval való definiálás jogosultsá~~a. Másodszor, ilyen a számossá`~operáciő létezésének bizonyítása, melyet a kiválasztási axióma se~~ítsévével fogiunk elvévezni.
   F tételeket használtuk már, ezért természetesen üvyelnünk kell majd, hogy bizonyításunkban ne alkalmazzuk azokat a tételeket. amelyeket ezek sevítsé~: vel nyertünk.
   Végül adósak maradtunk a trichotomia-tétel és a számosságaritmetika alaptételinek - a kiválasztási axiómán alapuló - bizonyításával. Mindezekhez az alapvető segédeszközöket a rendezett halmazok elmélete adja.
   Feladatol':
   1. Bizonyítsuk be, hogy o összes véges részhalmazainak halmaza mevszámiálható !
   2. Bizonyítsuk be, hogy ha az a számosságra a - c. akkor r;-a= c. 3. Bizonyítsuk be, hogy ha bármely végtelen a számosságra a='=a, akkor bármely két végtelen számosságra b;-c=bc.
   4. Bizonyítsuk be, hogy c~ összes permutációinak halmaza 2~~ számossávú!
   5. Bizonyítsuk be, hogy az irracionális számok halmaza C számossápú! 6. Bizonyítsuk be, hogy minden nemüres, perfekt, valós számhalmaz c számossávú!
   7. Bizonyítsuk be, hogy a [0, 1] intervallumon Lebesgue-mérhető függvények halmaza c~ számossápú!
   S. Bizonyítsuk be, hogy a [U, 1] intervallumon Riemann-integrálható függvények halmaza is c~ számossápú!