Pomalu rostoucí hierarchie ~ fη0 + 1(n)

Poslední dobou se jen tváříme, že všemu rozumíme. Ve skutečnosti nemáme ani ponětí, jak nepochopitelné struktury ordinálů tvoříme, a už vůbec nemáme představu, co se děje s rychle rostoucí hierarchií. Abychom měli trochu přehled, naučíme se pracovat s pomalu rostoucí hierarchií, jež se řídí podle tří pravidel:

g0(n) = 0

gα + 1(n) = gα(n) + 1

gβ(n) = gβ[n](n), je-li β mezní ordinál

------

Připomíná Hardyho hierarchii, ale nemohla by se víc lišit. Zdánlivě malé rozdíly mezi těmito dvěma hierarchemi tvoří dvě nesrovnatelné posloupnosti. Ukážeme si mnoho příkladů. Začněme malými ordinály:

g0(fη + 1(1000)) = 0

To nám podle nultého pravidla je jasné.

g1000(fη + 1(fε0(G))) = 1000

Zatím roste tak, že neroste. To bude platit, dokud na scénu nepřijdou nekonečné ordinály:

gω(1010) = 1010

Nenechme se zmást klamem, že by snad pomalu rostoucí hierarchie začala dohánět Hardyho hierarchii:

gωω(10) = 1010

Kdežto u Hardyho hierarchie bychom měli f10(10). Ale Hardyho hierarchie byla též o krok pozadu! Co kdybychom pořádně zatlačili?

gε0 + 1(3) = 28

------

Cože? Pouhých 28? Kdybychom použili Hardyho hierarchii, vypadalo by to takto:

Hε0 + 1(3) = Hε0(4)

Hε0(4) = Hωωω(4)

Převedeme na rychle rostoucí hierarchii:

Hωωω(4) = fωω(4)

------

A to je velmi velké číslo! Co kdybychom to ale porovnali s rychle rostoucí hierarchií?

fε0 + 1(3) = fε0(fε0(fε0(3)))

Rozepíšeme nejvnořenější funkci:

fε0(3) = fωω(3)

------

Bože, spas nás! Z této funkce by vzniklo tak nepředstavitelné číslo, které by teprve určovalo počet ω v druhém opakování ε0! A to bychom opakovali ještě jednou na konec! Zde je nutné podoknout, že přestože platí:

Hε0(n) < fε0(n) < Hε0(n + 1)

Nutně to neznamená, že to bude platit pro každý větší ordinál! Jak jsme zrovna viděli výše, pro ordinál ε0 + 1 a vstupní hodnotu 3 je rozdíl mezi rychle rostoucí hierarchií a Hardyho hierarchií nepředstavitelný a ani podstatný rozdíl ve vstupních hodnotách by Hardyho hierarchii nezachránil. Rovnost mezi rychle rostoucí hierarchií a Hardyho hierarchií bude platit jen pro některé větší ordinály.

------

Vraťme se k pomalu rostoucí hierarchii. Když se zamyslíme, všimneme si, že bude přesně popisovat počet rozdílných funkcí v prvním rozepsání. Zkusme se podívat:

gωω(2) = 4

Nyní si rozepíšeme indexy, které bychom našli v prvním rozepsání rychle rostoucí hierarchie se vstupní hodnotou 2:

0) ωω = ω2 = ω * 2 = ω + 2

1) ω + 1

2) ω

3) 1

4) 0

Tak by vypadala rychle rostoucí hierarchie:

fω + 1(fω(f1(f0(2))))

------

Zatímco výsledek pomalu rostoucí hierarchie jsou čtyři, pro rychle rostoucí hierarchii by to bylo přibližně g2 ↑↑↑↑↑ 6 z Grahamovy funkce; šíleně větší než Grahamovo číslo!

Zkusíme trochu větší posloupnost:

gε0(3) = 27

Protože indexy by pokračovaly takto:

0) ε0

0) ωω

0) ω3

0) ω2 * 3

0) ω2 * 2 + ω * 3

0) ω2 * 2 + ω * 2 + 3

Teprv jsme zapsali první nemezní ordinál. Pokračujme:

1) ω2 * 2 + ω * 2 + 2

2) ω2 * 2 + ω * 2 + 1

3) ω2 * 2 + ω * 2

3) ω2 * 2 + ω + 3

4) ω2 * 2 + ω + 2

5) ω2 * 2 + ω + 1

6) ω2 * 2 + ω

6) ω2 * 2 + 3

7) ω2 * 2 + 2

8) ω2 * 2 + 1

9) ω2 * 2

9) ω2 + ω * 3

9) ω2 + ω * 2 + 3

10) ω2 + ω * 2 + 2

11) ω2 + ω * 2 + 1

12) ω2 + ω * 2

12) ω2 + ω + 3

13) ω2 + ω + 2

14) ω2 + ω + 1

15) ω2 + ω

15) ω2 + 3

16) ω2 + 2

17) ω2 + 1

18) ω2

18) ω * 3

18) ω * 2 + 3

Až po 18. kroku jsme se zbavili mocniny. Konec je již jednoduchý:

19) ω * 2 + 2

20) ω * 2 + 1

21) ω * 2

21) ω + 3

22) ω + 2

23) ω + 1

24) ω

24) 3

25) 2

26) 1

27) 0

------

Celkově jsme zapsali 27 ruzných ordinálů, než jsme se dobojovali k 0. Pro ordinály menší než ε0 lze zaměnit všechny ω v indexu za n: 33 je 27.

Zkusme si rozepsat větší nekonečný ordinál se vstupní hodnotou 3:

0) ωωω

0) ωω3

0) ωω2 * 3

0) ωω2 * 2 + ω * 3

0) ωω2 * 2 + ω * 2 + 3

0) ωω2 * 2 + ω * 2 + 2 * 3

0) ωω2 * 2 + ω * 2 + 2 * 2 + ωω2 * 2 + ω * 2 + 1 * 3

0) ...

------

Trvalo by velmi dlouho, než bychom se vůbec dostali k prvnímu nemeznímu ordinálu! Celý zápis by obsahoval 333 (tedy 7625597484987) kroků.

Teď již víme, jaký vztah má pomalu rostoucí hierarchie k rychle rostoucí hierarchii. Jak by vypadal růst g, kdybychom využili ordinály jako ζ či η?

gζ0(n) ~ n ↑↑↑ (n + 1)

gη0(n) ~ n ↑↑↑↑ (n + 1)

------

Snad ani nemusíme zkoušet vstupní hodnoty, my bychom výsledky totiž ani celé nezapsali. Dostali jsme se do bodu, kdy pouhý počet rozdílných funkcí v prvním rozepsání je roven nepředstavitelným číslům! Někdy si ukážeme ordinály tak obrovské, že pokud bychom je užili v indexu pomalu rostoucí hierarchie, rostla by stejně rychle jako fε0(n)! Teď je ale načase se podívat na Veblenovy funkce.