8. Úplné svazy
Svaz A se nazývá distributivní, pokud pro libovolné prvky a; b; c 2 A platí a _ (b ^ c) = (a _ b) ^ (a _ c) .
Lemma 8.1. Buï A distributivní svaz. Pak pro libovolné prvky a; b; c 2 A platí a ^ (b _ c) = (a ^ b) _ (a ^ c): Dùkaz. Z distributivního zákona plyne, ¾e (a ^ b) _ (a ^ c) = ((a ^ b) _ a) ^ ((a ^ b) _ c): První závorka výrazu vpravo je zøejmì rovna a. Pou¾ijeme-li na druhou závorku vpravo distributivní zákon, dostaneme, ¾e (a ^ b) _ (a ^ c) = a ^ ((a _ c) ^ (b _ c)) = (a ^ (a _ c)) ^ (b _ c): Ponìvad¾ první závorka vpravo je rovna a, dùkaz je ukonèen. Lemma 8.2. Libovolná lineárnì uspoøádaná mno¾ina je distributivní svaz. Dùkaz. Pøedev¹ím si uvìdomme, ¾e libovolná lineárnì uspoøádaná mno¾ina A je svaz. Nech» a; b; c 2 A. Pøedpokládejme, ¾e b c (v opaèném pøípadì je dùkaz analogický). Pak b ^ c = b. Pokud a b, pak obì strany distributivního zákona jsou rovny b. Pokud b a c, obì strany jsou rovny a. Koneènì, pokud c a, obì strany se rovnají a. V libovolném distributivním svazu platí (a ^ b) _ (c ^ d) = (a _ c) ^ (a _ d) ^ (b _ c) ^ (b _ d): Ovìøení se provede opakovanou aplikací distributivního zákona. Úplný svaz A se nazývá úplnì distributivní, pokud v nerovnosti
^_a
(1)
i 2I j 2Ji
ij
_ ^a
f 2F i 2I
if (i)
(viz kapitola 6.) v¾dy platí rovnost. Vìta 8.3. Libovolná úplná lineárnì uspoøádaná mno¾ina je úplnì distributivní. Dùkaz. Víme, ¾e v¾dy platí nerovnost (1). Oznaème její levou stranu x a pravou y. Pøedpokládejme, ¾e x > y. Pøedpokládejme dále, ¾e neexistuje prvek x > z > y. W aij pro v¹echna i 2 I , pro libovolné i 2 I existuje f (i) 2 Ji tak, Ponìvad¾ x j 2Ji V ¾e y < aif (i), t.j., x aif (i). Pro takto vzniklé f 2 F platí aif (i) x > y, co¾ i 2I je spor. Tedy existuje prvek xV> z > y. Pak pro libovolné i 2 I existuje f (i) 2 Ji tak, ¾e z < aif (i). Tedy z aif (i), tak¾e y z, spor. i 2I
Rovnì¾ (P (M ); ) je úplnì distributivní úplný svaz pro libovolnou mno¾inu M . Typeset by
1
AMS-TEX
2
Pøíklad 8.4. Buï V vektorový prostor (nad R). Symbolem L(V ) oznaèíme mno-
¾inu v¹ech vektorových podprostorù ve V uspoøádanou mno¾inovou inkluzí. Ponìvad¾ libovolný prùnik vektorových podprostorù je vektorový podprostor, L(V ) je úplný svaz (podleW 6.2). Jsou-li Wi , i 2 I vektorové podprostory V , pak jejich supremum W = i2I Wi v L(V ) je vektorový podprostor generovaný sjednocením S Wi. Tedy prvky W jsou právì lineární kombinace r1v1 + : : : rnvn vektorù i 2I S v1; : : : ; vn 2 i2I Wi . Úplný svaz L(V ) není obecnì distributivní. Uva¾ujme vektorový prostor R2 a vektory v1; v2 ; v3 2 R2, které jsou po dvou lineárnì nezávislé (napø., v1 = (0; 1); v2 = (1; 0); v3 = (1; 1)). Nech» Wi je vektorový podprostor generovaný vi , i = 1; 2; 3. Pak W2 ^ W3 = O, kde O = f(0; 0)g je nejmen¹í vektorový podprostor v R2. Tedy W1 _ (W2 ^ W3) = W1. Na druhé stranì, (W1 _ W2) ^ (W1 _ W3) = V ^ V = V . Tedy distributivní zákon neplatí. Podmno¾ina X uspoøádané mno¾iny A se nazývá usmìrnìná, pokud pro libovolnou koneènou mno¾inu prvkù x1; : : : ; xn 2 X existuje prvek x 2 X takový, ¾e xi x pro v¹echna i = 1; : : : ; n. Napøíklad, libovolná lineárnì uspoøádaná podmno¾ina v A je usmìrnìná. Libovolná usmìrnìná mno¾ina je neprázdná (staèí zvolit n = 0). Úplná uspoøádaná mno¾ina se de nuje jako uspoøádaná mno¾ina A s nejmen¹ím prvkem, v ní¾ libovolná usmìrnìná podmno¾ina má supremum. Lze ukázat, ¾e uspoøádaná mno¾ina A je úplná, právì kdy¾ libovolná lineárnì uspoøádaná podmno¾ina v A má supremum. Ná¹ zájem o úplné uspoøádané mno¾iny je dán tím, ¾e suprema usmìrnìných podmno¾in jsou èasto pøirozenìj¹í ne¾ obecná suprema. Pøíklad 8.5. Buï A mno¾ina a A mno¾ina v¹ech koneèných posloupností a1 : : : an prvkù mno¾iny A. Jedná se vlastnì o "slova" nad "abecedou" A. Uspoøádáme mno¾inu A pomocí pre xù. To znamená, ¾e w1 w2, pokud w1 je poèáteèní úsek w2. Vzniklá uspoøádaná mno¾ina (A ; ) nemá ¾ádná netriviální suprema (kromì sup;, co¾ je prázdné slovo, a suprem srovnatelných prvkù). Supremum nekoneèné lineárnì uspoøádané mno¾iny v¹ak má pøirozený význam (napø., desetinný rozvoj reálného èísla). Tedy "nekoneèné slovo" aa : : : reprezentuje supremum øetìzce a aa : : : . Naproti tomu, ¾ádný rozumný význam nelze pøipsat supremu slov a, b, kde a; b 2 A jsou navzájem rùzné. Vìta 8.6. Buï A úplná uspoøádaná mno¾ina, která je svaz. Pak A je úplný svaz. Dùkaz. Potøebujeme ukázat, ¾e libovolné supremum lze rozlo¾it na usmìrnìné supremum koneèných suprem. Nech» ai 2 A pro i 2 I . Buï J mno¾ina koneèných podmno¾in mno¾iny I . Snadno se ovìøí, ¾e platí
_a = _ _ a :
i 2I
i
X 2J x2X
x
Prvek a uspoøádané mno¾iny A se nazývá kompaktní, pokud pro libovolnou usmìrnìnou podmno¾inu X A takovou, ¾e a supX existuje prvek x 2 X s vlastností a x.
3
Nejmen¹í prvek uspoøádané mno¾iny je v¾dy kompaktní. V koneèné uspoøádané mno¾inì je libovolný prvek kompaktní. Ve vìt¹inì uspoøádaných mno¾in vyskytujících se v informatice, je uspoøádání zalo¾eno na "mno¾ství informace nesené objekty": a b znamená, ¾e b nese aspoò tolik informace jako a. Takto lze interpretovat i nekoneèná slova zmínìná v 8.5. Kompaktní prvek je pak ten prvek a, který nese podstatné mno¾ství informace; pokud supremum usmìrnìné mno¾iny X zahrnuje informaci obsa¾enou v a, pak ji nutnì zahrnuje nìjaký prvek v X . Pøíklad 8.7. (1) Buï M mno¾ina. Uká¾eme, ¾e kompaktní prvky v P (M ) jsou koneèné podmno¾iny. Buï K M koneèná, X P (M ) usmìrnìná a K Správì X . Pak pro libovolný prvek a 2 K existuje Xa 2 X tak, ¾e a 2 Xa . Ponìvad¾ X je usmìrnìná a K koneèná, existuje X 2 X tak, ¾e Xa X pro ka¾dé a 2 K . Tedy K X . Dokázali jsme, ¾e K je kompaktní. Naopak, libovolnou nekoneènou podmno¾inu K M mù¾eme vyjádøit jako usmìrnìné sjednocení v¹ech koneèných podmno¾in v K . Tedy K nemù¾e být kompaktní. (2) Buï V vektorový prostor. Uká¾eme, ¾e kompaktní prvky v L(V ) jsou právì koneènìrozmìrné podprostory ve V . uká¾eme, ¾e pro libovolnou usmìrnìnou podmno¾inu X L(V ) je X = S XNejprve vektorový podprostor. Nech» v1 ; v2 2 X . Pak existují W1 ; W2 2 X tak, ¾e vi 2 Wi pro i = 1; 2. Ponìvad¾ X je usmìrnìná, existuje W 2 X tak, ¾e W1; W2 W . Tedy v1 ; v2 2 W a proto libovolná lineární kombinace vektorù v1 ; v2 patøí do W a proto i do X . Tedy X 2 L(V ). Buï nyní W koneènìrozmìrný podprostorS ve V a e1; : : : ; en báze W . Buï X L(V ) usmìrnìná podmno¾ina a W X . Tedy existují Wi 2 X tak, ¾e ei 2 Wi pro libovolné i = 1; : : : n. Ponìvad¾ X je usmìrnìná, existuje W 0 2 X tak, ¾e Wi W 0 pro i = 1; : : : ; n. Tedy W W 0 . Dokázali jsme, ¾e W je kompaktní. Naopak, libovolný nekoneènìrozmìrný vektorový prostor lze vyjádøit jako usmìrnìné sjednocení svých koneènìrozmìrných podprostorù. Nemù¾e tedy být kompaktní. Úplný svaz A se nazývá algebraický, jestli¾e libovolný prvek a 2 A je supremum kompaktních prvkù. Z 8.7 vyplývá, ¾e P (M ) a L(V ) jsou algebraické svazy. Vìta 8.8. Buï A algebraický svaz. Pak
a^
_ b = _ (a ^ b )
i 2I
i
i 2I
i
pro libovolný prvek a 2 A a libovolnou usmìrnìnou podmno¾inu fbi ni 2 I g v A. Dùkaz. Víme, ¾e v¾dy platí nerovnost
x=a^
_ b _(a ^ b ) = y:
i 2I
i
i 2I
i
W
Buï z x kompaktní prvek. Pak z a a z i2I bi . Ponìvad¾ mno¾ina fbi ni 2 I g je usmìrnìná, existuje i 2 I tak, ¾e z bi . Tedy z a ^ bi y. Ponìvad¾ x je supremum kompaktních prvkù, platí x y.
4
Q
Buï I mno¾ina a Ai , i 2 I uspoøádané mno¾iny. Pak kartézský souèin Ai i 2I uspoøádáme následovnì: (ai )i2I (bi )i2I , ai bi pro v¹echna i 2 I: Snadno se ovìøí, ¾e se skuteènì jedná o relaci uspoøádání (øíkáme, ¾e se jedná o uspoøádání po slo¾kách). Vzniklou uspoøádanou mno¾inu nazýváme souèinQ uspoøádaných mno¾in Ai . Jsou-li Ai , i 2 I lineárnì uspoøádané mno¾iny, pak Ai i 2I nemusí být lineárnì uspoøádaná. Staèí uvá¾it souèin dvou dvouprvkových øetìzcù. Pøíklad 8.9. Buï Eq(X ) mno¾ina v¹ech relací ekvivalence na mno¾inì X uspoøádaná inkluzí. Pak Eq(X ) je úplnýSsvaz nebo» libovolný prùnik relací ekvivalence je relace ekvivalence. Sjednocení Ri relací ekvivalence Ri 2 Eq(X ), i 2 I není i 2I S obecnì relace ekvivalence a supRi je relace ekvivalence generovaná Ri (t.j., nei 2I S jmen¹í relace ekvivalence obsahující Ri). Snadno se v¹ak ovìøí, ¾e sjednocení i 2I usmìrnìné mno¾iny relací ekvivalence je relace ekvivalence. Kompaktní prvky v Eq(X ) jsou právì relace ekvivalence generované koneènou podmno¾inou S X X . Svaz Eq(X ) je algebraický, není pøitom distributivní. Vìta 8.10. Buïte Ai , i 2 I úplné svazy. Pak Q Ai je úplný svaz. Jsou-li Ai i 2I Q (úplnì) distributivní úplné svazy, pak Ai je (úplnì) distributivní. i 2I
Dùkaz. Snadno se ovìøí, ¾e platí
_ (a
j 2J
ji )i2I = (
^ (a
j 2J
_a
j 2J
ji )i2I = (
ji )i2I
^a
j 2J
ji )i2I
Odsud ji¾ ihned plyne tvrzení o (úplné) distributivitì. Pøedvedeme to pro distributivitu: (ai ) _ (bi ) ^ (ci ) = (ai _ (bi ^ ci)) = ((ai _ bi ) ^ (ai _ ci)) = ((ai ) _ (bi )) ^ ((ai ) _ (bi ))
9. Kardinální èísla
Ka¾dé mno¾inì A pøiøadíme symbol jAj takový, ¾e jAj = jBj, právì kdy¾ mno¾iny A; B mají stejnou mohutnost. Symboly jAj se nazývají kardinální èísla. Kardinální èíslo jAj rovnì¾ nazýváme mohutnost mno¾iny A. Ponìvad¾ "mít stejnou mohutnost" je relace ekvivalence, postup je korektní. Není v¹ak podán v termínech teorie mno¾in nebo» kardinální èísla nejsou de nována jako mno¾iny. Pozdìji naznaèíme, jak lze kardinální èísla de novat v termínech teorie mno¾in.
5
Pøíklady. (1) Nezáporná celá èísla pova¾ujeme za kardinální èísla a sice za mohutnosti koneèných mno¾in. (2) Mohutnost spoèetné mno¾iny znaèíme @ . 0
(3) Mohutnost mno¾iny reálných èísel nazýváme mohutnost kontinua a znaèíme ji c. Polo¾íme jAj jBj, jestli¾e existuje prosté zobrazení A ! B. Relace mezi kardinálními èísly je zøejmì re exivní a tranzitivní. Uká¾eme, ¾e je uspoøádání. Pøedev¹ím si uvìdomíme, ¾e pokud A B, pak jAj jBj (nebo» zobrazení inkluze A ! B je prosté). 9.1. Cantor-Bernsteinova vìta. Z jAj jBj a jBj jAj plyne jAj = jBj. Dùkaz. Mìjme prostá zobrazení f : A ! B a g : B ! A. Musíme ukázat, ¾e pak existuje bijekce A ! B. Uva¾ujme zobrazení h : P (A) ! P (B) de nované vztahem
h(X ) = A g(B f (X )) Nech» X; Y 2 P (A), X Y . Pak postupnì platí f (X ) f (Y ), B f (Y ) B f (X ), g(B f (Y )) g(B f (X )) a h(X ) h(Y ). Tedy h : P (A) ! P (B) je isotonní zobrazení (obì mno¾iny P (A); P (B) jsou uspoøádané mno¾inovou inkluzí). Podle Vìty 6.3., existuje C A tak, ¾e
C = A g(B f (C )): De nujme zobrazení t : A ! B takové, ¾e t(x) = f (x) pro x 2 C a t(x) = g 1(x) pro x 2= C . De nice je korektní nebo» pro x 2= C platí x 2 g(B f (C )). Uká¾eme, ¾e t : A ! B je bijekce. Pøedpokládejme, ¾e pro x 2 C a y 2= C platí t(x) = t(y). Pak f (x) = g 1(y), tak¾e g(f (x)) = y 2= C . Zároveò f (x) 2= B f (C ) (nebo» x 2 C ), tak¾e g(f (x)) 2= g(B f (C )) a tedy g(f (x)) 2 C ; spor. Tedy t je prosté zobrazení nebo» obì zú¾ení t na C a A C jsou prostá. Nech» y 2 B, y 2= t(A). Pak y 2= f (C ), tak¾e y 2 B f (C ) a tedy g(y) 2= C . To v¹ak znamená, ¾e y = t(g(y)), spor. Tedy t je zobrazení na. Poznámka 9.2. (1) Ponìvad¾ zobrazení f : A ! P (A), f (a) = fag je v¾dy prosté, pro libovolnou mno¾inu A platí jAj jP (A)j. Z Cantorovy vìty plyne, ¾e v¾dy
jAj < jP (A)j: Odsud plyne, ¾e neexistuje nejvìt¹í kardinální èíslo. Vìta 9.3. Kardinální èísla netvoøí mno¾inu. Dùkaz. Pøedpokládejme, ¾e existuje mno¾ina I a mno¾iny Ai, i 2 I tak, ¾e jASi j, i 2 S I vyèerpává v¹echna kardinální èísla. Ponìvad¾ Ai Ai , platí jAi j j Ai j. i 2I i 2I S Tedy j Ai j je nejvìt¹í kardinální èíslo, co¾ odporuje poznámce 9.2. i 2I
6
Z Cantorovy a Cantor-Bernsteinovy vìty rovnì¾ plyne, ¾e neexistuje mno¾ina v¹ech mno¾in. Pro takovou mno¾inu M by toti¾ platilo, ¾e jP (M )j jM j nebo» libovolná podmno¾ina M je prvkem M . Tedy jP (M )j = jM j, spor. Zatím nejsme schopni zjistit, zda uspoøádání kardinálních èísel je lineární. Dosud známá kardinální èísla jsou 0 < 1 < < @0 < c: Z 4.4. plyne, ¾e @0 je minimální nekoneèné kardinální èíslo. Otázka, zda c je nejmen¹í nespoèetné kardinální èíslo je nerozhodnutelná. Vìta 9.4. c = jP (!)j. Dùkaz. Z dùkazu vìty 4.3. víme, ¾e c jP (!)j. Z konstrukce reálných èísel jako øezù ve spoèetné mno¾inì Q víme, ¾e c jP (!)j. Tedy c = jP (!)j. Operace s kardinálními èísly: Nech» = jAj a = jBj, pøièem¾ mno¾iny A; B jaou v (1) disjunktní. Polo¾me (1) + = jA [ Bj (2) = jA Bj (3) = jAB j Buïte P I , Ai ; i 2 S I mno¾iny, pøièem¾ Ai jsou navzájem disjunktní. (4) i = j Ai j i 2I i 2I De nice je korektní nebo» operace nezavisí na volbì mno¾in A; B. Skuteènì, jsou-li f : A ! A0 a g : B ! B0 bijekce, pak f [ g : A [ B ! A0 [ B0 pro A; B a A0 ; B0 disjunktní a
f g : A B ! A0 B0 h : AB ! (A0 )B ; h(u) = f u g 0
1
jsou bijekce. Operace +; jsou asociativní, komutativní a distributivní, co¾ plyne z vlastností mno¾inových operací [; . Navíc, z Vìty 4.1. plyne, ¾e platí ( ) = ( ) = + = : Dále platí ) + + ) : Skuteènì, je-li f : A ! B prosté zobrazení, pak zobrazení f [ idC : A [ C ! B [ C a f idC : A C ! B C jsou rovnì¾ prostá. Tvrzení vìty 9.4 lze pøepsat ve tvaru c = 2@0
7
Vìta 9.5. @ @ = @ , @ + @ = @ : 0
Dùkaz. Platí
0
0
0
0
0
@0 + @0 = jNj + j!j = jZj = @0
Podobnì @0 @0 = @0 plyne z toho, ¾e Q je spoèetná mno¾ina (viz 4.2. (4)). Vìta 9.6. Je-li S spoèetná mno¾ina reálných èísel, pak jR S j = c. Dùkaz. Máme jR Rj = 2! 2! = 2!+! = 2! . Tedy místo R mù¾eme vzít mno¾inu RR. Buï tedy S RR spoèetná mno¾ina. Existuje x 2 R tak, ¾e S \(Rfxg) = ;. Tedy fxg R R S , tak¾e jR S j = c. Dùsledek. Mohutnost mno¾iny iracionálních èísel je c. Vìta 9.7. Mohutnost mno¾iny v¹ech koneèných posloupností pøirozených èísel je @0 . Dùkaz. Buï P mno¾in v¹ech koneèných posloupností pøirozených èísel. Zøejmì @0 jP j. Pro dùkaz opaèné nerovnosti zapi¹me libovolné pøirozené èíslo a v dvojkové soustavì. Posloupnost a1 : : : an pak urèuje racionální èíslo 0; a1 2a22 : : : an. Ponìvad¾ rùzné posloupnosti zøejmì urèují rùzná racionální èísla, platí jP j jQj = @0 . Dùsledek. Mohutnost mno¾iny koneèných podmno¾in spoèetné mno¾iny je @0 . Pøipomeòme, ¾e reálné èíslo se nazývá algebraické, pokud je koøenem polynomu s celými koe cienty. Libovolné racionální èíslo je zøejmì algebraické. Reálná èísla, která nejsou algebraická se nazývají transcendentní. Transcendentní jsou napøíklad èísla ; e; dùkaz je v¹ak obtí¾ný. Uká¾eme, ¾e transcendentní èísla existují (a ¾e jich je víc ne¾ algebraických). Vìta 9.8. Mno¾ina A v¹ech algebraických èísel je spoèetná. Dùkaz. Mno¾ina v¹ech polynomù s celými koe cienty se oznaèuje Z[x]. Z vìty 9.7. plyne, ¾e to je spoèetná mno¾ina, t.j., existuje bijekce f : ! ! Z[x]. De nujme zobrazení g : A ! ! ! vztahem g(a) = (n; k), kde n je nejmen¹í èíslo takové, ¾e a je koøen polynomu f (n) a a je pøitom k-tý reálný koøen tohoto polynomu v uspoøádání podle velikosti. Zobrazení g je zøejmì prosté, tak¾e jA j @0 . Ponìvad¾ Q A , A je spoèetná mno¾ina. Dùsledek. Mno¾ina v¹ech transcendentních èísel má mohutnost kontinua. Dùkaz plyne z vìty 9.6. a 9.8. 10. Dobøe uspoøádané mno¾iny
De nice. Øekneme, ¾e lineárnì uspoøádaná mno¾ina je dobøe uspoøádaná, jestli¾e
libovolná její neprázdná podmno¾ina má nejmen¹í prvek. Pøídavné jméno lineárnì jsme mohli v de nici vynechat nebo» to plyne z existence nejmen¹ích prvkù dvouprvkových podmno¾in. Libovolná podmno¾ina dobøe uspoøádané mno¾iny je zøejmì dobøe uspoøádaná.
8
Pøíklady. (1) Libovolná koneèná lineárnì uspoøádaná mno¾ina je dobøe uspoøá-
daná. ! je dobøe uspoøádaná. (2) !op; Z; Q a R nejsou dobøe uspoøádané. Vìta 10.1. Buï A dobøe uspoøádaná mno¾ina a f : A ! A prosté izotonní zobrazení. Pak pro v¹echna a 2 A platí a f (a). Dùkaz. Buï X = fa 2 Anf (a) < ag. Pokud X 6= ;, existuje nejmen¹í prvek a0 2 X . Platí f (a0 ) < a0 , tak¾e f (a0 ) < a0 . Tedy f (a0 ) 2 X , co¾ je spor s f (a0 ) < a0. Pøedpoklad, ¾e f je prosté je podstatný; pro konstantní zobrazení tvrzení neplatí. De nice. Podmno¾ina Z uspoøádané mno¾iny A se nazývá zaèátek, pokud x 2 Z , y x implikuje y 2 Z . Zaèátek Z se nazývá vlastní, pokud Z 6= A. Dùsledek. Dobøe uspoøádaná mno¾ina není isomorfní s ¾ádným svým vlastním zaèátkem. Dùkaz. Pøedpokládejme, ¾e Z je vlastní zaèátek dobøe uspoøádané mno¾iny A a f : A ! Z isomor smus. Existuje prvek a 2 A Z . Ponìvad¾ f (a) 2 Z musí platit f (a) < a, co¾ je spor s vìtou 10.1. Je-li A uspoøádaná mno¾ina a a 2 A, pak polo¾íme
A(a) = fx 2 Anx < ag Zøejmì A(a) je vlastní zaèátek v A. V dobøe uspoøádané mno¾inì A je libovolný vlastní zaèátek Z tvaru A(a) pro nìjaké a 2 A. Za a je tøeba vzít nejmen¹í prvek mno¾iny A Z . Vìta 10.2. Buïte A; B dobøe uspoøádané mno¾iny. Pak existuje nejvý¹e jeden isomor smus A ! B. Dùkaz. Buïte f; g : A ! B isomor smy. Pøedpokládejme, ¾e f 6= g. Pak existuje a 2 A takové, ¾e f (a) < g(a). Ponìvad¾ A(a) = B(f (a)) a A(a) = B(g(a)) B ( g ( a )). Navíc B ( f ( a )) je zaèátek v B ( g ( a )). Toti¾ pro libovolné platí B(f (a)) = c < f (a) existuje d 2 A tak, ¾e c = f (d). Zøejmì d < a, tak¾e c 2 B(f (a)). Dostáváme spor s dùsledkem vìty 10.1. Dùsledek. Buï A dobøe uspoøádaná mno¾ina a f : A ! A isomor smus. Pak f = idA . Vìta 10.3. Buïte A; B dobøe uspoøádané mno¾iny. Pak nastane právì jedna z následujících mo¾ností: (1) A =B (2) A je isomorfní s vlastním zaèátkem B (3) B je isomorfní s vlastním zaèátkem A. Dùkaz. Je-li jedna z mno¾in A; B prázdná, tvrzení zøejmì platí. Pøedpokládejme, ¾e obì mno¾iny A; B jsou neprázdné. Polo¾me
A0 = fa 2 An existuje b 2 B s A(a) = B(b)g
9
B0 = fb 2 Bn existuje a 2 A s B(b) = A(a)g: Ponìvad¾ A0 obsahuje nejmen¹í prvek A a B0 obsahuje nejmen¹í prvek v B, mno¾iny A0 ; B0 jsou neprázdné. Navíc to zøejmì jsou zaèátky (A0 v A a B0 v B). Doká¾eme, ¾e A0 = B0. De nujme zobrazení f : A0 ! B0 tak, ¾e A(a) = B(f (a)). Z de nice mno¾in A0 ; B0 a dùsledku vìty 10.1. plyne, ¾e takové zobrazení existuje právì jedno. Navíc to je zøejmì isomor smus. Uká¾eme, ¾e nemù¾e nastat situace, kdy A0 6= A a souèasnì B0 6= B. V tomto pøípadì v¹ak existují a 2 A a b 2 B tak, ¾e A0 = A(a) a B0 = B(b). Tedy a 2 A0 a b 2 B0, co¾ není mo¾né. Ovìøili jsme, ¾e v¾dy nastane jedna z mo¾ností (1)-(3) a zbývá ovìøit, ¾e tyto mo¾nosti se navzájem vyluèují. Nastanou-li v¹ak dvì mo¾nosti souèasnì, vznikne dobøe uspoøádaná mno¾ina isomorfní se svým vlastním zaèátkem, co¾ odporuje dùsledku vìty 10.1. Poznámka. Z vìty 10.3. plyne, ¾e pro dobøe uspoøádané mno¾iny A; B nastane právì jedna z mo¾ností j Aj = j B j ; j Aj < j B j ; j B j < j Aj : Tedy kardinální èísla dobøe uspoøádaných mno¾in jsou lineárnì uspoøádaná. Pokud by libovolná mno¾ina ¹la dobøe uspoøádat, kardinální èísla by byla lineárnì uspoøádaná. Uvidíme, ¾e tomu tak je i naopak: pokud kardinální èísla jsou lineárnì uspoøádaná, pak libovolnou mno¾inu lze dobøe uspoøádat. Zatím umíme dobøe uspoøádat ka¾dou koneènou i spoèetnou mno¾inu. Neumíme napø. dobøe uspoøádat mno¾inu R. Uvidíme, ¾e problém, zda libovolnou mno¾inu lze dobøe uspoøádat, je na základì dosavadních axiomù ZF nerozhodnutelný. Význam dobøe uspoøádaných mno¾in spoèívá mimo jiné v tom, ¾e poskytují prostøedí pro roz¹íøení pojmu indukce. Vìta 10.4. (trans nitní indukce): Buï A dobøe uspoøádaná mno¾ina. Nech» pro libovolný prvek a 2 A je dán výrok V (a). Pøedpokládejme, ¾e pro libovolné a 2 A platí: (?) Je-li pravdivý výrok V (x) pro libovolné x < a, je pravdivý výrok V (a). Pak výrok V (a) je pravdivý pro v¹echna a 2 A. Dùkaz. Nech» B = fa 2 AnV (a) je nepravdivýg. Pøedpokládejme. ¾e mno¾ina B je neprázdná. Buï a nejmen¹í prvek v B. Dostáváme spor s (?). Obvyklá matematická indukce je trans nitní indukce pro !. Z (?) plyne, ¾e výrok V je pravdivý pro nejmen¹í prvek v A. V kapitole 8 jsme vidìli, ¾e souèin lineárnì uspoøádaných mno¾in ji¾ nemusí být lineárnì uspoøádaný. V teorii dobøe uspoøádaných mno¾in proto pracujeme s tzv. lexikogra ckým souèinem. De nice. Lexikogra cký souèin AB dobøe uspoøádaných mno¾in A; B je kartézský souèin A B vybavený uspoøádáním (a; b) (c; d) , a < c nebo a = c; b d:
10
Vìta 10.5. Buïte A; B dobøe uspoøádané mno¾iny. Pak A B je dobøe uspoøádaná
mno¾ina. Dùkaz. Nech» X A B je neprázdná podmno¾ina lexikogra ckého souèinu A B. Buï a0 nejmen¹í prvek v p1(X ) a b0 nejmen¹í prvek v p2 (p1 1(a0 ) \ X ). Zøejmì (a0 ; b0 ) je nejmen¹í prvek v X . Lexikogra cký souèin není obecnì komutativní. Napø., 2 ! a ! 2 nejsou isomorfní. Toti¾ ! 2 = !, zatímco 2 ! jsou dvì kopie ! nad sebou. Vìta 10.6. Pro libovolné uspoøádané mno¾iny A; B; C platí (A B ) C = A (B C ): Dùkaz. V (A B) C platí
(a; b; c) (a0 ; b0 ; c0) , (a; b) < (a0 b0 ) nebo (a; b) = (a0 ; b0 ); c c0 , a < a0 nebo a = a0 ; b < b0 nebo a = a0 ; b = b0 ; c < c0 : Podobnì, v A (B C )) platí (a; b; c) (a0 ; b0 ; c0) , a < a0 nebo a = a0 ; (b; c) (b0 ; c0 ) , a < a0 nebo a = a0 ; b < b0 nebo a = a0 ; b = b0 ; c < c0 :
Souèet (kardinální) disjunktních uspoøádaných mno¾in A; B mù¾eme de novat jako jejich sjednocení A [ B spolu s uspoøádáním, které na A, resp. B splývá se zadaným uspoøádáním a libovolné prvky a 2 A, b 2 B jsou nesrovnatelné. Takový souèet dvou lineárnì uspoøádaných mno¾in není lineárnì uspoøádaný. V teorii dobøe uspoøádáných mno¾in proto pracujeme s jiným (tzv. ordinálním) souètem. De nice. Souèet A + B dvou disjunktních dobøe uspoøádaných mno¾in de nujeme jako jejich sjednocení A [ B vybavené uspoøádáním
x y ,x; y 2 A; x y nebo x; y 2 B; x y nebo x 2 A; y 2 B: Souèet dobøe uspoøádaných mno¾in není komutativní. Napø., ! +1 není isomorfní s 1 + !. Toti¾, 1 + ! = !, zatímco ! + 1 není isomorfní s !. Vìta 10.7. Pro libovolné navzájem disjunktní dobøe uspoøádané mno¾iny A; B; C platí (A + B ) + C = A + (B + C ):
11
Dùkaz. V obou pøípadech platí
x y ,x; y 2 A; x y nebo x; y 2 B; x y nebo x; y 2 C; x y nebo x 2 A; y 2 B nebo x 2 A; y 2 C nebo x 2 B; y 2 C:
Budeme potøebovat i nekoneèné souèty. De nice. Buï I 6= ; uspoøádaná mno¾ina a A i , i 2 I po dvou disjunktní uspoøáS P dané mno¾iny. Souèet Ai de nujeme jako Ai spolu s uspoøádáním i 2I
i 2I
x y , existuje i 2 I tak, ¾e x; y 2 Ai ; x y nebo x 2 Ai ; y 2 Aj ; i < j:
VìtaP10.8. Buïte I 6= ; a Ai , i 2 I po dvou disjunktní dobøe uspoøádané mno¾iny.
Pak
i 2I
Ai je dobøe uspoøádaná.
S
Dùkaz. Mìjme ; 6= X Ai . Nech» I0 = fi 2 I nX \ Ai 6= ;g. Buï i0 nejmen¹í i 2I prvek v I0 a a0 nejmen¹í prvek v Ai0 \ X . Zøejmì a0 je nejmen¹í prvek v X . Vìta 10.9. (obecný asociativní zákon) Buï I 6= ; uspoøádaná mno¾ina, Ai , i 2 I P uspoøádané mno¾iny a I = Ij . Pak platí j 2J
XA = XXA i 2I
i
j 2J i2Ij
i
Dùkaz je zøejmý. Vìta 10.10. (pravý distributivní zákon) (
S
X A ) B = X( A B ) : i 2I
i
i 2I
i
S
P
Dùkaz. Pøedev¹ím platí (Ai B) = ( Ai ) B. Uspoøádání v ( Ai ) B je i 2I i 2I i 2I dáno následovnì:
(a; b) (c; d) ,a; c 2 Ai ; a < c nebo a 2 Ai ; c 2 Aj ; i < j nebo a = c; b d:
12
P
Uspoøádání v ( (Ai B) je dáno následovnì: i 2I
(a; b) (c; d) ,(a; b); (c; d) 2 Ai B; (a; b) (c; d) nebo (a; b) 2 Ai B; (c; d) 2 Aj B; i < j: To v¹ak nastane právì kdy¾ a; c 2 Ai; a < c nebo a = c; b d nebo a 2 Ai ; b 2 Aj ; i < j: Tím je tvrzení dokázáno. Levý distributivní zákon neplatí: ! (1 + 1) = ! 6= ! + ! = ! 1 + ! 1: Vìta 10.11. Buï I uspoøádaná mno¾ina a Ai = A po dvou disjunktní uspoøádané mno¾iny. Pak platí X A = I A: i i 2I
S
Dùkaz. Buïte fi : Ai ! A, i 2 I isomor smy. Pak zobrazení f : Ai ! I A Si2I dané pøedpisem f (a) = (i; fi (a)) pro a 2 Ai je bijekce. Pro a; b 2 Ai platí
ab v
X A ,a; b 2 A ; a b nebo i 2I
i
i 2I
i
a 2 Ai ; b 2 Aj ; i < j: To v¹ak nastane právì kdy¾ (i; fi (a)) (j; fj (b)) v I A. 11. Ordinální èísla
Ka¾dé dobøe uspoøádané mno¾inì A pøiøadíme symbol A tak, ¾e A = B, právì kdy¾ A = B. Symboly A se nazývají ordinální èísla. Ponìvad¾ relace "být isomorfní" je relací ekvivalence, postup je korektní. Není v¹ak veden v termínech teorie mno¾in, co¾ pozdìji opravíme. Pøíklad. Ordinální èíslo n-prvkové dobøe uspoøádané mno¾iny oznaèíme n. Ordinální èíslo dobøe uspoøádané mno¾iny ! znaèíme !. Polo¾íme A B, pokud A je isomorfní se zaèátkem B. Relace je zøejmì re exivní a tranzitivní. Z vìty 11.3. plyne, ¾e se jedná o lineární uspoøádání (na tøídì v¹ech ordinálních èísel). Právì uvedená formulace je korektní nebo» zøejmì nezávisí na volbì reprezentantù. Uspoøádání ordinálních èísel uvedených v pøíkladu nahoøe je 0 < 1 < :::n < :::! Pro libovolné ordinální èíslo polo¾íme W ( ) = f n < je ordinální èíslog Napøíklad, W (0) = ;, W (n) = f0; : : : ; n 1g a W (!) = f0; 1; : : : ; n; : : : g.
13
Vìta 11.1. Mno¾ina W ( ) je dobøe uspoøádaná pro libovolné ordinální èíslo a
platí W ( ) = . Dùkaz. Nech» = A. Polo¾me f (x) = A(x) pro libovolné x 2 A. Zøejmì f : A ! W ( ) je prosté zobrazení. Mìjme < , = B. Pak existuje x 2 A tak, ¾e B = A(x). Tedy = f (x), tak¾e f je isomor smus. Vìta 11.2. Ordinální èísla jsou dobøe uspoøádaná relací . Dùkaz. Buï Z 6= ; mno¾ina ordinálních èísel. Uva¾ujme 2 Z . Pak buï je nejmen¹í prvek v Z nebo mno¾ina W ( ) \ Z je neprázdná. Pak její nejmen¹í prvek (který existuje nebo» je ordinální èíslo) je zøejmì nejmen¹í prvek v Z . Ordinální èíslo se nazývá limitní, pokud mno¾ina W ( ) nemá nejvìt¹í prvek. V opaèném pøípadì se nazývá izolované. Tedy ordinální èíslo 0 je limitní. Operace s ordinálními èísly: Nech» = A a = B, pøièem¾ dobøe uspoøádané mno¾iny A; B jsou v (1) disjunktní. Polo¾me (1) + = A + B (2) = B A De nice je korektní nebo» operace zøejmì nezavisí na volbì dobøe uspoøádaných mno¾in A; B. Operace +; jsou asociativní, co¾ plyne z vìt 11.6. a 11.7. Z vìty 10.10. plyne platnost levého distributivního zákona
( + ) = + Dále platí
.
+0 = 0+ = 0=0 =0 1 = 1 = 2 = +
Operace +; nejsou komutativní. Napø. platí 1 + ! = ! 6= ! + 1
2 ! = ! 6= ! 2 = ! + ! V¹imnìme si faktu, ¾e izolovaná ordinální èísla jsou právì ordinální èísla tvaru + 1. Buï I dobøe uspoøádaná mno¾ina, Ai , i 2 I , dobøe uspoøádané mno¾iny a i = P Ai . Pak ordinální èíslo i2I i de nujeme pøedpisem
X = XA i 2I
i
i 2I
i
14
De nice zøejmì opìt nezávisí na volbì dobøe uspoøádaných mno¾in Ai . Z vìt 10.10. a 10.11. plyne X X i = i i 2I
i 2I
X = I i 2I
Tøídu v¹ech ordinálních èísel oznaèíme W . Symbol W ( ) je ve shodì s obecným oznaèením A(x) pro zaèátek. Ve W má nejen ka¾dá podmno¾ina, ale i ka¾dá podtøída Z W má nejmen¹í prvek (dùkaz je stejný). Vìta 11.3. Buï M mno¾ina ordinálních èísel. Pak existuje ordinální èíslo takové, ¾e < pro libovolné 2 M . Dùkaz. Pokud M = ;, pak = 0. Má-li M nejvìt¹í prvek , pak = +1. Pokud M nemá nejvìt¹í prvek, uva¾ujeme mno¾inu
A=
[ W ( )
2M
Ponìvad¾ A je dobøe uspoøádaná nmo¾ina, pro = A platí < pro v¹echna 2 M. Koneènì, pro libovolná ordinální èísla ; de nujeme mocninu následovnì:
0 = 1 +1 = = supf n < g pro 0 < limitní. (Zde je pou¾ito 11.3.) De nice je zalo¾ena na vìtì 11.4., t.j. na trans nitní indukci. Poznámka 11.4. Z vìty 11.3. plyne, ¾e W není mno¾ina a neobsahuje nejvìt¹í prvek. Dùsledek 11.5. Pro libovolnou mno¾inu M ordinálních èísel existuje sup M ve W. Dùkaz. Tvrzení je zøejmé, pokud M má nejvìt¹í prvek. Nech» M nemá nejvìt¹í prvek. Ordinální èíslo z 11.3. patøí do tøídy W M , která je proto neprázdná, tak¾e obsahuje nejmen¹í prvek. Ten je zøejmì sup M . Nyní si mù¾eme udìlat pøedstavu o zaèátku tøídy W ordinálních èísel (v jejím uspoøádání): 0; 1; 2; : : : ; n; : : : ; !; ! + 1; : : : ; ! + ! = ! !; : : : ; ! n; : : : ! ! = !2; : : : ; !n; : : : !! ; !
(! ! )! ; : : : ; !
!
o
n
; : : : 0
15
Pøitom ka¾dé limitní ordinální èíslo je v¾dy supremum v¹ech men¹ích ordinálních èísel. Toti¾, vztahy _ != n
!+! = jsou zøejmé. Rovnost
!! =
_ !+n
n
n
_ !n
n
plyne z toho, ¾e pro libovolné < ! ! existují m; n < ! tak, ¾e 2 W (m; n). Tedy < ! n. Koneènì rovnost _ !! = !n n
plyne z de nice mocniny ordinálních èísel. Èíslo 0 je supremum v¹ech pøedchozích ordinálních èísel. Je to nejmen¹í ordinální èíslo s vlastností !0 . V¹echna vý¹e uvedená ordinální èísla jsou spoèetná (t.j., jsou to ordinální èísla spoèetných dobøe uspoøádaných mno¾in). Nespoèetná ordinální èísla v¹ak musí existovat nebo» spoèetných ordinálních èísel není víc ne¾ v¹ech mo¾ných uspoøádání na mno¾inì !, t.j., nejvý¹e 2!! = 2! (a W není mno¾ina). Nejmen¹í nespoèetné ordinální èíslo se oznaèuje !1 . 12. Axiom výbìru
Q
Axiom výbìru: Buï I mno¾ina a Ai , i 2 I neprázdné mno¾iny. Pak mno¾ina Ai i 2I je rovnì¾ neprázdná. Axiom øíká, ¾e libovolná mno¾ina neprázdných mno¾in fAi ni 2 I g má tzv. výbìrovou funkci, t.j. zobrazení [ f : I ! Ai i 2I
takové, ¾e f (i) 2 Ai pro libovolné i 2 I . Axiom výbìru se oznaèuje AC. ZermeloFraenkelova teorie mno¾in s axiomem výbìru se oznaèuje ZFC a je to v souèasné dobì "standartní" teorie mno¾in. Pøíèinou zvlá¹tního postavení axiomu výbìru je jeho "nekonstruktivní" charakter. Zatímco v¹echny ostatní axiomy ZF pøesnì popisují, jakou mno¾inu vytváøí, AC pouze tvrdí, ¾e urèitá mno¾ina (t.j., výbìrová funkce) existuje, ani¾ by øekl, jak vypadá. Výbìrová funkce v¾dy existuje (bez AC), pokud mno¾ina I je koneèná, napø. I = f1; : : : ; ng. Staèí zvolit prvky ai 2 Ai pro i = 1; : : : ; n a polo¾it f = f(1; a1 ); : : : ; (n; an )g. Tato výbìrová funkce je vytvoøena pou¾itím axiomu dvojice. Takovou mo¾nost ji¾ nemáme pro nekoneènou mno¾inu I a to ani v pøípadì, pokud mno¾iny Ai jsou koneèné nebo dokonce dvouprvkové. Princip dobrého uspoøádání: Libovolnou mno¾inu lze dobøe uspoøádat. Tento princip má rovnì¾ "nekonstruktivní" charakter nebo» neøíká, jak pøíslu¹né dobré uspoøádání vypadá. Nahlédneme to napø. na existenci dobrého uspoøádání mno¾iny R reálných èísel. Uká¾eme, ¾e princip dobrého uspoøádání je (v ZF) ekvivalentní s axiomem výbìru.
16
Vìta 12.1. Princip dobrého uspoøádání implikuje axiom výbìru. Dùkaz. Buï I mno¾ina a ; = 6 Ai, i 2 I . Podle principu dobrého uspoøádání lze
[A
mno¾inu
i 2I
i
dobøe uspoøádat. V tomto dobrém uspoøádání, má libovolná mno¾ina Ai nejmen¹í prvek ai . Pak f (i) = ai de nuje výbìrovou funkci
f :I!
[A :
i 2I
i
Je pouèné si uvìdomit, ¾e dùkaz nelze vést následovnì: libovolná mno¾ina Ai lze dobøe uspoøádat, tak¾e má nejmen¹í prvek ai, atd. Toti¾ existuje celá mno¾ina Di dobrých uspoøádání mno¾iny Ai a k výbìru nìjakého z nich pro v¹echna i 2 I pou¾íváme axiom výbìru (pro mno¾iny Di , i 2 I ). Uká¾eme si dal¹í "skrytá" pou¾ití axiomu výbìru. Tato pou¾ití dokumentují, ¾e AC bì¾nì u¾íváme. Pøíklad 12.2. Známé tvrzení matematické analýzy øíká, ¾e funkce f : R ! R je spojitá v bodì a, právì, kdy¾ an ! a implikuje f (an ) ! f (a) pro libovolnou posloupnost (an ). Nutnost podmínky je zøejmá. Dostateènost se dokazuje následovnì. Nech» f není spojitá v a. Pak existuje okolí V bodu f (a) takové, ¾e pro libovolné 0 < n existuje an s vlastnostmi jan aj < n1 , f (an ) 2= V . Pak an ! a, ale neplatí f (an ) ! f (a). Pou¾itá posloupnost an je v¹ak výbìrová funkce N
!
[ fanja
n2N
n
aj < n1 ; f (an ) 2= V g
Lze ukázat, ¾e (bez urèité formy) AC tvrzení neplatí, t.j., ¾e "nemáme dost posloupností". Pøíklad 12.3. Doká¾eme, ¾e sjednocení spoèetné mno¾iny spoèetných mno¾in je spoèetná mno¾ina. Mìjme spoèetné mno¾iny Ai , i 2 !. Mno¾iny Ai lze tedy zapsat posloupnostmi Ai = fai0; ai1 ; : : : ; ain; : : : g
S
Uspoøádáme-li mno¾inu A = Ai po diagonálách A = fa00 ; a01 ; a10; : : : g, vidíme, i 2! ¾e mno¾ina A je spoèetná. Pou¾ití AC spoèívá ve výbìru uspoøádání mno¾in Ai do posloupností. Takových posloupností je v¾dy mno¾ina Di a na mno¾iny Di musíme opìt uplatnit AC. Princip maximality Buï A uspoøádaná mno¾ina taková, ¾e libovolný øetìzec v A má horní závoru. Pak ke ka¾dému a 2 A existuje maximální prvek b 2 A tak, ¾e a b.
17
Vìta 12.4. Princip maximality implikuje princip dobrého uspoøádání. Dùkaz. Buï A mno¾ina. Uva¾ujme mno¾inu
D = f(B; R)nR A A; R je dobré uspoøádání na B Ag Ponìvad¾ (;; ;) 2 D, platí máme D 6= ;. Pro (B1; R1 ); (B2 ; R2) 2 D polo¾íme (B1 ; R1) (B2; R2), pokud (B1 ; R1) je zaèátek (B2 ; R2). Zøejmì je uspoøádání mno¾iny D. Ovìøíme, ¾e D splòuje pøedpoklad principu maximality. Buï C D øetìzec. Pak [ R Q= B;R)2C
(
je lineární uspoøádání mno¾iny
Z=
[ B;R)2C
B
(
Uva¾ujme ; 6= X Z . Pro libovolné x 2 X existuje (B; R) 2 C tak, ¾e x 2 B. Zøejmì nejmen¹í prvek podmno¾iny X \ B je nejmen¹ím prvkem mno¾iny X . Tedy Q je dobré uspoøádání mno¾iny Z , tak¾e (Z; Q) 2 D. Zøejmì (Z; Q) je hledanou horní závorou øetìzce C v D. Podle principu maximality existuje maximální prvek (B; R) v D. Uká¾eme, ¾e pak B = A. V opaèném pøípadì existuje prvek a 2 A B a pro B0 = B [ fag a R0 = R [ (B fag) [ f(a; a)g platí (B0; R0) 2 D a zároveò (B; R) (B0; R0 ), co¾ není mo¾né. Vìta 12.5. Axiom výbìru implikuje princip maximality. Dùkaz. Buï A uspoøádaná mno¾ina taková, ¾e libovolný øetìzec v A má horní závoru a nech» a 2 A. Buï f výbìrová funkce na mno¾inì v¹ech neprázdných podmno¾in mno¾iny A. To znamená, ¾e f (X ) 2 X pro libovolné ; = 6 X A. Existuje dobøe uspoøádaná mno¾ina B taková, ¾e jBj jAj neplatí. V opaèném pøípadì by se W skládala z ordinálních èísel podmno¾in mno¾iny A, které lze dobøe uspoøádat. Ponìvad¾ dobrých uspoøádání podmno¾in mno¾iny A je pouze mno¾ina, dostali bychom spor s poznámkou 12.4. Trans nitní indukcí de nujme zobrazení g de nované na podmno¾inì C mno¾iny B tak, ¾e a je obrazem nejmen¹ího prvku mno¾iny B a
g(b) = f (fxng(y) < x pro v¹echna y < bg) Zobrazení g je zøejmì prosté. Ponìvad¾ jBj jAj neplatí, existuje b 2 B tak ¾e g není de nováno pro b. Buï b nejmen¹í prvek v B s touto vlastností. Pak existuje c 2 C tak ¾e c < b a neexistuje x 2 B, c < x < b. V opaèném pøípadì by obraz g byl øetìzec v A bez horní závory. Zøejmì g(c) je hledaný maximální prvek v A takový, ¾e a g(c).
18
13. Kardinální aritmetika
Vìta 13.1. (AC) Kardinální èísla jsou dobøe uspoøádaná relací .
Dùkaz. Libovolnému kardinálnímu èíslu pøiøadíme ordinální èíslo tak, ¾e
, Odsud ji¾ vyplyne tvrzení vìty nebo» ordinální èísla jsou dobøe uspoøádaná relací dle 13.2. Nech» = jAj. Buï M mno¾ina v¹ech ordinálních èísel takových, ¾e = (A; ) pro nìjaké dobré uspoøádání mno¾iny A. Z AC víme, ¾e M 6= ;, tak¾e M má nejmen¹í prvek, který oznaèíme . De nice zøejmì nezávisí na volbì mno¾iny A. Implikace ) je zøejmá. Nech» . Pak nebo . V druhém pøípadì platí , tak¾e = , tak¾e = . Pøedchozí vìta nám umo¾òuje indexovat nekoneèná kardinální èísla pomocí ordinálních èísel. Tøída kardinálních èísel pak (ve svém uspoøádání ) vypadá následovnì 0; 1; : : : ; n; : : : @0 ; @1 ; : : : ; @n; : : : @! ; : : : @ ; : : : Indexování provedeme následovnì. Ji¾ døíve jsme nejmen¹í nekoneèné kardinální èíslo oznaèili @0. Nyní @1 je nejmen¹í nespoèetné kardinální èíslo. Z 13.1. víme, ¾e takové kardinální èíslo existuje. Máme-li ji¾ sestrojena kardinální èísla @ pro v¹echna ordinální èísla < , pak @ je nejmen¹í kardinální èíslo vìt¹í ne¾ v¹echna @ pro < . Z 9.3. plyne, ¾e takové kardinální èíslo existuje. Ponìvad¾ pro libovolné kardinální èíslo @ existuje pouze mno¾ina kardinálních èísel men¹ích ne¾ @, @ = @ pro nìjaké ordinální èíslo . Tímto postupem jsme vlastnì sestrojili bijekci mezi ordinálními èísly a nekoneènými kardinálními èísly. V dùkazu vìtu 13.1. jsme libovolnému kardinálnímu èíslu pøiøadili ordinální èíslo a sice nejmen¹í ordinální èíslo mohutnosti . Budeme znaèit
@ = ! Tøídu W ordinálních èísel si pak mù¾eme pøedstavit následovnì 0; 1; : : : ; n; : : : !0; : : : 0; : : : !1; : : : ! ; : : : (srv. s kapitolou 12; ! = !0). Vìta 13.2. Axiom výbìru je ekvivalentní s tím, ¾e kardinální èísla jsou lineárnì uspoøádaná relací . Dùkaz. Implikace ) plyne z 13.1. Pøedpokládejme, ¾e kardinální èísla jsou lineárnì uspoøádaná relací . Uká¾eme, ¾e pak libovolnou mno¾inu lze dobøe uspoøádat, co¾ implikuje AC.
19
Buï A mno¾ina. Z dùkazu vìty 13.5. víme, ¾e existuje dobøe uspoøádaná mno¾ina B taková, ¾e jBj jAj neplatí. Tedy jAj < jBj nebo» pøedpokládáme, ¾e kardinální èísla jsou lineárnì uspoøádána relací . Tedy existuje prosté zobrazení f : A ! B, které nám umo¾ní de novat dobré uspoøádání mno¾iny A:
a b , f (a) f (b):
Poznámka 13.3. Byli jsme si vìdomi toho, ¾e ani kardinální, ani ordinální èísla jsme nezavedli v termínech teorie mno¾in. Za AC lze kardinální èísla zavést pomocí ordinálních èísel. Tím myslíme de novat @ jako ! , t.j., za kardinální èíslo pøímo pova¾ovat nejmen¹í ordinální èíslo dané mohutnosti. Nyní naznaèíme, jak lze v termínech ZF de novat ordinální èísla. Idea spoèívá v "kanonické volbì" dobøe uspoøádané mno¾iny A takové, ¾e A = . Touto volbou bude W ( ). Máme-li
= W ( ) pak
< , 2 t.j., je mno¾ina v¹ech men¹ích ordinálních èísel. Zejména to znamená, ¾e je dobøe uspoøádané relací 2. De nice ordinálního èísla jako mno¾iny dobøe uspoøádané relací 2 by v¹ak je¹tì nebyla v poøádku. Takovou je i mno¾ina ff;gg, kterou za ordinální èíslo nechceme nebo» ordinálním èíslem jednoprvkové mno¾iny je f;g. Mno¾ina ff;gg v¹ak není tranzitivní ve smyslu x2X)xX Ordinální èísla tranzitivní jsou. De nice ordinálního èísla v ZF tedy zní: ordinální èíslo je tranzitivní mno¾ina dobøe uspoøádaná relací 2. Vìta 13.4. (AC) Pro libovolné nekoneèné kardinální èíslo @ platí
@@=@ Dùkaz. Ji¾ víme, ¾e za AC jsou kardinální èísla právì @ , kde 2 W . Trans nitní indukcí budeme tedy dokazovat, ¾e
@ @ = @ Pro = 0 tvrzení platí (viz 13.5). Pøedpokládejme, ¾e 0 < a ¾e tvrzení platí pro v¹echna < . Doká¾eme, ¾e tvrzení platí pro . Tím bude dùkaz ukonèen. Na mno¾inì W (! ) W (! ) budeme uva¾ovat tzv. maximo-lexikogra cké uspoøádání. Je de nováno tak, ¾e ( ; ) < (; ), právì kdy¾ maxf ; g < maxf; g nebo
maxf ; g = maxf; g a <
20
nebo
maxf ; g = maxf; g; = a < Zøejmì se jedná o dobré uspoøádání. Oznaème
= W (! ) W (! ) tak¾e
W (! ) W (! ) = W ( ) Staèí, kdy¾ doká¾eme, ¾e platí = ! . Pak toti¾ bude platit
@ @ = jW (! ) W (! )j = jW (! )j = @ Pøedev¹ím platí ! nebo» jW (! )j jW (! ) W (! )j = jW ()j a ! je nejmen¹í ordinální èíslo mohutnosti @ . Pøedpokládejme, ¾e ! < . Pak existují ordinální èísla ; < ! tak, ¾e
W (! ) = W (( ; ))
(druhý výraz zde oznaèuje zaèátek urèený dvojicí ( ; ) v W (! )W (! )). Polo¾me
= maxf ; g + 1 Zøejmì < ! . Z de nice maximo-lexikogra ckého uspoøádání plyne, ¾e
W (( ; )) W () W () tedy
jW (! )j = jW (( ; ))j jW () W ()j = jW ()j
(poslední rovnost plyne z indukèního pøedpokladu). Ponìvad¾ < ! , platí
jW (! )j jW ()j < jW (! )j Dostáváme spor a dùkaz je tím ukonèen. Dùsledek 13.5. (AC) Pro libovolná ordinální èísla ; platí
@ @ = maxf@ ; @ g Dùkaz. Nech» napøíklad . Pak platí
@ = 1 @ @ @ @ @ = @ tak¾e @ @ = @ .
21
Dùsledek 13.6. (AC) Pro libovolná ordinální èísla ; platí @ + @ = maxf@ ; @ g Dùkaz. Nech» napøíklad . Pak platí @ @ + @ = 2 @ = @ Dùsledek 13.7. (AC) Pro libovolná ordinální èísla platí @@ = 2@ Dùkaz. Platí
2@ @@ (2@ )@ = 2@ @ = 2@
Zobecnìná hypotéza kontinua øíká, ¾e 2@ = @ +1: Toto tvrzení je nezávislé na ZFC. Dùsledek 13.8. (AC) Buïte I , Ai , i 2 I mno¾iny takové, ¾e jI j; jAi j @ pro v¹echna i 2 I . Pak platí [
j A i j @
Dùkaz. Platí
i 2I
j
[ A j j X W (! )j = jI W (! )j = jI j @
i 2I
i
i 2I
@
(zde jsme pou¾ili 13.11.) Poznámka 13.9.. Zejména, za AC platí, ¾e sjednocení spoèetnì mnoha spoèetných mno¾in je spoèetná mno¾ina. De nice 13.10. Kardinální èíslo @ se nazývá regulární, jestli¾e sjednocení < @ mno¾in mohutnosti < @ má mohutnost < @ . V opaèném pøípadì se @ nazývá singulární. Pøíkladem regulárního kardinálního èísla je @0 . Dùsledek 13.11. (AC) Pro libovolné ordinální èíslo je kardinální èíslo @ + 1 regulární. Dùkaz. Plyne z 13.11. a z toho, ¾e jX j < @ + 1 , jX j @
Nespoèetné kardinální èíslo @ se nazývá (slabì) nedosa¾itelné, je-li regulární a zároveò je limitní. Nazývá se nedosa¾itelné, je-li regulární a platí @ < @ ) 2@ < @ Libovolné nedosa¾itelné kardinální èíslo je zøejmì slabì nedosa¾itelné. Za zobecnìné hypotézy kontinua oba pojmy splynou. Existenci nedosa¾itelného kardinálního èísla nelze dokázat z axiomù ZFC.
