LOGIKA A TEORIE MNOŽIN
5. Dobře uspořádané množiny a ordinální čísla
Na předchozích stránkách jsme došli k jisté představě o kardinálních číslech (mohutnostech množin), které je ovšem prozatím značně děravá. O nekonečných mohutnostech hodnověrně víme jen tolik, že existuje vzrůstající řada nekonečných mohutností, ale nevíme skoro nic o ostatních mohutnostech.
Nejlepší znalosti máme o spočetných množinách, kde funguje metoda matematická indukce. Metodu lze snadno zobecnit na obecnější dobře uspořádané množiny. Zobecnění se nazývá transfinitní indukce.
Zatímco kardinální čísla zobecňují přirozená čísla ve smyslu množství, ordinální čísla zobecňují přirozená čísla ve smyslu seřazení. Pokračování za konečná čísla je ovšem rozdílné. Na jedno nekonečné kardinální číslo připadá nekonečně mnoho ordinálních čísel. Například, zatímco existuje jen jedna spočetná mohutnost H0, spočetných ordinálních čísel je nekonečně mnoho a dokonce nespočetně mnoho (přesně Hi). A že paradoxů není nikdy dost, uvidíme, že mezi kardinálními čísly a ordinálními čísly existuje bijekce.
5.1. Uspořádání
Nejdříve připomeneme pojmy týkající se obecných relací uspořádání.
5.1. Definice. Řekneme, že relace < na třídě A je antisymetrická, jestliže platí implikace (a<bAb<a)^a = b pro všechna a, b e A.
Reflexivní, antisymetrická a tranzitivní relace se nazývá uspořádání
Je-li < uspořádání na třídě A, pak > definovaná předpisem a > b <ř=> b < a je rovněž uspořádání na třídě A.
Je-li < uspořádání na třídě A, pak relace < definovaná předpisem a<b<^(a<bAa=/=b) se nazývá ostré uspořádání Podobně >.
Třída spolu se zadaným uspořádáním se nazývá uspořádaná třída. Množina spolu se zadaným uspořádáním se nazývá uspořádaná množina.
Každá podtřída B q A uspořádané třídy A je uspořádaná třída, definujeme-li indukované uspořádání na B formulí <b = <a h (B x B), to jest, klademe-li a <b b <ř=> a <a b pro a, b (z B. Podobně pro ostré uspořádání.
Příklad. Inkluze c je uspořádání na univerzální třídě U a každé její podtřídě. Ostrá inkluze c je ostré uspořádání na univerzální třídě U a každé její podtřídě.
Příklad.   Množiny N, Z, Q, K jsou uspořádány obvyklým způsobem "podle velikosti." Příklad.   Prázdná relace 0 x 0 na prázdné množině je ostré i neostré uspořádání.
5.2. Definice. Buď A uspořádaná třída. Prvek m e A se nazývá největší prvek resp. nejmenší prvek, jestliže
(Va G A) a < to   resp.    (Va G A) to < a.
Prvek m e A se nazývá maximální prvek resp. minimální prvek, jestliže
(Va G A) (to < a =>• to = a)    resp.    (Va G A) (a < to     to = a).
Příklad.   Univerzální třída IÁ má nejmenší prvek 0 a nemá žádný největší prvek. Cvičení.   Uspořádaná třída má nejvýše jeden největší a nejvýše jeden nejmenší prvek.
39
LOGIKA A TEORIE MNOŽIN
Cvičení. Největší prvek uspořádané třídy je jediným maximálním prvkem této třídy. Nejmenší prvek uspořádané třídy je jediným minimálním prvkem této třídy.
Cvičení. Uvedte příklad uspořádané množiny, která má jediný maximální prvek a žádný největší prvek.
Návod. Množina je nutně nekonečná.
5.3. Definice. Bud X uspořádaná třída, A C X její podtřída. Prvek m G X se nazývá horní závora resp. dolní závora podtřídy A, jestliže
(Va G A) a < m   resp.    (Va G A) m < a.
Existuje-li nejmenší horní závora, nazývá se supremum a značí se sup A. Existuje-li největší dolní závora, nazývá se infimum a značí se inf A.
Cvičení. Každá množina A C U (tj. množina množin) má supremum i infimum vzhledem k uspořádání inkluzí a platí sup A = |J A a inf A = f] A.
5.2. Řetězce
5.4. Definice. Prvky a, b uspořádané množiny se nazývají srovnatelné, jestliže platí
(a < b) v 0 < a).
Uspořádání < na třídě A je úplné, jestliže jsou každé dva prvky třídy A srovnatelné. Třída spolu s úplným uspořádáním se nazývá úplné uspořádaná třída. Úplně uspořádaná množina se nazývá řetězec.
Příklad.   Množina reálných čísel s obvyklým upořádáním je řetězec.
Podmnožina řetězce s indukovaným uspořádáním je opět řetězec (protože nemá nesrovnatelné prvky) a nazývá se podřetězec.
Příklad. Intervaly I(a, fe), I(a,b], I[a,b), I[a,b] jakož i množiny N, Z, Q tvoří podřetězce v řetězci reálných čísel.
Příklad.   Uspořádání třídy IÁ inkluzí není úplné. Množiny {a} a {&}, kde a ^ b, jsou nesrovnatelné.
Buď M řetězec, budte m, n G M dva prvky takové, že m < n a neexistuje p G M takové, že m < p < n. Pak řekneme, že prvek n je následovník prvku m, resp., že prvek m je předchůdce prvku n a zapisujeme m <o n nebo n o> m.
Cvičení. Ukažte, že každý prvek a £ M má nejvýše jednoho předchůdce a nejvýše jednoho následovníka .
40
LOGIKA A TEORIE MNOŽIN
5.3. Dobré uspořádání
5.5. Definice. Řekneme, že uspořádaná třída T je dobře uspořádaná, jestliže každá neprázdná podtřída A d T obsahuje nejmenší prvek.
5.6. Tvrzení. Každá dobře uspořádaná třída je úplně uspořádaná.
Důkaz. Připusťme, že existují nesrovnatelné prvky a, b. Pak množina {a, b} nemá nejmenší prvek.
Příklad.   Každý konečný řetězec je dobře uspořádaný.
Příklady.    1. Množiny Z, Q, K nejsou dobře uspořádané, neboť neobsahují nejmenší prvek.
2. Polouzavřený interval I[0,1) není dobře uspořádaná množina, protože jeho podmnožina 1(0,1) neobsahuje nejmenší prvek.
5.7. Tvrzení. Množina přirozených čísel je dobře uspořádaná.
Důkaz. Buď A c N neprázdná podmnožina, buď a e A libovolný prvek. Prvky větší než a nemají vliv na existenci nejmenšího prvku, prvky menší nebo rovné a zase tvoří neprázdný konečný řetězec, který má nejmenší prvek.
Připomeňme, že prvek b uspořádané množiny je následovníkem prvku a, jestliže a < b a neexistuje c takové, že a < c < b.
5.8. Tvrzení. Každý prvek dobře uspořádané třídy, s výjimkou největšího, má následovníka.
Důkaz. Buď X dobře uspořádaná třída, buď a G X libovolný prvek, který není největším prvkem v X. Nechť B = {x G X \ a < x}. Kdyby byla třída B prázdná, bylo by x > a pro všechny prvky x G X (protože X je úplně uspořádaná) a a by byl největším prvkem v X, což podle předpokladu není. Tudíž, B je naprázdná a podle předpokladu má nejmenší prvek. Označme jej b. Evidentně a < b. Ukažme, že b je následovník prvku a. Připusťme opak, tedy že existuje prvek c takový, že a < c < b. Pak c G S, a tedy nutně b < c, což je spor.
Dobře uspořádanou množinu můžeme znázornit diagramem, v němž jsou prvky seřazeny zleva doprava od menších k větším a každý prvek je spojen úsečkou se svým následovníkem.
Příklady.    Pětiprvkový řetězec má diagram
o—o—o—o—o.
Množina přirozených čísel má diagram
o—o—o—o— ■ ■ ■ ,
kde tři tečky znamenají spočetné opakování vzoru o—.
Cvičení. Ukažte, že v dobře uspořádané množině nemůže existovat nekonečná ostře klesající posloupnost prvků ■ ■ ■ < (22 < ffli < do-
41
LOGIKA A TEORIE MNOŽIN
5.4. Transfinitní indukce
Princip transfinitní indukce umožňuje dokazovat tvrzení tvaru
(Vx g x)4>{x),
kde X je dobře uspořádaná třída. Indukční krok spočívá v důkazu, že z pravdivosti 4>(x) pro všechna x < a plyne pravdivost 4>(a).
5.9. Tvrzení. Buď 4>(x) formule, buď X dobře uspořádaná třída. Nechť pro všechna a G X podmínka (Vx < a) 4>(x) implikuje 4>{a). Pak je 4>(x) pravdivá pro všechna x G X.
Důkaz. Buď A Q X podtřída, tvořená prvky x, pro něž 4>(x) neplatí. Připusťme, že A =/= 0. Pak existuje nejmenší prvek a e A, což je nejmenší prvek, pro něž cp neplatí. Pro všechny prvky x < a (pokud existují) potom 4>(x) platí, takže, podle předpokladu, platí i 4>{a), což je ve sporu s a e A. Tudíž, A = 0, a tedy 4>(x) platí pro všechna x G X.
Může se zdát, že 4>(x) nemusí platit pro nejmenší prvek a třídy X. Opak je pravdou, neboť třída {x G X \ x < a} je v tomto případě prázdná, a proto je podmínka (Vx < a) 4>(x) splněna.
Princip transfinitní indukce také umožňuje konstruovat množiny Fx závislé na prvku dobře uspořádané třídy X. K tomu stačí dokazovat formule tvaru
(VxGX)(3F, eU)<P(x,Fx).
V tom případě hovoříme o transfinitně rekurzívní konstrukci tříd Fx.
5.5. Izotonní zobrazení a izomorfismy
5.10. Definice. Zobrazení / : X —> Y mezi uspořádanými třídami se nazývá izotonní, jestliže platí implikace a < b =>• /(a) < f(b) pro libovolná a, b G X.
Zobrazení / : X —> Y mezi uspořádanými třídami se nazývá ostře izotonní, jestliže platí implikace a < b =>• /(a) < f(b) pro libovolná a, b G X.
Příklad. Identické zobrazení idx ■ X —> X je izotonní i ostře izotonní při jakémkoliv uspořádání na X. Konstantní zobrazení X —> 1 (všichni na jednoho) je izotonní, ale nikoliv ostře izotonní, má-li X více než jeden prvek.
Cvičení.   Nechť je injektivní zobrazení izotonní. Ukažte, že je potom ostře izotonní.
Je-li bijektivní zobrazení izotonní, neznamená to ještě, že i inverzní zobrazení je izotonní. Nejjednodušším protipříkladem je zobrazení dvouprvkové množiny sestáváající ze dvou nesrovnatelných prvků na dvouprvkový řetězec.
5.11. Definice. Bijektivní zobrazení / : X —> Y mezi uspořádanými třídami se nazývá izomorfismus, jsou-li / i /_1 izotonní. Říkáme, že uspořádané třídy X, Y jsou izomorfní, pokud mezi nimi existuje izomorfismus. Zapisujeme X = Y.
Cvičení.   Každý izomorfismus X —> Y je ostře izotonní zobrazení.
5.12. Tvrzení. Každé bijektivní izotonní zobrazeníX —> Y, kde třída X je řetězec, je izomorfismus.
Důkaz. Nechť /(a) < f(b). Protože X je úplně uspořádaná, platí a < b nebo a = b nebo b < a. Druhá možnost odporuje injektivitě, třetí odporuje izotónnosti a zbývá jen první, tedy a < b.
42