O číslech, část 10: Čísla ordinální a rostoucí hierarchie

Kapitola předchozí nám ukázala, že není zase tak velký nesmysl pracovat s nějakým číslem ω, které je větší než všechna přirozená čísla, a tím by nám vznikla i čísla jako ω + 1 nebo 2ω. To je sice hezké, ale jak bychom takového čísla mohli opravdu dosáhnout z toho, co máme? Musíme se vydat do nekonečna a ještě dál!

Jako tomu bylo už v několika předchozích článcích, i zde se musíme vrátit na samotný začátek našeho matematického putování, k přirozeným číslům. Jich se budeme po zbytek této kapitoly držet, protože koneckonců jenom díky modelům aritmetiky přirozených čísel jsme objevili číslo ω. Tenkrát jsem uváděl množinový způsob konstrukce přirozených čísel, tedy že prázdná množina ∅ = 0; {∅} = 1; {0, 1} = {∅, {∅}} = 2; {0, 1, 2} = {∅, {∅}, {∅, {∅}}} = 3 a tak dále. Můžeme pozorovat, že každé přirozené číslo vlastně identifikujeme s množinou všech menších přirozených čísel, a tak to jde až do nekonečna.

Když víme, že číslo je vlastně množina čísel, proč bychom nemohli postupovat i obráceně, tedy že by množina čísel mohla být číslo? V principu bychom se o něco takového mohli pokusit, ale musíme si stanovit nějaká omezení: předně odebrání čísel z již vytvořeného čísla by nemělo vést k vytvoření něčeho nového, protože to bychom mohli už mezi přirozenými čísly najít hromadu nových množin. Ne, raději zůstaňme u té podoby množin, které jsme viděli doposud, tedy že pokud množina obsahuje nějaké číslo, musí obsahovat i všechna čísla menší.

První nová množina, která toto pravidlo splňuje, je ℕ = {0, 1, 2, 3, 4, …}, všechna přirozená čísla a zároveň sjednocení všech přirozených čísel. Dále bychom mohli jistě najít i ℕ ∪ {ℕ} nebo ℕ ∪ {ℕ, ℕ ∪ {ℕ}} a vlastně úplně stejným způsobem bychom mohli hledat následovníky dalších takových množin. Už minule jsme ukázali, že existence čísla ω nevede sama o sobě k žádným sporům, a nyní už máme i způsob, jak ho zkonstruovat: ω = ℕ. Další čísla se konstruují stejně jako přirozená, tedy ω + 1 = ℕ ∪ {ℕ} atd.

Pokud budeme pracovat s množinou všech přirozených čísel jako s číslem, k čemu by nám takové číslo bylo? Čísla obvykle potřebujeme k popisu nějakých veličin, a v tomto případě to je nejinak ‒ přirozená čísla jsme mohli použít k popisu pořadí; máme-li například ve frontě 5 stojících lidí, můžeme říct, že první z nich stojí na pozici 0, další na pozici 1 atd. Co kdyby ovšem takováhle fronta lidí byla nekonečná? Každému z nich by se dalo přiřadit nějaké přirozené číslo, ale co kdyby přišel další člověk a zařadil se za všechny předchozí? Nebuďme vázáni reálným konečným prostorem a časem; takový hypotetický člověk by, pokud by existoval, musel mít taky pořadí, a to by bylo právě číslo ω (a další za ním by měl ω + 1 atd.). Pořadí je latinsky ordo a proto tato čísla, v tomto kontextu, budeme nazývat ordinální.

