Twierdzenie Goodsteina - Goodstein's theorem

W logice matematycznej , twierdzenie goodsteina jest oświadczenie o liczb naturalnych , udowodnione przez Reuben Goodstein w 1944 roku, który stanowi, że każda sekwencja Goodstein ostatecznie kończy się na 0. Kirby i Paryżu pokazał, że jest nie do udowodnienia w Peano arytmetyki (ale to może być udowodnione w silniejsze systemy, takie jak arytmetyka drugiego rzędu ). To był trzeci przykład prawdziwego stwierdzenia, że jest nie do udowodnienia w arytmetyce Peano, po przykładów podanych przez niezupełności twierdzenia Gödla i Gerhard Gentzen bezpośredniego dowodu „s 1943 na unprovability z ε ₀ -Indukcja w arytmetyce Peano. Twierdzenie Parisa-Harringtona podało inny przykład.

Laurence Kirby i Jeff Paris wprowadzili graficzną grę hydrową o zachowaniu podobnym do sekwencji Goodsteina: „Hydra” (nazwana od mitologicznej wielogłowej Hydry Lerny ) jest ukorzenionym drzewem, a ruch polega na odcięciu jednego jej „głów” (gałąź drzewa), na które hydra odpowiada, wyhodując skończoną liczbę nowych głów zgodnie z pewnymi zasadami. Kirby i Paris udowodnili, że Hydra zostanie ostatecznie zabita, niezależnie od strategii, jaką Herkules używa do odrąbania jej głów, choć może to zająć bardzo dużo czasu. Podobnie jak w przypadku sekwencji Goodsteina, Kirby i Paris pokazali, że nie można tego udowodnić w samej arytmetyce Peano.

Dziedziczne Base- n oznaczenie

Sekwencje Goodstein są określone w zakresie koncepcji zwanych „dziedziczne Base- n zapis”. Notacja ta jest bardzo podobna do zwykłej zasadową- n systemy pozycyjne, ale zwykle notacja nie wystarcza dla celów twierdzenie goodsteina.

W zwykłym zapisie o podstawie n , gdzie n jest liczbą naturalną większą od 1, dowolną liczbę naturalną m zapisujemy jako sumę wielokrotności potęg n :

${\ Displaystyle m = a_ {k} n ^ {k} + a_ {k-1} n ^ {k-1} + \ cdots + a_ {0}}$

gdzie każdy współczynnik A _I spełnia 0 ≤ _i < N i _k ≠ 0 . Na przykład w bazie 2

${\ Displaystyle 35 = 32 + 2 + 1 = 2 ^ {5} + 2 ^ {1} + 2 ^ {0}.}$

Tak więc reprezentacja o podstawie 2 liczby 35 to 100011, co oznacza 2 ⁵ + 2 + 1 . Podobnie 100 reprezentowane w bazie 3 to 10201:

${\ Displaystyle 100 = 81 + 18 + 1 = 3 ^ {4} + 2 \ cdot 3 ^ {2} + 3 ^ {0}.}$

Należy pamiętać, że same wykładniki nie są napisane w wyjś- n notacji. Na przykład powyższe wyrażenia obejmują 2 ⁵ i 3 ⁴ oraz 5>2, 4>3.

Aby przekonwertować reprezentację n na dziedziczną notację n , najpierw przepisz wszystkie wykładniki w notacji n . Następnie przepisz dowolne wykładniki wewnątrz wykładników i kontynuuj w ten sposób, aż każda liczba występująca w wyrażeniu (z wyjątkiem samych podstaw) zostanie przekonwertowana na notację o podstawie n .

Na przykład, podczas gdy 35 w zwykłym zapisie o podstawie 2 to 2 ⁵ + 2 + 1 , jest zapisane w dziedzicznej notacji o podstawie 2 jako

${\ Displaystyle 35 = 2 ^ {2 ^ {2 ^ {1}} + 1} + 2 ^ {1} + 1,}$

korzystając z faktu, że 5 = 2 ² + 1. Podobnie 100 w dziedzicznej notacji o podstawie 3 to

${\ Displaystyle 100 = 3 ^ {3 ^ {1} + 1} + 2 \ cdot 3 ^ {2} + 1.}$

