Goodsteinova věta

Goodsteinova věta, vyslovená v roce 1944 R. Goodsteinem, tvrdí:

Pro každou Goodsteinovu posloupnost ${\displaystyle m_{0},m_{1},m_{2},\ldots \,\!}$ existuje takové přirozené číslo ${\displaystyle n\,\!}$, pro které je ${\displaystyle m_{n}=0\,\!}$.

Goldsteinova posloupnost

Goodsteinova posloupnost je matematický pojem označující jistý druh posloupnosti přirozených čísel. Goodsteinovy posloupnosti 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.

Definice

Goodsteinova posloupnost ${\displaystyle 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 ${\displaystyle 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:

${\displaystyle m_{0}=21=2^{4}+2^{2}+1=2^{(2^{2})}+2^{2}+1}$

1. 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:

   ${\displaystyle m_{1}=(3^{(3^{3})}+3^{3}+1)-1=3^{(3^{3})}+3^{3}}$

   ${\displaystyle m_{2}=(4^{(4^{4})}+4^{4})-1=4^{(4^{4})}+4^{3}.3+4^{2}.3+4.3+3}$

   ${\displaystyle 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}$

   ${\displaystyle \vdots }$

Vlastnosti Goodsteinových posloupností

Je na první pohled vidět, že taková posloupnost zpočátku velice rychle roste i pro malý první člen.

Goodsteinova věta však paradoxně říká, že pro každou Goodsteinovu posloupnost existuje takové přirozené číslo ${\displaystyle n}$, pro které je ${\displaystyle 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 ${\displaystyle \,m_{0}=4}$ je ${\displaystyle \,m_{k}}$ rovné nule až od ${\displaystyle k=3\cdot 2^{402\,653\,211}-3}$, což je číslo, které má 121 210 700 číslic.

Myšlenka důkazu

Ačkoliv Goodsteinova věta pojednává o chování přirozených čísel, její důkaz vychází z vlastností čísel nekonečných - konkrétně z vlastností ordinální mocniny se základem ${\displaystyle \omega \,\!}$

Máme-li nějakou Goodsteinovu posloupnost, například
${\displaystyle m_{0}=21=2^{(2^{2})}+2^{2}+1\,\!,}$
${\displaystyle m_{1}=(3^{(3^{3})}+3^{3}+1)-1=3^{(3^{3})}+3^{3}\,\!,}$
${\displaystyle m_{2}=(4^{(4^{4})}+4^{4})-1=4^{(4^{4})}+4^{3}\cdot 3+4^{2}\cdot 3+4\cdot 3+3\,\!,}$
${\displaystyle m_{3}=(5^{(5^{5})}+5^{3}\cdot 3+5^{2}\cdot 3+5\cdot 3+3)-1=5^{(5^{5})}+5^{3}\cdot 3+5^{2}\cdot 3+5\cdot 3+2\,\!,}$
${\displaystyle \vdots \,\!}$,

můžeme ji seshora omezit následující posloupností ordinálních čísel:
${\displaystyle \alpha _{0}=\omega ^{(\omega ^{\omega })}+\omega ^{\omega }+1\,\!,}$
${\displaystyle \alpha _{1}=\omega ^{(\omega ^{\omega })}+\omega ^{\omega }\,\!,}$
${\displaystyle \alpha _{2}=\omega ^{(\omega ^{\omega })}+\omega ^{3}\cdot 3+\omega ^{2}\cdot 3+\omega \cdot 3+3\,\!,}$
${\displaystyle \alpha _{3}=\omega ^{(\omega ^{\omega })}+\omega ^{3}\cdot 3+\omega ^{2}\cdot 3+\omega \cdot 3+2\,\!,}$
${\displaystyle \vdots \,\!}$.

Taková posloupnost je klesající a podle vlastností klesajících posloupností na třídě ordinálních čísel má tedy pouze konečně mnoho nenulových členů - žádná klesající posloupnost ordinálních čísel nemůže být nekonečná. Máme tedy posloupnost, která shora omezuje Goodsteinovu posloupnost, a která nakonec skončí na nule - tím pádem i Goodsteinova posloupnost nakonec skončí na nule.

Význam Goodsteinovy věty

Goodsteinova věta je příkladem tvrzení o přirozených číslech, které nelze dokázat ani vyvrátit z axiomů Peanovy aritmetiky - je tedy na těchto axiomech nezávislá. Teprve s použitím transfinitní rekurze a výsledků ordinální aritmetiky je tato věta dokazatelná. Její relativní bezespornost s Peanovou aritmetikou ostatně vyplývá již z faktu, že ji lze dokázat v Zermelově–Fraenkelově teorii množin, jejíž konečná ordinální čísla jsou modelem Peanovy aritmetiky. Nedokazatelnost Goodsteinovy věty v Peanově aritmetice prokázali roku 1982 Laurie Kirby a Jeff Paris užitím metod Ketonena a Solovaye.

Goodsteinova věta zůstává dodnes jediným teoreticky číselným tvrzením, o němž je známa jeho nezávislost na Peanově aritmetice. Všechna další nezávislá tvrzení lze sice vyjádřit „v řeči přirozených čísel“, ale svým významem jsou spíše kombinatorická (různé verze Ramseyovy věty) nebo logická (Gödelova formule a její obdoby).

Z filosofického hlediska je fakt, že je nějaké tvrzení o přirozených číslech možné dokázat pouze s použitím aktuální formy nekonečna - tj. ordinálních čísel, jistě zarážející.

Myšlenka důkazu nezávislosti na PA

Hlavní myšlenka důkazu nezávislosti Goodsteinovy věty na Peanově aritmetice spočívá ve „zkrácení“ daného nestandardního modelu ve kterém případně Goodsteinova věta platí na model Peanovy aritmetiky, v němž již platit nemůže. Ke konstrukci takového zkrácení se používá teorie indikátorů. Důkaz probíhá schematicky takto:

1. Zvolíme libovolný nestandardní model M Peanovy aritmetiky. Pokud v něm Goodsteinova věta neplatí, je důkaz hotov. Předpokládáme tedy, že v něm platí.
2. Vybereme nějaké ${\displaystyle m\in M}$ nestandardní a k němu nejmenší k takové, že k-tý člen Goodsteinovy posloupnosti od m je nulový.
3. Ukážeme, že k>m a dokonce interval <m,k> je tak „velký“, že lze model M rozdělit na dvě části ${\displaystyle \,D}$ a ${\displaystyle \,M\setminus D}$ tak, že:
   • D je dolní množina v M (tj. s každým prvkem obsahuje i všechny menší)
   • ${\displaystyle m\in D}$, ${\displaystyle k\not \in D}$
   • D je modelem Peanovy aritmetiky
4. Pak v modelu D zjevně neplatí Goodsteinova věta, neboť díky minimalitě k Goodsteinova posloupnost od m (které leží v D) nedosáhne nikdy nuly

Odkazy

Reference

• Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 9 (1944), 33-41.
• Kirby, L. and Paris, J., Accessible independence results for Peano arithmetic, Bull. London. Math. Soc., 14 (1982), 285-93.
• Sochor, A., Klasická matematická logika, Praha, Karolinum 2001

Související články

• Ordinální aritmetika

Portály: Matematika