Ordinální čísla slouží pro popis množin, které jsou nějakým způsobem uspořádané. Podobně jako onu frontu lidí bychom chtěli popsat stejným způsobem i frontu stromů, cihel, hvězd nebo čísel; chceme tedy sdružit všechny množiny (přesněji množiny vybavené nějakým pořadím) podle nějaké ekvivalence, jako jsme to už dříve dělali. Pro tuto konkrétní ekvivalenci potřebujeme izomorfismus vzhledem k pořadí, tedy můžeme nahradit všechny prvky množiny za jiné a změnit způsob, jakým je uspořádáme, ale jejich vzájemné pořadí se tím nijak nezmění. Tak například všechna přirozená čísla a všechna sudá přirozená čísla jsou takto ekvivalentní, neboť vynásobení nebo vydělení 2 nijak neovlivní jejich pořadí. Stejně tak libovolný interval reálných čísel je ekvivalentní s jakýmkoliv jiným intervalem reálných čísel, pokud jsou oba stejného typu, i pokud zaměníme ≤ za ≥ (můžeme prohodit konce intervalů). Jelikož se jedná o izomorfismus, je jasné, že mezi danými množinami musí existovat bijekce, tedy musí být stejně velké.

Takto ekvivalentní množiny mají společné něco, čemu budu říkat ordinalita (anglicky order type, typ pořadí). Množiny se stejnou ordinalitou náleží do společné třídy ekvivalence, takže samotnou třídu ekvivalence dané množiny bych mohl chápat jako její ordinalitu, ale možná by bylo dobré snažit se najít nějakého dobrého reprezentanta takové třídy ekvivalence, tedy nějakou prototypální množinu se stejnou ordinalitou.

Každé ordinální číslo je uspořádané a ve skutečnosti tento typ uspořádání má speciální název: dobré uspořádání. Dobře uspořádaná množina je lineárně uspořádaná (podobně jako např. celá, racionální nebo reálná čísla), ale zároveň má jednu důležitou vlastnost: každá neprázdná podmnožina takové množiny má nejmenší prvek. To evidentně nesplňují už celá čísla (záporná čísla nemají minimum) a tím pádem ani racionální nebo reálná čísla, i kdybychom je zdola omezili (zdola otevřené intervaly taky nemají minimum). Přestože i u těchto množin dává smysl hovořit o ordinalitě, nadále se omezíme pouze na dobře uspořádané množiny.

Každé ordinální číslo je jako množina dobře uspořádané, protože každé ordinální číslo má konečné množství přímých předchůdců (žádné, pokud se jedná o limitní ordinál jako ω nebo ω + ω). Jedná se tedy o jakési rozšíření přirozených čísel, pokud bychom chtěli zachovat jejich dobré uspořádání. Ve skutečnosti každá dobře uspořádaná množina je ekvivalentní s nějakým ordinálním číslem, takže je můžeme chápat jako ony reprezentanty či prototypy dané ordinality.

Protože ordinální čísla reprezentují pořadí, operace nad nimi jsou definovány trochu jinak, než jak jsme zvyklí: nejsou komutativní. Zde záleží na pořadí, neboť ω + 1 a 1 + ω jsou z hlediska pořadí množin odlišné věci ‒ to první je fronta o délce (ordinalitě) ω, za níž je dán další prvek, zatímco to druhé je jeden prvek, za nějž je dána fronta o délce ω; je jasné že 1 + ω je vlastně pouze ω, protože v tom nekonečnu dalších přidaných prvků se ten první lehce ztratí. Podobně i ω + ω = 2ω, ale ω⋅2 = ω, protože ordinalita nekonečné řady dvojic je zase jen ω. (Zde je moje notace opačná vůči obecně používané notaci, kdy 2⋅ω = ω. To mi nepřijde přirozené, protože 2ω chápu jako dvě omegy a ω⋅2 chápu jako omegu dvojic. Mám právo si to definovat jinak, ale buďte opatrní, pokud to budete chtít někde takto používat.) Odčítání a dělení ordinálních čísel raději vůbec dělat nebudeme.

To je všechno hezké, ale kolik takových čísel vlastně je, a jak se k nim můžeme dostat? Jeden můj oblíbený způsob, jak nacházet stále větší a větší ordinální čísla, je pomocí rychle rostoucí hierarchie. Smyslem tvorby této hierarchie je ukázat užitečnost ordinálních čísel při hledání velmi velkých přirozených čísel, a to díky diagonalizaci.