Sekwencje Goodsteina

Ciąg Goodsteina G ( m ) liczby m jest ciągiem liczb naturalnych. Pierwszym elementem ciągu G ( m ) jest samo m . Aby uzyskać drugie, G ( m )(2), napisz m w dziedzicznej notacji o podstawie 2, zmień wszystkie 2 na 3, a następnie odejmij 1 od wyniku. Ogólnie rzecz biorąc, ( n  + 1)-szy składnik , G ( m ) ( n  + 1) , sekwencji Goodsteina m jest następujący:

• Weźmy dziedziczną podstawę- n  + 1 reprezentację G ( m ) ( n ).
• Wymienić każde wystąpienie wyjś- n  + 1, z n  + 2 .
• Odejmij jeden. (Zauważ, że następny termin zależy zarówno od poprzedniego, jak i od indeksu n .)
• Kontynuuj, aż wynik wyniesie zero, w którym to momencie sekwencja się kończy.

Wczesne sekwencje Goodsteina szybko się kończą. Na przykład, G (3) kończy się w szóstym kroku:

Baza	Notacja dziedziczna	Wartość	Uwagi
2	${\displaystyle 2^{1}+1}$	3	Napisz 3 w notacji o podstawie 2
3	${\ Displaystyle 3 ^ {1} + 1-1 = 3 ^ {1}}$	3	Zmień 2 na 3, a następnie odejmij 1
4	${\ Displaystyle 4 ^ {1} -1 = 3}$	3	Zmień 3 na 4, a następnie odejmij 1. Teraz nie ma już 4s
5	${\ Displaystyle 3-1 = 2}$	2	Nie pozostało 4s do przełączenia na 5s. Po prostu odejmij 1
6	${\ Displaystyle 2-1 = 1}$	1	Brak 5s do przejścia na 6s. Po prostu odejmij 1
7	${\ Displaystyle 1-1 = 0}$	0	Nie pozostało 6s do przełączenia na 7s. Po prostu odejmij 1

Późniejsze sekwencje Goodsteina rosną dla bardzo dużej liczby kroków. Na przykład G (4) OEIS :  A056193 zaczyna się w następujący sposób:

Baza	Notacja dziedziczna	Wartość
2	${\ Displaystyle 2 ^ {2} ^ {1}}}$	4
3	${\ Displaystyle 3 ^ {3 ^ {1}} -1 = 2 \ cdot 3 ^ {2} +2 \ cdot 3 + 2}$	26
4	${\ Displaystyle 2 \ cdot 4 ^ {2} +2 \ cdot 4 + 1}$	41
5	${\ Displaystyle 2 \ cdot 5 ^ {2} +2 \ cdot 5}$	60
6	${\ Displaystyle 2 \ cdot 6 ^ {2} +2 \ cdot 6-1 = 2 \ cdot 6 ^ {2} + 6 + 5}$	83
7	${\ Displaystyle 2 \ cdot 7 ^ {2} + 7 + 4}$	109
${\displaystyle \vdots}$	${\displaystyle \vdots}$	${\displaystyle \vdots}$
11	${\ Displaystyle 2 \ cdot 11 ^ {2} + 11}$	253
12	${\ Displaystyle 2 \ cdot 12 ^ {2} + 12-1 = 2 \ cdot 12 ^ {2} + 11}$	299
${\displaystyle \vdots}$	${\displaystyle \vdots}$	${\displaystyle \vdots}$
24	${\ Displaystyle 2 \ cdot 24 ^ {2} -1 = 24 ^ {2} + 23 \ cdot 24 + 23}$	1151
${\displaystyle \vdots}$	${\displaystyle \vdots}$	${\displaystyle \vdots}$
${\ Displaystyle B = 3 \ cdot 2 ^ {402 \ 653 \ 209} -1}$	${\ Displaystyle 2 \ cdot B ^ {1}}$	${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 210} -2}$
${\ Displaystyle B = 3 \ cdot 2 ^ {402 \ 653 \ 209}}$	${\ Displaystyle 2 \ cdot B ^ {1}-1 = B ^ {1} + (B-1)}$	${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 210} -1}$
${\displaystyle \vdots}$	${\displaystyle \vdots}$	${\displaystyle \vdots}$

