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.

Przypisy

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