Mějme nekonečnou tabulku čísel:

	fk(0)	fk(1)	fk(2)	fk(3)	fk(4)	fk(5)	fk(6)	fk(7)	fk(8)	fk(9)	⋯
f0(x)	1	2	3	4	5	6	7	8	9	10	⋯
f1(x)	2	3	4	5	6	7	8	9	10	11	⋯
f2(x)	3	4	5	6	7	8	9	10	11	12	⋯
f3(x)	4	5	6	7	8	9	10	11	12	13	⋯
f4(x)	5	6	7	8	9	10	11	12	13	14	⋯
f5(x)	6	7	8	9	10	11	12	13	14	15	⋯
f6(x)	7	8	9	10	11	12	13	14	15	16	⋯
f7(x)	8	9	10	11	12	13	14	15	16	17	⋯
f8(x)	9	10	11	12	13	14	15	16	17	18	⋯
f9(x)	10	11	12	13	14	15	16	17	18	19	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱

Každý řádek této tabulky představuje jednu funkci f_k(x). Je vcelku jedno, jak je tato funkce definována, ale je patrné, že každá následující funkce je větší než všechny funkce před ní. (Normálně u takových hierarchií bývá zvykem zvolit f_k(x) tak, aby rostla trochu strměji, ale to tady nepotřebujeme; asi by bylo lepší říct, že máme jen rostoucí hierarchii, ovšem nikoliv rychle.)

Existuje nějaká funkce, která roste víc než jakákoliv f_k(x) v této tabulce? Ano; pokud bychom vzali kupříkladu čísla na diagonále (1, 3, 5, 7, 9, 11 atd.), evidentně rostou rychleji (o 2) než čísla na jakémkoliv řádku této tabulky. V takovém případě by možná mělo smysl tato čísla identifikovat taky, a to právě pomocí notace f_ω(x):

	fω+k(0)	fω+k(1)	fω+k(2)	fω+k(3)	fω+k(4)	fω+k(5)	fω+k(6)	fω+k(7)	fω+k(8)	fω+k(9)	⋯
fω(x)	1	3	5	7	9	11	13	15	17	19	⋯
fω+1(x)	2	4	6	8	10	12	14	16	18	20	⋯
fω+2(x)	3	5	7	9	11	13	15	17	19	21	⋯
fω+3(x)	4	6	8	10	12	14	16	18	20	22	⋯
fω+4(x)	5	7	9	11	13	15	17	19	21	23	⋯
fω+5(x)	6	8	10	12	14	16	18	20	22	24	⋯
fω+6(x)	7	9	11	13	15	17	19	21	23	25	⋯
fω+7(x)	8	10	12	14	16	18	20	22	24	26	⋯
fω+8(x)	9	11	13	15	17	19	21	23	25	27	⋯
fω+9(x)	10	12	14	16	18	20	22	24	26	28	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱

Z určitého hlediska je funkce f_ω(x) "za všemi" předchozími funkcemi, protože odpovídající prvky jsou eventuálně větší než prvky jakékoliv dosavadní funkce. Stejně tak dává smysl mít f_ω+1(x) pro funkci odpovídající diagonále posunuté o 1 dolů, a tak podobně. Nic nám nyní nebrání identifikovat i diagonálu v této tabulce jako f_ω+ω(x):

	f2ω+k(0)	f2ω+k(1)	f2ω+k(2)	f2ω+k(3)	f2ω+k(4)	f2ω+k(5)	f2ω+k(6)	f2ω+k(7)	f2ω+k(8)	f2ω+k(9)	⋯
