Jsme připraveni probrat Goodsteinovu větu. Nebude to snadné, ale zdoláme-li ji, odemkneme si dveře do nové oblasti googologie. Budeme se spoléhat na naši zběhlost ve Wainerově posloupnosti ordinálů, tudíž pokud ti něco není jasné, doporučuji znovu si přečíst předchozí části.
Goodsteinovy posloupnosti závisí na pojmu "hereditary base-n notation". Nepodařilo se mi vyhledat překlad, proto použiji vlastní: dědičný zápis o základu n.
V dědičném zápisu o základu n, kde n je přirozené číslo větší než 1, libovolné číslo m je zapsáno jako součet násobků mocnin n:
m = aknk + ak - 1nk - 1 + ... + a0
Kde každý součinitel a splňuje: 0 ≤ a < n, též ak ≠ 0.
------
Zkusme přepsat 35 na dvojkový základ:
35 = 32 + 2 + 1 = 25 + 21 + 20
Tedy 35 bychom napsali jako 100011. Vyzkoušíme převést 100 na trojkový základ:
100 = 81 + 18 + 1 = 34 + 2 * 32 + 30
Tedy 10201.
------
Všimni si, že mocnitele jsme nepřepsali do n základu. Kdybychom tak učinili, stvoříme právě dědičný zápis o základu n. Patrně se může stát, že ani po druhém opakování je nepřepíšeme do n základu; musíme pak tento postup opakovat víckrát.
Přepišme tedy 35 a 100 na dědičné zápisy o základech 2 a 3:
35 = 2221+ 1 + 21 + 1
100 = 331+ 1 + 2 * 32 + 1
------
Teď si povíme, co je Goodsteinova posloupnost. Popíšeme ji slovně:
První prvek posloupnosti je G0(n).
Pro G0(n) přepíšeme n do dědičného zápisu o dvojkovém základu.
Pro Gk(n) vezmeme zápis Gk - 1(n), zvětšíme všechny číslice a, které jsou rovny základu, o 1 a z výsledného zápisu odečteme 1. Následně zvětšíme základ o 1.
Pokračujeme, dokud Gk(n) není rovno nule.
Index k, pro které je Gk(n) rovno nule, je výsledek pro G(n)
------
A jak to bude vypadat? Podívejme se:
G0(0) = 0
To dá rozum; ani naše rychle rostoucí hierarchie by s nulou tolik nedokázala! Zvětšíme vstupy:
G0(1) = 1
G1(1) = 1 - 1 = 0
Samozřejmě! Zkusíme ještě dvojku a trojku:
G0(2) = 21
G1(2) = 31 - 1 = 2
G2(2) = 2 - 1 = 1
G3(2) = 1 - 1 = 0
Takže G(2) je rovno třem. Nudné, ale očekávané. Jdeme dál:
G0(3) = 21 + 1
G1(3) = 31
G2(3) = 41 - 1 = 3
G3(3) = 3 - 1 = 2
G4(3) = 2 - 1 = 1
G5(3) = 1 - 1 = 0
Proč opět tolik povyku kvůli něčemu tak pomalu rostoucímu? No dobře, poslední šance:
G0(4) = 22
G1(4) = 33 - 1 = 2 * 32 + 2 * 3 + 2
G2(4) = 2 * 42 + 2 * 4 + 1
G3(4) = 2 * 52 + 2 * 5
G4(4) = 2 * 62 + 2 * 6 - 1 = 2 * 62 + 6 + 5
G5(4) = 2 * 72 + 7 + 4
...
G9(4) = 2 * 112 + 11
G10(4) = 2 * 122 + 11
...
G22(4) = 2 * 242 - 1 = 242 + 23 * 24 + 23
...
G3 * 2402653209 - 3(4) = 2 * (3 * 2402653209 - 3)
...
G3 * 2402653211 - 3(4) = 0
------
Zničehonic to vyskočilo na poměrně velké číslo! Ale opravdu to roste rychleji než všechno, co jsme si zatím ukázali? Vizme výsledky větších vstupních hodnot:
G(12) = fω + 1(f3(3)) - 3
Vždyť to je mnohem větší než Grahamovo číslo! A jak vypadají další?
G(64) = fωω + 3(3) - 3
------
To je šílené! Jednoduchá pravidla, malé vstupní hodnoty, a přesto to převálcovalo vše, co jsme si již ukázali! Ale jak je to možné? Chicon v 1983 dokázal tento vztah:
G(n) = hRω2(n + 1)(1) - 1
Kde Rω2(n + 1) je výsledek, přepsali-li bychom n do dědičného zápisu o dvojkovém základu a všechny dvojky zaměnili za ω. Například:
G(12) = hωω + 1 + ωω + 1(1) - 1
------
Neukazovali jsme si, jak převádět mezi Hardyho hierarchií a rychle rostoucí hierarchií v těchto složitějších případech, naštěstí Caicedo v 2007 to pořešil za nás. V případě, že n = 2m1 + 2m2 + ... + 2mk, kde m1 > m2 > ... > mk:
G(n) = fRω2(m1)(fRω2(m2)(...(fRω2(mk)(3))...)
------
Tím jsme si před chvílí odvodili, že G(12) je výrazně větší než Grahamovo číslo. Z těchto dvou rovností plyne:
G(2 ↑↑ n) = fω ↑↑ (n - 1)(3) - 3
------
Aby tomu mohla čelit naše rychle rostoucí hierarchie, musíme využít samotný vrchol Wainerovy posloupnosti:
fε0(n) = fω ↑↑ (n - 1)(n)
Už od pohledu vidíme, že to bude aspoň o krok napřed vůči Goodsteinově funkci. Konečně si povíme o Goodsteinově větě. Shrnu ji krátce, jelikož celý důkaz je příliš složitý: pro libovolné n v G(n) je takové konečné k, aby Gk(n) bylo rovno nule.
Proč je to tak důležité? Protože Peanova aritmetika toto tvrzení nedokáže potvrdit. Abychom toto tvrzení dokázali, potřebujeme mnohem mocnější sadu axiomů. Obdobně bychom nemohli potvrdit konečnost žádné funkce, která by rostla rychleji než Goodsteinova.
Přežili jsme střet s Goodsteinovou větou a vyprázdnili jsme Wainerovu posloupnost ordinálů. Čeká nás obrovské území nekonečných ordinálů, pro které se budeme muset buď naučit nové fundamentální posloupnosti, nebo si vytvořit vlastní. Určitě bychom přišli na vlastní posloupnosti, ale bude lehčí se podívat na výtvory ostatních.