Goodsteinova posloupnost

Technology

12 hours ago

Author

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