Goodsteinova věta

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

Pro každou Goodsteinovu posloupnost m_0, m_1, m_2, \ldots \,\! existuje takové přirozené číslo n \,\! , pro které je m_n = 0 \,\! .

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 \omega \,\!

Máme-li nějakou Goodsteinovu posloupnost, například

m_0 = 21 = 2^{(2^2)} + 2^2 + 1 \,\!,

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\cdot3 + 4^2\cdot3 + 4\cdot3 + 3 \,\!,

m_3 = (5^{(5^5)} + 5^3\cdot3 + 5^2\cdot3 + 5\cdot3 + 3) - 1 = 5^{(5^5)} + 5^3\cdot3 + 5^2\cdot3 + 5\cdot3 + 2 \,\!,

\vdots \,\!

můžeme ji seshora omezit následující posloupností ordinálních čísel:

\alpha_0 = \omega^{(\omega^{\omega})} + \omega^{\omega} + 1 \,\!,

\alpha_1 = \omega^{(\omega^{\omega})} + \omega^{\omega} \,\!,

\alpha_2 = \omega^{(\omega^{\omega})} + \omega^3\cdot3 + \omega^2\cdot3 + \omega\cdot3 + 3 \,\!,

\alpha_3 = \omega^{(\omega^{\omega})} + \omega^3\cdot3 + \omega^2\cdot3 + \omega\cdot3 + 2 \,\!,

\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á. 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. +more 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ů. +more Důkaz probíhá schematicky takto: # 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í. # Vybereme nějaké m\in M nestandardní a k němu nejmenší k takové, že k-tý člen Goodsteinovy posloupnosti od m je nulový. # Ukážeme, že k>m a dokonce interval je tak „velký“, že lze model M rozdělit na dvě části \,D a \,M \setminus D tak, že: #* D je dolní množina v M (tj. s každým prvkem obsahuje i všechny menší) #* m\in D, k\not\in D #* D je modelem Peanovy aritmetiky # 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

Goodsteinova posloupnost * Ordinální aritmetika

Kategorie:Teorie množin Kategorie:Matematické věty a důkazy