Goodsteinova posloupnost

Goodsteinova posloupnost je matematický pojem označující jistý druh posloupnosti přirozených čísel. Goodsteinovy posloupnosti a s nimi související Goodsteinova věta jsou dobrým příkladem toho, jak mohou vlastnosti nekonečných množin (v tomto případě konkrétně ordinálních čísel) ovlivňovat pravdivost tvrzení o přirozených číslech, tedy o objektech konečných.

O vlastnostech Goodsteinových posloupností totiž nelze rozhodnout v běžné Peanově aritmetice z jejích axiomů - Goodsteinova věta je na těchto axiomech nezávislá. Teprve s použitím transfinitní rekurze a výsledků ordinální aritmetiky je tato věta dokazatelná.

Definice

Goodsteinova posloupnost $m_0,m_1,m_2,\dots$ je tvořena rekurzivně ze svého prvního členu následujícím způsobem:

1.Zvolme si jako první člen posloupnosti nějaké přirozené číslo (například $m_0=21$).

2.Vyjádřeme toto číslo jako mocninný rozvoj čísla 2 a totéž proveďme i s exponenty jednotlivých členů rozvoje:
$m_0=21=2^4+2^2+1=2^{(2^2)}+2^2+1$

3. Další člen posloupnosti vznikne z předchozího vždy tak, že všechna čísla základu rozvoje nahradíme číslem o 1 vyšším, od výsledku odečteme 1 a vzniklé číslo opět vyjádříme způsobem popsaným ve 2, ale tentokrát pro vyšší základ:
$m_1=(3^{(3^3)}+3^3+1)-1=3^{(3^3)}+3^3$
$m_2=(4^{(4^4)}+4^4)-1=4^{(4^4)}+4^3.3+4^2.3+4.3+3$
$m_3=(5^{(5^5)}+5^3.3+5^2.3+5.3+3)-1=5^{(5^5)}+5^3.3+5^2.3+5.3+2$
$⋮$

Vlastnosti Goodsteinových posloupností

Je na první pohled vidět, že taková posloupnost zpočátku velice rychle roste - doporučuji zkusit si vypočítat hodnotu prvních pár členů - i pro malý první člen. Co teprve v případě, že bychom se nedrželi při zdi a místo 21 začali například s 1021!

Velice překvapující je proto tvrzení Goodsteinovy věty, která říká:
Pro každou Goodsteinovu posloupnost existuje takové přirozené číslo $n$, pro které je $m_n=0$.

Goodsteinova posloupnost tedy na počátku velice rychle roste, ale dříve nebo později se zarazí, začne klesat, a nakonec skončí na nule. I pro velmi malý první člen však může být doba po níž se posloupnost dostane na nulu ohromná - například pro $m_0=4$ je $m_k$ poprvé rovné nule až pro $k=3\cdot 2^{402653211}-3$, což je číslo, které má 121 210 700 číslic.

Související články

• Goodsteinova věta
• Ordinální aritmetika
• Peanova aritmetika
• Rekurze
• Transfinitní rekurze