f2ω(x)	1	4	7	10	13	16	19	22	25	28	⋯
f2ω+1(x)	2	5	8	11	14	17	20	23	26	29	⋯
f2ω+2(x)	3	6	9	12	15	18	21	24	27	30	⋯
f2ω+3(x)	4	7	10	13	16	19	22	25	28	31	⋯
f2ω+4(x)	5	8	11	14	17	20	23	26	29	32	⋯
f2ω+5(x)	6	9	12	15	18	21	24	27	30	33	⋯
f2ω+6(x)	7	10	13	16	19	22	25	28	31	34	⋯
f2ω+7(x)	8	11	14	17	20	23	26	29	32	35	⋯
f2ω+8(x)	9	12	15	18	21	24	27	30	33	36	⋯
f2ω+9(x)	10	13	16	19	22	25	28	31	34	37	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱

Smyslem všech těchto tabulek bylo ilustrovat jediné: i když jsme museli najít ordinální čísla až za nekonečnem, díky jejich schopnosti zachytit ordinalitu množin se dají použít v něčem, co je naprosto smysluplné ‒ pokud bychom všechny tyto funkce chtěli seřadit podle toho, jak moc rostou (chceme, aby od určitého místa byly prvky jedné funkce vždy větší než prvky jiné funkce), diagonálně sestrojená funkce je vždy v pořadí větší než všechny řádkové funkce a ordinalita množiny všech funkcí až do f_k(x) je přesně k.

Pokud bychom v diagonalizaci postupovali dále, dostávali bychom funkce f_3ω+k(x), f_4ω+k(x), f_5ω+k(x), f_6ω+k(x) a obecně f_(n+1)ω+k(x) = f_nω+x+k(x). Co ale potom? Dokázali bychom tady najít nějakou funkci, která by se v této posloupnosti nenacházela, ale stále by byla větší než všechny předchozí?

Mohli bychom zkusit diagonalizovat samotnou diagonalizaci, s rostoucím x brát výsledky z dalších a dalších diagonalizací. To by byla funkce g(x) = f_xω(x) a je jen přirozené pro její identifikaci použít číslo ω⋅ω = ω², tedy f_ω²+k(x) = f_xω+k(x):

	fω2+k(0)	fω2+k(1)	fω2+k(2)	fω2+k(3)	fω2+k(4)	fω2+k(5)	fω2+k(6)	fω2+k(7)	fω2+k(8)	fω2+k(9)	⋯
fω2(x)	1	4	9	16	25	36	49	64	81	100	⋯
fω2+1(x)	2	5	10	17	26	37	50	65	82	101	⋯
fω2+2(x)	3	6	11	18	27	38	51	66	83	102	⋯
fω2+3(x)	4	7	12	19	28	39	52	67	84	103	⋯
fω2+4(x)	5	8	13	20	29	40	53	68	85	104	⋯
fω2+5(x)	6	9	14	21	30	41	54	69	86	105	⋯
fω2+6(x)	7	10	15	22	31	42	55	70	87	106	⋯
fω2+7(x)	8	11	16	23	32	43	56	71	88	107	⋯
fω2+8(x)	9	12	17	24	33	44	57	72	89	108	⋯
fω2+9(x)	10	13	18	25	34	45	58	73	90	109	⋯
⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋮	⋱

Zatímco předchozí růst byl lineární, tento je už kvadratický, takže je vidět, že výsledek opravdu roste mnohem rychleji a tato funkce tedy musí být v pořadí za všemi předchozími. I tuto funkci můžeme diagonalizovat a dostaneme f_ω²+ω(x), f_ω²+2ω(x), f_ω²+3ω(x) a opětovnou diagonalizací diagonalizace f_ω²+ω²(x).

Diagonalizací ovšem stále ještě není dost, opět můžeme provést diagonalizaci diagonalizací, a tak dostaneme f_ω³(x), tentokráte s kubickým růstem. Nu a když celé toto opět diagonalizujeme, dostaneme f_ω^ω(x) s růstem jako x^x. Z určitého hlediska si každé takové ordinální číslo můžeme představit i jako výraz, kde místo ω bude x, a takový výraz bude charakteristickou funkcí daného ordinálního čísla, izomorfní vzhledem k pořadí.

Celý tento proces se dá znázornit jedním obrázkem:

