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 w 1982 roku Jeff Paris i Laurie Kirby.
Popularne sformułowanie Wybierzmy liczbę naturalną m(0), na przykład 1077:
zapiszmy tę liczbę w postaci potęg dwójki:
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:
Zamieńmy w powyższym wyrażeniu wszystkie liczby 2 na liczbę 3:
przyjmijmy, że czyli:
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: ). Pośrednie wyrazy dla liczby 1077 osiągają wartości rzędu 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
Bibliografia
Goodsteina