LOGIKA A TEORIE MNOŽIN 6. Ordinální čísla O izomorfních uspořádaných množinách říkáme, že mají stejný ordinální typ. Ordinální čísla můžeme definovat jako ordinální typy dobře uspořádaných množin. Znamená to, že dvě ordinální čísla jsou si rovna, právě když jsou ordinálními typy izomorfních dobře uspořádaných množin. Pro ordinální typy zavedeme zvláštní symboly. Podobným způsobem jsme zavedli kardinální čísla, jen místo bijekcí mezi množinami rozhodují izomorfismy dobře uspořádaných množin. Izomorfismus uspořádaných množin je bijekce, a proto mají izomorfní uspořádané množiny stejnou mohutnost. Odtud plyne, že každé ordinální číslo má určitou mohutnost, přičemž může existovat více různých ordinálních čísel stejné mohutnosti. Podobně jako u mohutností taková definice neumožňuje utvořit třídu ordinálních čísel. To nám dovolí až von Neumannova definice ordinálních čísel čili ordinálů, kterou uvedeme později. Není tak názorná jako definice pomocí ordinálních typů. Příklady. 1. Každé přirozené číslo n označuje rovněž ordinální typ řetězce o n prvcích (již víme, že je dobře uspořádaný). Jeho diagram sestává z n bodů spojených úsečkami, např. 1, 2, 3 mají po řadě diagramy o , o—o , o—o—o . 2. Symbolem w se označuje ordinální typ množiny všech přirozených čísel uspořádaných podle velikosti (rovněž dobře uspořádaná množina). Výše jsme uvedli její diagram o—o—o—o--■ ■. Jinou názornou ilustrací čísla w je nekonečná řada objektů lili. táhnoucích se k obzoru. 6.1. Aritmetika ordinálních čísel Podobně jako kardinální čísla, lze i ordinální čísla sečítat, násobit a umocňovat. Operace sčítání a násobení definujeme podobně jako stejnojmenné operace s kardinálními čísly, pouze je potřeba zařídit, aby disjunktní sjednocení a součiny dobře uspořádaných množin byly dobře uspořádané množiny. (Podobný postup není možný v případě umocňování.) Upozorněme též, že operace s ordinálními čísly nejsou komutativní. 6.2. Sčítání ordinálních čísel 6.1. Definice. Buďte A, B dvě dobře uspořádané množiny. Množina ({0} x Ä) U ({1} x B) s uspořádáním daným formulí (i, a) <(j,b) & i? Máme 0 U o—o--■ ■ = | o |—| o—o— ■ ■ ■ | = o—o— ■ ■ ■ = u) neboli 1 + lllk lllk Tudíž, 1 + w = w. Podobně 2 + w = w, atd. Příklad. Kolik je w + 1? Máme o—o--■ ■ U o = | o—o— ■ ■ ■ |—| o | = o—o— ■ ■ ■ o. neboli ik l lllkl Vidíme, že w + 1 7^ w. Vskutku, v u je jediný prvek, 0, který nemá přechůdce, kdežto v w + 1 jsou takové prvky dva. Podobně w + 2 7^ w + 1 (proč?), atd. Příklad. Kolik je w + u>7 Máme o—o--■ ■ U o—o--■ ■ = o—o- ÍYa^EEE = o—o— ■ ■ ■ o—o- neboli lilu. llliJllk Vidíme, že w + u> je další ordinální číslo, různé od již sestrojených. Podobně u) + u) + l, w + u> + u> jsou po řadě \\k \\k I lllk lllk lllk další nová ordinální čísla. 44 LOGIKA A TEORIE MNOŽIN Shora uvedené příklady ukazují, že na rozdíl od sčítání kardinálních čísel není sčítání or-dinálních čísel komutativní. Například 1+lu = lu=/=lu + 1. Nicméně, sčítání ordinálních čísel je asociativní (ověřte jako cvičení). Vyplatí se rovnou zavést i zobecnění na systémy. Dobře uspořádaný systém dobře uspořádaných množin je systém {Aí}í<=i, kde jednotliví sčítanci Ai i indexová množina I jsou dobře uspořádáni. Disjunktní sjednocení \jAi = \J({i}xAi) iei iei uspořádáme podle předpisu (i, a,i) < (j, a,j) i < j V (i = j A at < a,j) (zde a>i (z Ai & o-j G Aj). Opět platí, že prvky disjunktního sjednocení uspořádáváme 1. podle prvních složek, přičemž přebíráme uspořádání z /; 2. v případě rovnosti podle druhých složek, přičemž použijeme uspořádání z té množiny, kde se oba prvky nacházejí. Schematicky Ai± Ai2 Ai3 přičemž jednotlivé "bloky" jsou uspořádány stejně jako jejich indexy v množině /. Je zřejmé, že dříve zavedené disjunktní sjednocení dvou množin je speciální případ, kdy indexovou množinou je řetězec 0—1. Zobecnění na n-prvkový řetězec je zřejmé — obdržíme součet n množin. 6.3. Tvrzení. Disjunktní sjednocení dobře uspořádaného systému dobře uspořádaných množin je dobře uspořádaná množina. Důkaz. Buď_B neprázdná podmnožina v disjunktním sjednocení \_\ieI Ai. NechťIg je množina všech indexů i takových, že B D Ai =/= 0. Zřejmě je Ib ^ 0 neprázdná (proč?) podmnožina v dobře uspořádané množině /, takže má nejmenší prvek, což je podle definice nejmenší index i takový, že BnAi =/= 0. Pak je ovšem BnAi neprázdná podmnožina dobře uspořádané množiny Ai, takže má nejmenší prvek, který je současně nejmenším prvkem podmnožiny B (proč?). 6.4. Definice. Buďte ordinální typy dobře uspořádaných množin Ai,i E I, kde / je dobře uspořádaná. Součet ^ieIcii definujeme jako ordinální typ disjunktního sjednocení |_liej^4i. Příklad. Máme jak je snadno vidět z diagramu | o |—| o—o |—| o—o—o |--■ ■ 45 LOGIKA A TEORIE MNOŽIN 6.3. Násobení ordinálních čísel Jako další operaci zavedeme násobení, přičemž se ukáže, že v případě dvou operandů jde o speciální případ sčítání systému ordinálních čísel. 6.5. Definice. Buďte A, B dvě dobře uspořádané množiny. Množina A x B s uspořádáním daným formulí (a, b) < (a', b') ^ a < a' V (a = a' Ab < b') se nazývá lexikografický součin dobře uspořádaných množin nebo jen součin dobře uspořádaných množin A, B a, značí se A x B. Slovy: Prvky součinu uspořádáme 1. podle prvních složek, 2. v případě rovnosti podle druhých složek. Původ přívlastku "lexikografický" nalezneme ve slovníkovém uspořádání dvoupísmenných slov. Je to dobře patrné v níže uvedených příkladech. Jinak: A krát B znamená, že prvky množiny A nahradíme kopiemi mnžiny B; v rámci jedné a téže kopie přebíráme uspořádání z B, zatímco mezi různými kopiemi přebíráme uspořádání z A. Schematicky B B B A Z definic je patrné, že součin A x B není nic jiného, než disjunktní součet A x B = \_\B A systému sestávajícího z kopií množiny B, po jedné pro každý prvek z A, a proto je dobře uspořádaný. Příklad. Počítejme 3x3. Máme r [o, o] [o, i] [o, 2]} 3x3=([l,0] [1,1] [1,2] i l [2, 0] [2,1] [2, 2] J s lexikografickým uspořádáním [0, 0] < [0,1] < [0, 2] < [1, 0] < [1,1] < [1, 2] < [2, 0] < [2, 1] < [2, 2]. Vidíme, že zároveň jde o disjunktní sjednocení [0,0]—[0,1]—[0,2] - [1,0]—[1,1]—[1,2] - [2,0]—[2,1]—[2,2] Jelikož součin dvou dobře uspořádaných množin je speciálním případem součtu systému množin, je dobře uspořádán. Můžeme pak pro ordinální čísla a, [3, která jsou po řadě or-dinálními typy množin A,B, definovat součin a/3 = a x [3 jako ordinální typ množiny A x B. Cislo a se nazývá násobitel (multiplicator), čislo [3 násobenec (multiplicandus). Jelikož násobení není obecně komutativní, na pořadí záleží. Pro zapamatování: Při zápisu "x" násobíme v pořadí "kolikrát co," to jest, a x [3 má význam "akrát Obvyklejší je zápis součinu v převráceném pořadí jako [3 ■ a = a x [3, což znamená, že násobíme v pořadí "co kolikrát," to jest, a ■ [3 má význam ua /3krát." Důvody pro převrácený zápis uvedeme v souvislosti s umocňováním níže. 46 LOGIKA A TEORIE MNOŽIN Pro zachování historické pravdy uveďme, že G. Cantor původně zavedl součin ekvivalentní součinu "'x" [v práci Ueber unendliche, lineare Punktniannichfaltigkeiten, Mathematische Annalen 21 (1883) 545-591 na str. 551], ale později přešel k převrácenému součinu. Příklad. Kolik je 2 x u> = |J2 uj! Dostáváme I o—o— • • ■ I—I o—o— ■ ■ ■ I což je w + u) neboli lllk líh.. Pro srovnání, ui x 2 = 2 je | o—o |—| o—o |—| o—o |--■ ■ čili o—o—o—o— ■ ■ ■ , což je w. Vidíme, že 2 x lj ^ tu = tu x 2. Příklad. Kolik je oj x uj — u? Dostáváme | o—o— ■ ■ ■ |—| o—o— ■ ■ ■ |—| o—o— ■ ■ ■ |--■ ■ čili o—o— ■ ■ ■ o—o— ■ ■ ■ o—o—...... nebo názorněji lili, llk. Ih, Může se psát i jako mocnina ur (viz níže). 47