Tato spirála končí ve ω^ω, ale nic nám nebrání jít ještě dál. Jako další dostaneme ω^ωω, potom ω^ωωω a na cestě směrem do ω^ωωω⋰ nám překáží už jenom naše notace. Místo ω^ω však můžeme použít Knuthův zápis ω ↑↑ 2 a jít tak ještě dále, až do ω ↑↑ ω.

Kdybychom neměli k dispozici novou notaci, k ω ↑↑ ω se můžeme dostat i jiným způsobem, podobným tomu, jak jsme sestrojili ω, jako sjednocení všech přirozených čísel. Stejným způsobem můžeme sjednotit i všechna ordinální čísla ω ↑↑ n a tím získáme dobře uspořádanou množinu, jejíž ordinalita je právě ω ↑↑ ω. Toto číslo se též značí ϵ₀ a ještě jedna možnost, jak si ho představit, je jako nejmenší pevný bod splňující rovnost x = ω^x, tedy platí ϵ₀ = ω^ϵ₀.

Dosáhli jsme konce našich možností? Stále ne, neboť i za ϵ₀ jsou vyšší ordinální čísla, začněme třeba u ϵ₀ + 1, ω^{ϵ₀ + 1}, ω^{ωϵ₀ + 1} a tak dále. Celá tato posloupnost má opět "limitu", tentokráte ϵ₁ = ϵ₀^{ϵ₀ϵ₀ϵ₀⋰}, další ordinální číslo jako pevný bod x ↦ ϵ₀^x. Už není asi moc překvapivé, že i x ↦ ϵ₁^x má pevný bod ϵ₂ a tímto způsobem můžeme jít opět až do nekonečna, kde nalezneme ϵ_ω a po něm ϵ_ϵω, ϵ_ϵϵω a opět dále až do ϵ_ϵϵϵ⋱ = ζ₀ jako řešení x = ϵ_x. Situace se zde zase opakuje, dostáváme totiž ζ₁ = ζ₀^{ζ₀ζ₀ζ₀⋰} a opět ζ_ζζζ⋱ = η₀.

Zdá se, že nám pomalu dochází řecká abeceda, ale chybějící notace nesmí být pro matematika překážkou! Stačí použít Veblenovu hierarchii, která nám dá alternativní označení všech dosavadních čísel: ϕ₀(x) = ω^x, ϕ₁(x) = ϵ_x, ϕ₂(x) = ζ_x a ϕ₃(x) = η_x. Jednoduše řečeno dolní index u ϕ nám vybírá "písmenko" a argument této funkce nám vybírá dolní index toho písmenka (až na ϕ₀). Pro další účely budu ϕ_k(0) zkracovat prostě jako ϕ_k.

Ani s Veblenovou funkcí jsme se stále na konec nedostali, protože i tato hierarchie tvoří dobře uspořádanou množinu a její ordinalita je řešením x = ϕ_x, tedy ϕ_ϕϕϕ⋱ = Γ₀. Toto číslo se nazývá Fefermanův–Schütteho ordinál a ohraničuje všechny ordinály, ke kterým se dá dostat diagonalizací a rekurzí. Od tohoto momentu se už pohybujeme v oblasti tak velkých čísel, že nám dochází nejenom notace, ale vyjadřovací síla mnohých existujících matematických teorií. Přesto však můžeme pokračovat dále, neboť tak jako Γ₀ ohraničuje všechna ordinální čísla dosažitelná pomocí Veblenovy funkce z předchozích čísel, tak i Γ₁ ohraničuje všechna další dosažitelná ordinální čísla, která obsahují Γ₀.

Sice jsme ztratili schopnost konstrukce takových čísel, ale pořád můžeme jít dál; po Γ₁ dostáváme Γ₂, potom Γ₃ a nakonec samozřejmé i Γ_ΓΓΓ⋱. Přestože hovoříme o astronomicky velkých číslech, za Fefermanovým–Schütteho ordinálem už není moc velká možnost invence; všechno budou jen ohraničení nějak dosažitelných ordinálních čísel. I Veblenovu funkci můžeme dále rozšiřovat o další argumenty, ovšem se stejným výsledkem.

