Twierdzenie Goodsteina

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Twierdzenie Goodsteinatwierdzenie 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 Peano, co udowodnili[1] w 1982 roku Jeff Paris i Laurie Kirby.

Popularne sformułowanie[edytuj | edytuj kod]

  • 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)^{\prime}= 3^{3^{3+1}+3} + 3^{3^3+1} + 3^{3^3} + 3^3 +1
  • przyjmijmy że m(1) = m(0)^{\prime} - 1 czyli:
m(1) =  m(0)^{\prime}-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. 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 Peano, 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

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

Bibliografia[edytuj | edytuj kod]