Wainerova posloupnost ~ fω2(n)

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!