Twierdzenie Goodsteina

Twierdzenie Goodsteina – twierdzenie teorii liczb sformułowane przez Goodsteina w 1944 roku dotyczące pewnej własności ciągów liczb naturalnych. Mimo że sformułowanie twierdzenia jest czysto arytmetyczne i względnie nieskomplikowane, twierdzenie to jest niezależne od aksjomatyki Peana, co udowodnili^[1] w 1982 roku Jeff Paris i Laurie Kirby.

Popularne sformułowanie

Wybierzmy liczbę naturalną m(0), na przykład 1077:

m(0)=1077

zapiszmy tę liczbę w postaci potęg dwójki:

m(0)=1077=2^{10}+2^{5}+2^{4}+2^{2}+1

Dokonajmy takiego przedstawienia wszystkich liczb występujących w powyższym zapisie, aby każda z nich była wyrażona wyłącznie w postaci potęg liczby 2:

m(0)=2^{10}+2^{5}+2^{4}+2^{2}+1=2^{2^{2+1}+2}+2^{2^{2}+1}+2^{2^{2}}+2^{2}+1

Zamieńmy w powyższym wyrażeniu wszystkie liczby 2 na liczbę 3:

m(0)'=3^{3^{3+1}+3}+3^{3^{3}+1}+3^{3^{3}}+3^{3}+1

przyjmijmy, że $m(1)=m(0)'-1,$ czyli:

m(1)=m(0)'-1=3^{3^{3+1}+3}+3^{3^{3}+1}+3^{3^{3}}+3^{3}

w wyrażeniu m(1) dokonajmy zamiany liczby 3 na 4 i odejmijmy 1; dostajemy w ten sposób m(2)
kontynuujemy postępowanie, m(3) otrzymamy zamieniając 4 na 5 i odejmując 1.
otrzymując ciąg liczbowy m(i) gdzie i=1,2... jest liczbą naturalną.

Twierdzenie Goodsteina: tak otrzymany ciąg zmierza do zera.

Jednak jak łatwo się przekonać pierwsze N wyrazów ciągu, gdzie N jest pewną bardzo dużą liczbą zależną od m(0), rośnie bardzo szybko (W szybko rosnącej hierarchii: $f_{\varepsilon _{0}}(n)$ ). Pośrednie wyrazy dla liczby 1077 osiągają wartości rzędu $10^{10000}$ i więcej, aby w końcu dać w wyniku 0. Jak się okazuje, nie można tego faktu dowieść w ramach systemu formalnego arytmetyki Peana, jest to zatem nietrywialny przykład twierdzenia ciekawego matematycznie i zarazem niedowiedlnego na gruncie teorii liczb naturalnych. Dowód tego twierdzenia jest oparty na arytmetyce liczb porządkowych.

Przypisy

↑ Laurie Kirby, Jeff Paris. Accessible independence results for Peano arithmetic. „Bull. London Math. Soc.”. 14 (1982), no. 4. s. 285–293.

Bibliografia

AleksanderA. Błaszczyk AleksanderA., SławomirS. Turek SławomirS., Teoria mnogości, Warszawa: Wydawnictwo Naukowe PWN, 2007, ISBN 978-83-01-15232-1, OCLC 189636646 .

[1] Laurie Kirby, Jeff Paris. Accessible independence results for Peano arithmetic. „Bull. London Math. Soc.”. 14 (1982), no. 4. s. 285–293.

[1]