Elementy G (4) nadal rosną przez jakiś czas, ale u podstawy osiągają maksimum , pozostają tam do następnych kroków, a następnie rozpoczynają pierwsze opadanie. ${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 209}}$${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 210} -1}$${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 209}}$

Wartość 0 zostaje osiągnięta u podstawy . (Co ciekawe, jest to liczba Woodalla : . Tak samo jest ze wszystkimi innymi końcowymi podstawami dla wartości początkowych większych niż 4.) ${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 211} -1}$${\ Displaystyle 3 \ cdot 2 ^ {402 \ 653 \ 211} -1 = 402 \ 653 \ 184 \ cdot 2 ^ {402 \ 653 \ 184} -1}$

Jednak nawet G (4) nie daje dobrego wyobrażenia o tym, jak szybko mogą się zwiększać elementy ciągu Goodsteina. G (19) rośnie znacznie szybciej i zaczyna się następująco:

Notacja dziedziczna	Wartość
${\ Displaystyle 2 ^ {2 ^ {2}} + 2 + 1}$	19
${\ Displaystyle 3 ^ {3 ^ {3}} + 3}$	7 625 597 484 990
${\ Displaystyle 4 ^ {4 ^ {4}} + 3}$	${\ Displaystyle \ około 1,3 \ razy 10 ^ {154}}$
${\ Displaystyle 5 ^ {5 ^ {5}} + 2}$	${\ Displaystyle \ około 1,8 \ razy 10 ^ {2 \ 184}}$
${\ Displaystyle 6 ^ {6 ^ {6}} + 1}$	${\ Displaystyle \ około 2,6 \ razy 10 ^ {36 \ 305}}$
${\ Displaystyle 7 ^ {7 ^ {7}}}$	${\ Displaystyle \ około 3,8 \ razy 10 ^ {695 \ 974}}$
${\ Displaystyle 8 ^ {8 ^ {8}} -1 = 7 \ cdot 8 ^ {7 \ cdot 8 ^ {7} + 7 \ cdot 8 ^ {6} + 7 \ cdot 8 ^ {5} + 7 \ cpunkt 8^{4}+7\cpunkt 8^{3}+7\cpunkt 8^{2}+7\cpunkt 8+7}}$ ${\ Displaystyle + 7 \ cdot 8 ^ {7 \ cdot 8 ^ {7} + 7 \ cdot 8 ^ {6} + 7 \ cdot 8 ^ {5} + 7 \ cdot 8 ^ {4} + 7 \ cdot 8 ^{3}+7\cdot 8^{2}+7\cdot 8+6}+\cdot }$ ${\ Displaystyle + 7 \ cdot 8 ^ {8 + 2} + 7 \ cdot 8 ^ {8 + 1} + 7 \ cdot 8 ^ {8}}$ ${\ Displaystyle + 7 \ cdot 8 ^ {7} + 7 \ cdot 8 ^ {6} + 7 \ cdot 8 ^ {5} + 7 \ cdot 8 ^ {4}}$ ${\ Displaystyle + 7 \ cdot 8 ^ {3} + 7 \ cdot 8 ^ {2} + 7 \ cdot 8 + 7}$	${\ Displaystyle \ około 6 \ razy 10 ^ {15 \ 151 \ 335}}$
${\ Displaystyle 7 \ cdot 9 ^ {7 \ cdot 9 ^ {7} + 7 \ cdot 9 ^ {6} + 7 \ cdot 9 ^ {5} + 7 \ cdot 9 ^ {4} + 7 \ cdot 9 ^ {3}+7\cpunkt 9^{2}+7\cpunkt 9+7}}$ ${\ Displaystyle + 7 \ cdot 9 ^ {7 \ cdot 9 ^ {7} + 7 \ cdot 9 ^ {6} + 7 \ cdot 9 ^ {5} + 7 \ cdot 9 ^ {4} + 7 \ cdot 9 ^{3}+7\cdot 9^{2}+7\cdot 9+6}+\cdots }$ ${\ Displaystyle + 7 \ cdot 9 ^ {9 + 2} + 7 \ cdot 9 ^ {9 + 1} + 7 \ cdot 9 ^ {9}}$ ${\ Displaystyle + 7 \ cdot 9 ^ {7} + 7 \ cdot 9 ^ {6} + 7 \ cdot 9 ^ {5} + 7 \ cdot 9 ^ {4}}$ ${\ Displaystyle + 7 \ cdot 9 ^ {3} + 7 \ cdot 9 ^ {2} + 7 \ cdot 9 + 6}$	${\ Displaystyle \ około 5,6 \ razy 10 ^ {35 \ 942 \ 384}}$
${\displaystyle \vdots}$	${\displaystyle \vdots}$