Pokud bychom chtěli prorazit teoretickou hranici těchto ordinálů, potřebujeme různé triky. Nejčastěji se do hry přibere nehorázně velké ordinální číslo Ω, takové, které jsme doposud ještě nenavštívili, a které je větší než cokoliv, co bychom mohli tímto způsobem vytvořit. Taková existují taky, ale ještě jsme příklad žádného z nich neviděli, takže tuto cestu dále následovat nebudeme. 

Všechna dosavadní čísla byla spočitatelná (tedy existuje algoritmus, který dokáže posoudit, jestli nějaká množina má takovou ordinalitu), takže je můžeme ohraničit nejmenším nespočitatelným ordinálem, což je Churchův–Kleeneho ordinál ω₁^CK, opět další významný hraniční ordinál z různých teorií. Po něm následují i další ordinály, různě ohraničují větší a větší množiny ordinálních čísel, ale už tak zajímavé nejsou, a v principu můžeme přijít na další množiny ordinálních čísel, za nimiž vždy musí být ordinál, který v nich není.

Sice to vypadá, že jsme dosáhli již astronomických výšek, přesto jsme se však téměř vůbec nepřiblížili ničemu, co tvoří většinu celého prostoru ordinálních čísel. Zůstali jsme totiž jen u spočetných ordinálních čísel, to znamená, že každé určuje jen nějaké uspořádání spočetné množiny, tedy například přirozených čísel. Znamená to taky, že jakákoliv množina se sebevyšší ordinalitou, i tak vysokou jako ω₁^CK, má stále stejný počet prvků jako přirozená čísla. Sice se nám tedy povedlo přirozená čísla "roztáhnout" do pyramidálních výšin stále složitějšími uspořádáními, ale zatím jsme vlastně na skutečně větší množinu nenarazili. Zatímco přirozená čísla charakterizovala jak pořadí, tak velikost, zde zatím zůstalo jen u pořadí.

To se ovšem změní ‒ všechna spočetná ordinální čísla, tedy taková, která jsme zatím viděli, i všechna další, která mohou uspořádat přirozená čísla, sama tvoří množinu. Tato množina je dobře uspořádaná, ale musí být větší než všechny předchozí, nejenom vyšší jako ordinální číslo, ale i mohutnější jako množina (protože jinak by musela obsahovat sama sebe, což nejde). Jedná se o první nespočetné ordinální číslo, ω₁ (občas též značeno Ω; lze jej též použít v procesu výše pro nacházení dalších vysokých spočetných ordinálů), a takovou ordinalitu může mít pouze a jedině množina větší než přirozená čísla.

Podobným způsobem můžeme definovat i ω₂ jako ordinalitu všech ordinálních čísel uspořádávajících množiny o stejné velikosti, jako má ω₁, a asi už není překvapivé, že nakonec dostaneme i ω_ω, ω_ωω a dorazíme k dalšímu limitnímu ordinálu ω_ωωω⋱ = Φ₁. Jak patrno, to, co jest nahoře, jest jako to, co jest dole.

Hledat čísla větší než Φ₁ má samozřejmě smysl, ale v tento moment už není potřeba vázat se tolik na pořadí. Existence čísel ω₁, ω₂ atd. nám ukázala, že můžeme tvořit tak mohutné množiny ordinálních čísel, jak jen chceme, ale co vlastně znamená mohutnost množiny, či její spočetnost, a jak daleko se takto můžeme dostat? Na to vše se podíváme někdy příště.

Jako poslední věc se opět musím zamyslet, jak by vypadala ordinální čísla v našem matematickém světě. Inu, jelikož byla vytvořena jako rozšíření přirozených čísel, musí se nacházet na samém vrcholu naší nekonečné věže, a ještě výše. Je to vůbec možné? Samozřejmě: