Doteď jsme používali Wainerovu fundamentální posloupnost ordinálů, ale nevíme, co přesně je. Seznámíme se s mezními (limitními) ordinály a jak se mezi nimi přechází.
Ordinál α je mezní ordinál, pokud jsou ordinály menší než α a zároveň kdykoliv je β menší než α, je ordinál γ takový, aby platilo:
β < γ < α
------
Všechny ostatní ordinály jsou izolované. Jedinou výjimku tvoří 0, jež není ani izolovaný ani mezní ordinál.
K tomuto popisu se můžeš kdykoliv vrátit, bude-li třeba, protože mu nemusíš nutně hned rozumět. Ukážeme si příklady mezních ordinálů, abychom je lépe pochopili. Začněme prvním nekonečným ordinálem, ω:
ω = sup{0, 1, 2, 3, ...}
------
Co to ale znamená? Suprémum je zde nejmenší ordinál, který je větší než všechny ostatní ordinály v množině. Jelikož přirozených čísel je nekonečno, nenašli bychom největší číslo, ale můžeme si takto uměle stvořit nekonečné číslo.
Abychom pokračovali dále, musíme si vysvětlit jedno pravidlo aritmetiky nekonečných ordinálů:
1 + ω = ω
ω + 1 ≠ ω
1 + ω < ω + 1
------
Na pořadí operací u nekonečných ordinálů záleží. Je nutné umístit větší prvky před menšími. Odůvodnění je jasné: kdybychom přidali prvek před 0, mohli bychom přepsat tento prvek na 0 a všechna ostatní čísla zmenšit o 1; množina by byla stejná. Ale přidáme-li tento prvek až po ω, nic takového bychom udělat nemohli.
Teď bychom tedy mohli pokračovat:
ω * 2 = sup{ω + 0, ω + 1, ω + 2, ω + 3, ...}
ω * 3 = sup{ω * 2 + 0, ω * 2 + 1, ω * 2 + 2, ω * 2 + 3, ...}
------
Dostali bychom se až k:
ω2 = sup{ω * 0, ω * 1, ω * 2, ω * 3, ω * 4, ω * 5, ...}
ω3 = sup{ω2 * 0, ω2 * 1, ω2 * 2, ω2 * 3, ...}
------
Můžeme tak vytvořit libovolný nekonečný ordinál:
ω4 * 5 = sup{ω4 * 4 + 0, ω4 * 4 + 1, ω4 * 4 + 2, ...}
------
Je načase zkusit mocninné věže:
ωω = sup{ω0, ω1, ω2, ω3, ω4, ...}
ωωω = sup{ωω0, ωω1, ωω2, ωω3, ...}
------
Až bychom narazili na samotný konec Wainerovy hierarchie:
ωωωω (...) = ε0
Tedy:
ε0 = sup{0, 1, ω, ωω, ωωω, ...}
------
ε0 je vrchol Wainerovy posloupnosti. Sestavili jsme si dobře uspořádanou řadu nekonečných ordinálů, které teď budeme moci využít s naší rychle rostoucí hierarchií. Kdykoliv narazíme na mezní ordinál, zaměníme jej za ntý prvek z naší fundamentální posloupnosti, již jsme použili v sup{...}. Pozor! Zde indexujeme prvky od 0. Než ale budeme pokračovat, je nezbytně nutné si celou posloupnost řádně zobecnit, jinak by se později mohly vyskytnout potíže:
ω[n] = n
ωα + 1[n] = ωα * n
ωα[n] = ωα[n], je-li α mezní ordinál
(ωα1 + ωα2 + ... + ωαk)[n] = ωα1 + ... + ωαk[n], pokud α1 ≥ α2 ≥ ... ≥ αk
ε0[0] = 0
ε0[n + 1] = ωε0[n] = ω ↑↑ (n - 1)
------
Zkusme si jednoduchý příklad:
fω2(3) = fω * ω(3)
Užijeme třetí pravidlo rychle rostoucí hierarchie, abychom vyměnili mezní ordinál ω * ω za ω * 3, třetí prvek fundamentální posloupnosti pro ω2:
fω * 3(3) = fω * 2 + 3(3)
Co jsme to udělali? ω * 3 je ω + ω + ω, ale to je taky mezní ordinál, takže poslední ω jsme opět nahradili trojkou. Stejně tak je i třetí prvek fundamentální posloupnosti pro ω * 3 roven ω * 2 + 3. Pokračujme:
fω * 2 + 3(3) = fω * 2 + 2(fω * 2 + 2(fω * 2 + 2(3)))
------
To už začíná vypadat složitě! Zkusíme teď rozepisovat pouze nejvnořejnější části:
fω * 2 + 2(3) = ...(fω * 2 + 1(3)))
fω * 2 + 1(3) = ...(fω * 2(3)))
fω * 2(3) = fω + 3(3)
Pozor! Jelikož ω * 2 je mezní ordinál, museli jsme jej nejdřív přepsat podle třetího pravidla rychle rostoucí hierarcihe. Pokračujme:
fω + 3(3) = ...(fω + 2(3)))
fω + 2(3) = ...(fω + 1(3)))
fω + 1(3) = ...(fω(3)))
Opět jsme narazili na mezní ordinál! Znovu jej přepišme:
fω(3) = f3(3)
f3(3) = ...(f2(3)))
f2(3) = ...(f1(3)))
f1(3) = ...(f0(3)))
------
Vůbec jen vypsat nejvnořenější funkce bylo obtížné! Pamatujeme si, že fω + 1(n) roste podobně rychle jako Grahamovo gn a že fω + 2(n) rekurzivně opakuje gn. Zkus si jen představit tu šílenost, kdybychom Grahamovo číslo použili v ω + n jako konečnou část indexu! A věř, že fω2(3) by se i takovému číslu mohlo pouze smát!
Dále si ukážeme Hardyho hierarchii, abychom lépe porozuměli Goodsteinově větě. Brzo se i naučíme zkrotit rychle rostoucí hierarchii!