Pomimo tego szybkiego wzrostu twierdzenie Goodsteina stwierdza, że każda sekwencja Goodsteina ostatecznie kończy się na 0 , bez względu na wartość początkową.

Dowód twierdzenia Goodsteina

Twierdzenie Goodsteina można udowodnić (za pomocą technik spoza arytmetyki Peano, patrz poniżej) w następujący sposób: Mając ciąg Goodsteina G ( m ), konstruujemy równoległy ciąg P ( m ) liczb porządkowych, który jest ściśle malejący i zakończony. Wtedy G ( m ) również musi się zakończyć i może się zakończyć tylko wtedy, gdy dojdzie do 0. Powszechnym nieporozumieniem tego dowodu jest przekonanie, że G ( m ) dochodzi do 0, ponieważ jest zdominowane przez P ( m ). Właściwie fakt, że P ( m ) dominuje nad G ( m ) nie odgrywa żadnej roli. Ważnym punktem jest to, że G ( m ) ( k ) istnieje wtedy i tylko wtedy, gdy P ( m ) ( k ) istnieje (równoległość). Następnie, jeśli P ( m ) kończy się, tak samo dzieje się z G ( m ). A G ( m ) może zakończyć się tylko wtedy, gdy dojdzie do 0.

Definiujemy funkcję, która oblicza dziedziczną reprezentację u podstawy k, a następnie zastępuje każde wystąpienie podstawy k pierwszą nieskończoną liczbą porządkową ω. Na przykład . ${\displaystyle f=f(u,k)}$${\ Displaystyle f (100,3) = f (3 ^ {3 ^ {1} + 1} + 2 \ cdot 3 ^ {2} + 1,3) = \ omega ^ {\ omega ^ {1} + 1 }+2\omega ^{2}+1=\omega ^{\omega +1}+2\omega ^{2}+1}$

Każdy termin P ( m )( n ) sekwencji P ( m ) jest następnie definiowany jako f ( G ( m )( n ), n+1 ). Na przykład G (3)(1) = 3 = 2 ¹ + 2 ⁰ i P (3)(1) = f (2 ¹ + 2 ⁰ ,2) = ω ¹ + ω ⁰ = ω + 1 . Dodawanie, mnożenie i potęgowanie liczb porządkowych są dobrze zdefiniowane.

Twierdzimy, że : ${\ Displaystyle f(G(m)(n),n+1)>f(G(m)(n+1),n+2)}$

Niech będzie G ( m ) ( n ) po zastosowaniu pierwszej operacji zmieniającej zasady w generowaniu następnego elementu ciągu Goodsteina, ale przed drugą operacją minus 1 w tym pokoleniu. Zauważ, że . ${\ Displaystyle G'(m) (n)}$${\ Displaystyle G (m) (n + 1) = G'(m) (n)-1}$

