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},\ldots \,\!$ 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\,\!$
$\vdots \,\!$

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^{402\,653\,211}-3$ , což je číslo, které má 121 210 700 číslic.

Související články