Następnie wyraźnie . Teraz stosujemy operację minus 1 i , as . Na przykład i , tak i , który jest ściśle mniejszy. Zauważ, że aby obliczyć f(G(m)(n),n+1) , musimy najpierw napisać G ( m )( n ) w dziedzicznej notacji bazowej n +1 , ponieważ na przykład wyrażenie albo nie ma sensu lub jest równy . ${\ Displaystyle f(G(m)(n),n+1)=f(G'(m)(n),n+2)}$${\ Displaystyle f(G'(m)(n),n+2)>f(G(m)(n+1),n+2)}$${\ Displaystyle G '(m) (n) = G (m) (n + 1) + 1}$${\ Displaystyle G (4) (1) = 2 ^ {2}}$${\ Displaystyle G (4) (2) = 2 \ cdot 3 ^ {2} +2 \ cdot 3 +2}$${\ Displaystyle f (2 ^ {2}, 2) = \ omega ^ {\ omega}}$${\ Displaystyle f (2 \ cdot 3 ^ {2} +2 \ cdot 3 +2, 3) = 2 \ omega ^ {2} +2 \ omega +2}$${\ Displaystyle \ omega ^ {\ omega} -1}$${\ Displaystyle \ omega ^ {\ omega}}$

Zatem ciąg P ( m ) jest ściśle malejący. Ponieważ standardowy porządek < na liczbach porządkowych jest dobrze ugruntowany , nieskończona ściśle malejąca sekwencja nie może istnieć, lub równoważnie, każda ściśle malejąca sekwencja liczb porządkowych kończy się (i nie może być nieskończona). Ale P ( m )( n ) jest obliczane bezpośrednio z G ( m )( n ). Stąd sekwencja G ( m ) również musi się kończyć, co oznacza, że ​​musi osiągnąć 0.

Chociaż ten dowód twierdzenia Goodsteina jest dość łatwy, twierdzenie Kirby-Parisa , które pokazuje, że twierdzenie Goodsteina nie jest twierdzeniem arytmetyki Peano, jest techniczne i znacznie trudniejsze. Wykorzystuje policzalne niestandardowe modele arytmetyki Peano.

Rozszerzone twierdzenie Goodsteina

Załóżmy, że definicja sekwencji Goodstein zostaje zmieniony tak, że zamiast zastępując każde wystąpienie bazy B z B +1 zastępuje go b +2 . Czy sekwencja nadal się kończy? Ogólnie rzecz biorąc, niech b ₁ , b ₂ , b ₃ , … będą dowolnymi ciągami liczb całkowitych. Następnie niech n +1-szy wyraz G ( m )( n +1) rozszerzonej sekwencji Goodsteina m będzie następujący: weź dziedziczną zasadę b _n reprezentację G ( m )( n ) i zastąp każde wystąpienie zasady b _n z b _{n +1,} a następnie odejmij jeden. Twierdzi się, że ta sekwencja nadal się kończy. Rozszerzony dowód definiuje P ( m )( n ) = f ( G ( m )( n ), n ) w następujący sposób: weź dziedziczną bazę b _n reprezentację G ( m )( n ) i zastąp każde wystąpienie bazy b _n z pierwszą nieskończoną liczbą porządkową ω. Operacja zmiany zasad sekwencji Goodsteina przy przechodzeniu z G ( m )( n ) do G ( m )( n +1) nadal nie zmienia wartości f . Na przykład, jeśli b _n = 4 i jeśli b _{n +1} = 9 , to , stąd liczba porządkowa jest ściśle większa niż liczba porządkowa${\ Displaystyle f (3 \ cdot 4 ^ {4 ^ {4}} + 4,4) = 3 \ omega ^ {\ omega ^ {\ omega}} + \ omega = f (3 \ cdot 9 ^ {9 ^ {9}}+9,9)}$${\ Displaystyle f (3 \ cdot 4 ^ {4 ^ {4}} + 4,4)}$${\ Displaystyle f ((3 \ cdot 9 ^ {9 ^ {9}} + 9 -1,9).}$

Długość sekwencji w funkcji wartości początkowej

Funkcja Goodsteina , , jest zdefiniowana w taki sposób, że jest to długość ciągu Goodsteina rozpoczynającego się od n . (Jest to funkcja całkowita, ponieważ każda sekwencja Goodsteina się kończy). Ekstremalne tempo wzrostu można skalibrować, odnosząc je do różnych standardowych hierarchii funkcji indeksowanych porządkowo, takich jak funkcje w hierarchii Hardy'ego i funkcje w szybkim - rosnąca hierarchia Löba i Wainera: ${\ Displaystyle {\ mathcal {G}}: \ mathbb {N} \ do \ mathbb {N}}$${\ Displaystyle {\ Mathcal {G}} (n)}$${\displaystyle {\mathcal {G}}}$${\ Displaystyle H_ {\ alfa}}$${\displaystyle f_{\alfa}}$

• Kirby i Paris (1982) udowodnili, że

${\displaystyle {\mathcal {G}}}$ma w przybliżeniu taką samą stopę wzrostu jak (która jest taka sama jak w ); dokładniej, dominuje dla każdego i dominuje${\ Displaystyle H_ {\ epsilon _ {0}}}$${\displaystyle f_{\epsilon_{0}}}$${\displaystyle {\mathcal {G}}}$${\ Displaystyle H_ {\ alfa}}$${\ Displaystyle \ alfa < \ epsilon _ {0}}$${\ Displaystyle H_ {\ epsilon _ {0}}}$${\displaystyle {\mathcal {G}}\\!.}$

(Dla dowolnych dwóch funkcji , mówi się, że dominuje, jeśli dla wszystkich wystarczająco dużych .)${\ Displaystyle f, g: \ mathbb {N} \ do \ mathbb {N}}$${\displaystyle f}$ ${\displaystyle g}$${\displaystyle f(n)>g(n)}$${\ Displaystyle n}$

• Cichon (1983) pokazał, że

${\ Displaystyle {\ mathcal {G}} (n) = H_ {R_ {2} ^ {\ omega} (n + 1)} (1) -1,}$

gdzie jest wynikiem umieszczenia n w dziedzicznej notacji o podstawie 2, a następnie zastąpienia wszystkich 2 przez ω (jak zrobiono w dowodzie twierdzenia Goodsteina).${\ Displaystyle R_ {2} ^ {\ omega} (n)}$

• Caicedo (2007) pokazał, że jeśli z wtedy${\ Displaystyle n = 2 ^ {m_ {1}} +2 ^ {m_ {2}} + \ cdots +2 ^ {m_ {k}}}$${\displaystyle m_{1}>m_{2}>\cdots>m_{k},}$

${\ Displaystyle {\ mathcal {G}} (n) = f_ {R_ {2} ^ {\ omega} (m_ {1})} (f_ {R_ {2} ^ {\ omega} (m_ {2}) }(\cdots (f_{R_{2}^{\omega }(m_{k})}(3))\cdots ))-2}$.

Kilka przykładów:

n			${\ Displaystyle {\ Mathcal {G}} (n)}$
1	${\displaystyle 2^{0}}$	${\ Displaystyle 2-1}$	${\ Displaystyle H_ {\ omega} (1)-1}$	${\displaystyle f_{0}(3)-2}$	2
2	${\ Displaystyle 2 ^ {1}}$	${\ Displaystyle 2 ^ {1} + 1-1}$	${\ Displaystyle H_ {\ omega +1} (1)-1}$	${\displaystyle f_{1}(3)-2}$	4
3	${\ Displaystyle 2 ^ {1} +2 ^ {0}}$	${\ Displaystyle 2 ^ {2}-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega}} (1)-1}$	${\displaystyle f_{1}(f_{0}(3))-2}$	6
4	${\ Displaystyle 2 ^ {2}}$	${\ Displaystyle 2 ^ {2} + 1-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega} +1} (1)-1}$	${\displaystyle f_{\omega}(3)-2}$	3,2 402653211 − 2 6,895080803×10 121210694
5	${\ Displaystyle 2 ^ {2} +2 ^ {0}}$	${\ Displaystyle 2 ^ {2} + 2-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega} + \ omega} (1) -1}$	${\displaystyle f_{\omega}(f_{0}(3))-2}$	> A (4,4) > 10 10 10 19728
6	${\ Displaystyle 2 ^ {2} +2 ^ {1}}$	${\ Displaystyle 2 ^ {2} +2 + 1-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega} + \ omega +1} (1)-1}$	${\displaystyle f_{\omega}(f_{1}(3))-2}$	> A (6,6)
7	${\ Displaystyle 2 ^ {2} +2 ^ {1} +2 ^ {0}}$	${\ Displaystyle 2 ^ {2 + 1} -1}$	${\ Displaystyle H_ {\ omega ^ {\ omega +1}} (1)-1}$	${\displaystyle f_{\omega}(f_{1}(f_{0}(3)))-2}$	> A (8,8)
8	${\ Displaystyle 2 ^ {2 + 1}}$	${\ Displaystyle 2 ^ {2 + 1} + 1-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega +1} +1} (1) -1}$	${\ Displaystyle f_ {\ omega +1} (3)-2}$	> A 3 (3,3) = A ( A (61, 61), A (61, 61))
${\displaystyle \vdots}$
12	${\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2}}$	${\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2} + 1-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega +1} + \ omega ^ {\ omega} +1} (1) -1}$	${\ Displaystyle f_ {\ omega +1} (f_ {\ omega} (3)) -2}$	> f ω+1 (64) > liczba Grahama
${\displaystyle \vdots}$
19	${\ Displaystyle 2 ^ {2} ^ {2}} +2 ^ {1} +2 ^ {0}}$	${\ Displaystyle 2 ^ {2 ^ {2}} +2 ^ {2}-1}$	${\ Displaystyle H_ {\ omega ^ {\ omega ^ {\ omega}} + \ omega ^ {\ omega}} (1) (1) -1}$	${\ Displaystyle f_ {\ omega ^ {\ omega}} (f_ {1} (f_ {0}(3)))-2}$

(Dla funkcji Ackermanna i granic liczbowych Grahama patrz szybko rosnąca hierarchia#Funkcje w szybko rosnących hierarchiach ).

Zastosowanie do funkcji obliczalnych

Twierdzenie Goodsteina może być użyte do skonstruowania całkowitej obliczalnej funkcji, której arytmetyka Peano nie może udowodnić, że jest całkowita. Sekwencja Goodsteina liczby może być skutecznie wyliczona przez maszynę Turinga ; w ten sposób funkcja, która odwzorowuje n na liczbę kroków wymaganych do zakończenia sekwencji Goodsteina n, jest obliczana przez konkretną maszynę Turinga. Ta maszyna po prostu wylicza sekwencję Goodsteina n, a gdy sekwencja osiągnie 0 , zwraca długość sekwencji. Ponieważ każda sekwencja Goodsteina ostatecznie się kończy, ta funkcja jest całkowita. Ale ponieważ arytmetyka Peano nie dowodzi, że każda sekwencja Goodsteina się kończy, arytmetyka Peano nie dowodzi, że ta maszyna Turinga oblicza funkcję całkowitą.

Zobacz też

• Niestandardowy model arytmetyki
• Szybko rosnąca hierarchia
• Twierdzenie Parisa-Harringtona
• Twierdzenie Kanamori-McAloon
• Twierdzenie Kruskala o drzewie

Bibliografia

Bibliografia

• Goodstein, R. (1944), "O ograniczonym twierdzeniu porządkowym", Journal of Symbolic Logic , 9 (2): 33-41, doi : 10.2307/2268019 , JSTOR  2268019 , S2CID  235597.
• Cichon, E. (1983), „Krótki dowód dwóch niedawno odkrytych wyników niezależności przy użyciu rekurencyjnych metod teoretycznych”, Proceedings of the American Mathematical Society , 87 (4): 704-706, doi : 10.2307/2043364 , JSTOR  2043364.
• Caicedo, A. (2007), "funkcja Goodsteina" (PDF) , Revista Colombiana de Matemáticas , 41 (2): 381-391.

Zewnętrzne linki

• Weisstein, Eric W. „Sekwencja Goodsteina” . MatematykaŚwiat .
• Niektóre elementy dowodu, że twierdzenie Goodsteina nie jest twierdzeniem PA, z pracy licencjackiej Justina T Millera
• Klasyfikacja niestandardowych modeli arytmetyki Peano według twierdzenia Goodsteina - Teza Dana Kaplana, Franklana i Marshall College Library
• Definicja sekwencji Goodsteina w Haskell i rachunku lambda
• Gra Hydra zaimplementowana jako aplet Java
• Implementacja JavaScript wariantu gry Hydra
• Goodstein Sequences: The Power of a Detour via Infinity - dobra ekspozycja z ilustracjami Goodstein Sequences i grą hydra.
• Kalkulator Goodsteina