Twierdzenie Goodsteina
W matematyce , a dokładniej w logice matematycznej , twierdzenie goodsteina jest arytmetyka oświadczenie odnoszące się do sekwencji , zwane sekwencje Goodstein . Sekwencje Goodsteina są niezwykle szybko rosnącymi początkowo ciągami liczb całkowitych , a twierdzenie stwierdza, że (wbrew pozorom) każdy ciąg Goodsteina kończy się na 0. Swoją nazwę zawdzięcza swojemu autorowi, matematykowi i logikowi Reubenowi Goodsteinowi .
Twierdzenia Goodsteina nie można wykazać w arytmetyce Peano pierwszego rzędu, ale można je wykazać w mocniejszych teoriach, takich jak teoria mnogości ZF (prosty dowód wykorzystuje liczby porządkowe aż do ) lub w arytmetyce drugiego rzędu . Twierdzenie daje zatem, w szczególnym przypadku arytmetyki pierwszego rzędu, przykład nierozstrzygalnego stwierdzenia, bardziej naturalny niż te otrzymane przez twierdzenia Gödla o niezupełności .
ε0{\ displaystyle \ varepsilon _ {0}}![\ varepsilon _ {0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acb0a8377db20e42274444cb181d51b5532b5844)
Definicja sekwencji Goodsteina
Przed zdefiniowaniem sekwencji Goodsteina, najpierw zdefiniujmy notację dziedziczenia o podstawie n . Aby zapisać naturalną liczbę całkowitą z taką notacją, najpierw piszemy ją w klasycznej postaci rozkładu o podstawie n :
wkniek+wk-1niek-1+⋯+w0{\ Displaystyle a_ {k} n ^ {k} + a_ {k-1} n ^ {k-1} + \ cdots + a_ {0}}![a_ {k} n ^ {k} + a _ {{k-1}} n ^ {{k- 1}} + \ cdots + a_ {0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b2f6eed5555a4b929f749b272d1be74ca22ec79)
gdzie każdy jest liczbą całkowitą z przedziału od 0 do n-1 . Następnie stosujemy to samo traktowanie do wykładników k , k-1 ,… iteracyjnie, aż otrzymamy wyrażenie składające się tylko z liczb całkowitych od 0 do n-1 .
wja{\ displaystyle a_ {i}}![mieć}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bc77764b2e74e64a63341054fa90f3e07db275f)
Na przykład liczba 35 jest zapisywana w podstawie 2 , a notacja dziedziczna (znana również jako iterowana punktacja ) na podstawie 2 .
25+2+1{\ Displaystyle 2 ^ {5} + 2 + 1}
222+1+21+1{\ Displaystyle 2 ^ {2 ^ {2} +1} + 2 ^ {1} +1}![{\ Displaystyle 2 ^ {2 ^ {2} +1} + 2 ^ {1} +1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/538a901a5e3ea4c169a916fa46dafbf43c9b0feb)
Ciąg Goodsteina liczby całkowitej m , oznaczonej przez G ( m ), jest zdefiniowany w następujący sposób: pierwszym elementem ciągu jest m . Aby otrzymać następujący element, piszemy m w notacji dziedzicznej o podstawie 2, następnie zmieniamy każde 2 na 3 i na koniec odejmujemy 1 od wyniku. Mamy wtedy drugi element sekwencji. Aby otrzymać trzeci, wpisujemy obliczony wcześniej element w notacji dziedzicznej o podstawie 3, zmieniamy 3 na 4 i odejmujemy 1. Kontynuujemy w ten sposób, aż otrzymamy 0 (co zawsze się dzieje, jak pokazano poniżej).
Bardziej formalnie, sekwencja jest określona przez iterację następujących dwóch operacji: w kroku n (przez pozowanie ):
sol(m){\ Displaystyle G (m)}
sol1(m)=m{\ Displaystyle G_ {1} (m) = m}![{\ Displaystyle G_ {1} (m) = m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c516cdde06ab2153a6b11f4170abcf28ba8fe633)
- Zapisz liczbę całkowitą w notacji dziedzicznej o podstawie n + 1 i zamień n + 1 na n + 2;solnie(m){\ Displaystyle G_ {n} (m)}
![{\ Displaystyle G_ {n} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a21238038e9c99c5ff1ec444cd919123ca31e0f2)
- Odejmij 1; w ten sposób otrzymujemy .solnie+1(m){\ displaystyle G_ {n + 1} (m)}
![{\ displaystyle G_ {n + 1} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ac78d977424e7e468bd9155b29a0689c0018629)
Stwierdzenie twierdzenia
Twierdzenie Goodsteina - Niezależnie od początkowej wartości m , ciąg Goodsteina G ( m ) kończy się na 0.
Przykłady apartamentów Goodstein
Pierwsze sequele Goodsteina szybko się kończą.
- Zatem dla G (1):
-
sol1{\ displaystyle G_ {1}}
(1) = 1,
-
sol2{\ displaystyle G_ {2}}
(1) = 1 - 1 = 0
- A dla G (2):
-
sol1{\ displaystyle G_ {1}}
(2) = 2 = 2 1
-
sol2{\ displaystyle G_ {2}}
(2) = 3 1 - 1 = 2
-
sol3{\ displaystyle G_ {3}}
(2) = 2 - 1 = 1
-
sol4{\ displaystyle G_ {4}}
(2) = 1 - 1 = 0
Ale sekwencje Goodsteina generalnie rosną podczas dużej liczby etapów, jak zobaczymy dokładniej w ostatniej sekcji . Na przykład sekwencje G (4) i G (5) zaczynają się w następujący sposób:
Wartość
|
Notacja dziedziczna
|
---|
4
|
2 2 |
26
|
2 3 2 + 2 3 + 2
|
41
|
2 4 2 + 2 4 + 1
|
60
|
2 5 2 + 2 5
|
83
|
2 6 2 + 6 + 5
|
109
|
2 7 2 + 7 + 4
|
|
...
|
253
|
2 11 2 + 11
|
299
|
2 12 2 + 11
|
|
...
|
1058
|
2 23 2 |
1151
|
24 2 + 23 24 + 23
|
|
...
|
|
|
Wartość
|
Notacja dziedziczna
|
---|
5
|
2 2 +1
|
27
|
3 3 |
255
|
3 4 3 + 3 4 2 + 3 4 + 3
|
467
|
3 5 3 + 3 5 2 + 3 5 + 2
|
775
|
3 6 3 + 3 6 2 + 3 6 + 1
|
1197
|
3 7 3 + 3 7 2 + 3 7
|
1751
|
3 8 3 + 3 8 2 + 2 8 + 7
|
|
...
|
10830
|
3 15 3 + 3 15 2 + 2 15
|
13087
|
3 16 3 + 3 16 2 + 16 + 15
|
|
...
|
92287
|
3 31 3 + 3 31 2 + 31
|
101407
|
3 32 3 + 3 32 2 + 31
|
|
...
|
762048
|
3 63 3 + 3 63 2 |
798719
|
3 64 3 + 2 64 2 + 63 64 + 63
|
|
...
|
|
- Jeśli chodzi o sekwencję G (4), zjawisko obserwowane dla zasad 6, 12 i 24 jest odtwarzane dla wszystkich zasad postaci p = 3 × 2 n : poprzednia wartość nie zawiera członu jednostkowego (człon (p- 1) 0 ), a zatem pojawia się w podstawie p człon potęgowy 0 równy (p-1), przy jednoczesnym zmniejszeniu o jedną jednostkę członu potęgowego 1 lub 2.
Zatem, gdy osiągniemy podstawę b = 3 × 2 27 - 1 = 402 653 183, człon ciągu jest równy b 2 = 162 129 585 780 031 489. Następnym składnikiem jest ( b + 1) 2 - 1 , to znaczy w bazie ( b + 1): b ( b + 1) + b , a zatem następujący wyraz będzie b ( b + 2) + b - 1 itd., tak że nie ma już żadnego terminu moc 2 lub większa w notacji dziedzicznej.
Gdy dochodzimy do podstawy B = ( b + 1) 2 b - 1 = 3 × 2 402653210 - 1, człon ciągu jest równy B (sekwencja była również stała od podstawy ( B + 1) / 2). Następna wartość to zatem B-1, to znaczy, że sekwencja w końcu zaczyna się zmniejszać i osiąga wartość zerową dla podstawy 2 B + 1 = 3 × 2 402 653 211 - 1 , czyli d 'gdzie indziej a Woodall ilość (bo 3 x 2 402 653 211 = 402 653 184 x 2 402653184 ). .
Podstawa, na której później G (4) kończy się ponad 120 milionami liczb, co oznacza, że liczba wyrazów ciągu G (4) jest rzędu 10 120 000 000 .
- Chociaż sekwencja G (5) nie rośnie dużo szybciej, trwa o wiele dłużej, a zwykłe notacje wykładnicze nie pozwalają nam już wyrazić największej osiągniętej podstawy. Pozowanie:
sol(nie)=nie2nie{\ Displaystyle g (n) = n2 ^ {n}}
solk=sol∘sol∘⋯∘sol{\ Displaystyle g ^ {k} = g \ circ g \ circ \ cdots \ circ g}![g ^ {k} = g \ circ g \ circ \ cdots \ circ g](https://wikimedia.org/api/rest_v1/media/math/render/svg/55d0e70370a8b3e96dffe1f0716b7ba8b7181e17)
k razy
M=sol3(64)=270+270+2702270{\ Displaystyle M = g ^ {3} (64) = 2 ^ {70 + 2 ^ {70} + 2 ^ {70} 2 ^ {2 ^ {70}}}}
NIE=solM(M), P.=solNIE(NIE), Q=solP.(P.),{\ Displaystyle N = g ^ {M} (M), \ P = g ^ {N} (N), \ Q = g ^ {P} (P),}
liczba wyrazów ciągu G (5) wynosi wtedy Q -2 (patrz ostatnia sekcja, aby zapoznać się z uzasadnieniem tego obliczenia). Liczby tej nie można dokładnie wyrazić za pomocą notacji strzałek Knutha , ale jest ona (w tym zapisie) rzędu 2 ↑ 6 lub znowu, używając funkcji Ackermanna , rzędu A (5, 4).
- Jednak te dwa przykłady nie dają jeszcze wystarczającego wyobrażenia o tym, jak szybko może rosnąć sekwencja Goodsteina. Zatem G (19) rośnie znacznie szybciej i zaczyna się następująco:
Pomimo tego szybkiego wzrostu (w kolejności od n n 7 , i to z wielu etapów znacznie większej niż ilość Graham ), sekwencja ostatecznie zmniejsza się do zera.
Dowód
Twierdzenie Goodsteina można zademonstrować (metodą, która jest poza arytmetyką Peano) za pomocą liczb porządkowych : biorąc pod uwagę liczbę całkowitą m i jej ciąg Goodsteina G ( m ), konstruujemy ciąg równoległy P ( m ) liczb porządkowych, tak że P ( m ) ściśle zmniejsza się i kończy. Tak samo będzie wtedy z kontynuacją Goodstein G ( m ), która może zakończyć się tylko wtedy, gdy zostanie anulowana.
Dokładniej, dla każdej liczby całkowitej n termin ciągu P ( m ) uzyskuje się przez zastosowanie transformacji na końcu ciągu Goodsteina o m w następujący sposób: bierzemy dziedziczną reprezentację o podstawie n +1 terminu , i każde wystąpienie n +1 zastępujemy pierwszą nieskończoną liczbą porządkową ω; więc na przykład i . Dodawanie, mnożenie i potęgowanie liczb porządkowych są dobrze zdefiniowane, a wynikiem jest liczba porządkowa reprezentowana w normalnej formie Cantora . Co więcej, kiedy wykonujemy zmianę bazy w sekwencji Goodsteina, aby przejść od do , otrzymujemy : jest to centralny punkt tej konstrukcji (na przykład ).
P.nie(m){\ displaystyle P_ {n} (m)}
fanie+1{\ displaystyle f_ {n + 1}}
solnie(m){\ Displaystyle G_ {n} (m)}
solnie(m){\ Displaystyle G_ {n} (m)}
sol1(3)=3=21+20{\ Displaystyle G_ {1} (3) = 3 = 2 ^ {1} + 2 ^ {0}}
P.1(3)=fa2(sol1(3))=ω1+ω0=ω+1{\ Displaystyle P_ {1} (3) = f_ {2} (G_ {1} (3)) = \ omega ^ {1} + \ omega ^ {0} = \ omega +1}
solnie(m){\ Displaystyle G_ {n} (m)}
solnie+1(m){\ displaystyle G_ {n + 1} (m)}
P.nie(m)=fanie+1(solnie(m))=fanie+2(solnie(m)){\ Displaystyle P_ {n} (m) = fa_ {n + 1} (G_ {n} (m)) = f_ {n + 2} (G_ {n} (m))}
fa4(3⋅444+3.40)=3ωωω+3=fa5(3⋅555+3){\ Displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3,4 ^ {0}) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3 = f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3)}![{\ Displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3,4 ^ {0}) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3 = f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/accfd09f766da276ef7f062af79910aa7ff088de)
Po odjęciu 1 będzie ściśle mniejsza niż :
P.nie+1(m)=fanie+2(solnie(m))-1=fanie+2(solnie+1(m)){\ Displaystyle P_ {n + 1} (m) = f_ {n + 2} (G_ {n} (m)) - 1 = f_ {n + 2} (G_ {n + 1} (m))}
P.nie(m){\ displaystyle P_ {n} (m)}![{\ displaystyle P_ {n} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31625db7317b61049867349ca95e2fe77739030f)
- kiedy normalna forma Cantora ma postać z , = . Więc jest ściśle większy niż ;P.nie(m){\ displaystyle P_ {n} (m)}
X+α.ω0{\ Displaystyle X + \ alfa. \ omega ^ {0}}
α≠0{\ displaystyle \ alpha \ neq 0}
P.nie+1(m){\ displaystyle P_ {n + 1} (m)}
P.nie(m){\ displaystyle P_ {n} (m)}
fa4(3⋅444+3)=3ωωω+3{\ Displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3}
fa5(3⋅555+3)-1)=3ωωω+2{\ Displaystyle f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3) -1) = 3 \ omega ^ {\ omega ^ {\ omega}} + 2}![{\ Displaystyle f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3) -1) = 3 \ omega ^ {\ omega ^ {\ omega}} + 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/03afd299b81a183593d1e2f9c40a6975c5e0349e)
- w ten sam sposób, gdy jest limitem porządkowym, jest ściśle gorszy, a więc jest ściśle wyższy od ;P.nie(m){\ displaystyle P_ {n} (m)}
P.nie+1(m){\ displaystyle P_ {n + 1} (m)}
fa4(3⋅44)=3ωω{\ Displaystyle f_ {4} (3 \ cdot 4 ^ {4}) = 3 \ omega ^ {\ omega}}
fa5(3⋅55-1)=fa5(2⋅54+4⋅53+4⋅52+4⋅51+4⋅50)=2⋅ω4+4⋅ω3+4⋅ω2+4⋅ω+4{\ Displaystyle f_ {5} (3 \ cdot 5 ^ {5} -1) = f_ {5} (2 \ cdot 5 ^ {4} +4 \ cdot 5 ^ {3} +4 \ cdot 5 ^ {2 } +4 \ cdot 5 ^ {1} +4 \ cdot 5 ^ {0}) = 2 \ cdot \ omega ^ {4} +4 \ cdot \ omega ^ {3} +4 \ cdot \ omega ^ {2} +4 \ cdot \ omega +4}![{\ Displaystyle f_ {5} (3 \ cdot 5 ^ {5} -1) = f_ {5} (2 \ cdot 5 ^ {4} +4 \ cdot 5 ^ {3} +4 \ cdot 5 ^ {2 } +4 \ cdot 5 ^ {1} +4 \ cdot 5 ^ {0}) = 2 \ cdot \ omega ^ {4} +4 \ cdot \ omega ^ {3} +4 \ cdot \ omega ^ {2} +4 \ cdot \ omega +4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/69878616bc858cadf62e8faf054c11a1d4d9298a)
- w obu przypadkach dochodzimy do wniosku, że ciąg równoległy P ( m ) ściśle maleje.
Po ustaleniu ścisłego spadku ciągu P ( m ) argument jest kontynuowany w następujący sposób: jeśli ciąg G ( m ) nie osiągnąłby 0, byłby nieskończony (ponieważ zawsze byłby zdefiniowany). Zatem P ( m ) również byłoby nieskończone (ponieważ zawsze byłoby zdefiniowane). Ale P ( m ) ściśle maleje; obecnie standardem kolejność < w zestawie porządkowych poniżej jest kolejność dobra , nie jest więc bezwzględnie zmniejszenie nieskończoną sekwencję liczb porządkowych lub, innymi słowy, każdy ściśle zmniejszenie sekwencja liczb porządkowych końcach i nie mogą w związku z tym być nieograniczone. Ta sprzeczność pokazuje, że ciąg G ( m ) kończy się i dlatego dochodzi do 0 (nawiasem mówiąc, ponieważ istnieje liczba naturalna k taka, że = 0, iz definicji P ( m ) również mamy = 0).
solk+1(m){\ displaystyle G_ {k + 1} (m)}
P.k+1(m){\ displaystyle P_ {k + 1} (m)}
ε0{\ displaystyle \ varepsilon _ {0}}
solk(m){\ Displaystyle G_ {k} (m)}
P.k(m){\ displaystyle P_ {k} (m)}![{\ displaystyle P_ {k} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcfeaf040ec713f95849f7e5e70d289d4e9d18d4)
Chociaż dowód twierdzenia Goodsteina jest stosunkowo łatwy, twierdzenie Laurence'a Kirby'ego i Jeffa Parisa, które stwierdza, że twierdzenia Goodsteina nie można udowodnić w arytmetyce Peano, jest techniczne i znacznie trudniejsze. Dowód Kirby'ego i Parisa wykorzystuje policzalne niestandardowe modele arytmetyki Peano, aby zredukować twierdzenie Goodsteina do twierdzenia Gentzena , co daje spójność arytmetyki przez indukcję aż do liczby porządkowej ε 0 (granica wyższa z liczb porządkowych użytych do udowodnienia twierdzenia Goodsteina twierdzenie).
Długość sekwencji jako funkcja wartości początkowej
Funkcja Goodstein , jest określona przez „ ma długość Goodstein sekwencji G ( n )” (to znaczy stosujące jako wszystkie pakiety Goodstein końcu). Wyjątkowo gwałtowny wzrost może być mierzone przez połączenie różnych funkcji hierarchii indeksowanych przez porządkowe, takie jak funkcje w hierarchii Hardy (w) , lub przy pomocy na szybko rosnące hierarchii z lob i Wainer:
sol:NIE→NIE{\ Displaystyle {\ mathcal {G}}: \ mathbb {N} \ to \ mathbb {N} \ \, \!}
sol(nie){\ Displaystyle {\ mathcal {G}} (n)}
sol{\ displaystyle {\ mathcal {G}} \, \!}
H.α{\ displaystyle H _ {\ alpha} \, \!}
faα{\ displaystyle f _ {\ alpha} \, \!}![f _ {\ alpha} \, \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/f734dfa8e00d082904b61eff0a65083eeaf4d6ea)
- Pokazali to Kirby i Paris (1982)
sol{\ displaystyle {\ mathcal {G}} \, \!}![{\ mathcal {G}} \, \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e490be527974ca05b195679c7ab1a5a930e7577)
rośnie mniej więcej tak szybko, jak (a zatem jak ); a dokładniej, dominuje nad wszystkim i dominuje
H.ε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}
faε0{\ displaystyle f _ {\ varepsilon _ {0}} \, \!}
sol{\ displaystyle {\ mathcal {G}} \, \!}
H.α{\ displaystyle H _ {\ alpha} \, \!}
α<ε0{\ Displaystyle \ alpha <\ varepsilon _ {0} \, \!}
H.ε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}
sol.{\ Displaystyle {\ mathcal {G}} \, \!.}![{\ mathcal {G}} \, \!.](https://wikimedia.org/api/rest_v1/media/math/render/svg/60d5867efca8cac9f546d4beb8780e1ca3c7feba)
(w przypadku dwóch funkcji mówimy, że dominuje, jeśli dla wszystkich jest wystarczająco duży). A dokładniej, Cichon (1983) to wykazał
fa,sol:NIE→NIE{\ Displaystyle f, g: \ mathbb {N} \ do \ mathbb {N} \, \!}
fa{\ Displaystyle f \, \!}
sol{\ displaystyle g \, \!}
fa(nie)>sol(nie){\ Displaystyle f (n)> g (n) \, \!}
nie{\ Displaystyle n \, \!}
sol(nie)=H.R2ω(nie+1)(1)-1,{\ Displaystyle {\ mathcal {G}} (n) = H_ {R_ {2} ^ {\ omega} (n + 1)} (1) -1,}![{\ mathcal {G}} (n) = H _ {{R_ {2} ^ {\ omega} (n + 1)}} (1) -1,](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fbcc1d05c5be45338ede84ef18f587f0fc75daf)
gdzie jest wynikiem zapisania n w notacji dziedzicznej o podstawie 2, a następnie zastąpienia wszystkich 2 przez ω (jak w dowodzie twierdzenia Goodsteina).
R2ω(nie){\ Displaystyle R_ {2} ^ {\ omega} (n)}
- Caicedo (2007) wykazali, że jeśli z czymnie=2m1+2m2+⋯+2mk{\ Displaystyle n = 2 ^ {m_ {1}} + 2 ^ {m_ {2}} + \ cdots + 2 ^ {m_ {k}}}
m1>m2>⋯>mk,{\ displaystyle m_ {1}> m_ {2}> \ cdots> m_ {k},}![m_ {1}> m_ {2}> \ cdots> m_ {k},](https://wikimedia.org/api/rest_v1/media/math/render/svg/771baf4748b87d17597a7c690c7bf2793b7fab79)
sol(nie)=faR2ω(m1)(faR2ω(m2)(⋯(faR2ω(mk)(3))⋯))-2{\ 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}![{\ 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](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fc41eb70640010c49e093330f7beb5819c1dbaa)
.
Oto kilka przykładów:
nie
|
sol(nie){\ Displaystyle {\ mathcal {G}} (n)}
|
---|
1
|
20{\ displaystyle 2 ^ {0}}
|
2-1{\ displaystyle 2-1}
|
H.ω(1)-1{\ Displaystyle H _ {\ omega} (1) -1}
|
fa0(3)-2{\ displaystyle f_ {0} (3) -2}
|
2
|
2
|
21{\ displaystyle 2 ^ {1}}
|
21+1-1{\ Displaystyle 2 ^ {1} + 1-1}
|
H.ω+1(1)-1{\ Displaystyle H _ {\ omega +1} (1) -1}
|
fa1(3)-2{\ displaystyle f_ {1} (3) -2}
|
4
|
3
|
21+20{\ Displaystyle 2 ^ {1} + 2 ^ {0}}
|
22-1{\ Displaystyle 2 ^ {2} -1}
|
H.ωω(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega}} (1) -1}
|
fa1(fa0(3))-2{\ displaystyle f_ {1} (f_ {0} (3)) - 2}
|
6
|
4
|
22{\ displaystyle 2 ^ {2}}
|
22+1-1{\ Displaystyle 2 ^ {2} + 1-1}
|
H.ωω+1(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega} +1} (1) -1}
|
faω(3)-2{\ displaystyle f _ {\ omega} (3) -2}
|
3 2 402 653 211 - 2
|
5
|
22+20{\ Displaystyle 2 ^ {2} + 2 ^ {0}}
|
22+2-1{\ Displaystyle 2 ^ {2} + 2-1}
|
H.ωω+ω(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega} + \ omega} (1) -1}
|
faω(fa0(3))-2{\ displaystyle f _ {\ omega} (f_ {0} (3)) - 2}
|
> A (5,4) (gdzie A to funkcja Ackermanna )
|
6
|
22+21{\ Displaystyle 2 ^ {2} + 2 ^ {1}}
|
22+2+1-1{\ Displaystyle 2 ^ {2} + 2 + 1-1}
|
H.ωω+ω+1(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega} + \ omega +1} (1) -1}
|
faω(fa1(3))-2{\ displaystyle f _ {\ omega} (f_ {1} (3)) - 2}
|
> A (7,6)
|
7
|
22+21+20{\ Displaystyle 2 ^ {2} + 2 ^ {1} + 2 ^ {0}}
|
22+1-1{\ Displaystyle 2 ^ {2 + 1} -1}
|
H.ωω+1(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega +1}} (1) -1}
|
faω(fa1(fa0(3)))-2{\ displaystyle f _ {\ omega} (f_ {1} (f_ {0} (3))) - 2}
|
> A (9,8)
|
8
|
22+1{\ Displaystyle 2 ^ {2 + 1}}
|
22+1+1-1{\ Displaystyle 2 ^ {2 + 1} + 1-1}
|
H.ωω+1+1(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega +1} +1} (1) -1}
|
faω+1(3)-2{\ displaystyle f _ {\ omega +1} (3) -2}
|
> A 3 (3,3) = A ( A (61, 61), A (61, 61))
|
⋮{\ displaystyle \ vdots}
|
12
|
22+1+22{\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2}}
|
22+1+22+1-1{\ Displaystyle 2 ^ {2 + 1} + 2 ^ {2} + 1-1}
|
H.ωω+1+ωω+1(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega +1} + \ omega ^ {\ omega} +1} (1) -1}
|
faω+1(faω(3))-2{\ displaystyle f _ {\ omega +1} (f _ {\ omega} (3)) - 2}
|
> f ω + 1 (64)> G, liczba Grahama
|
⋮{\ displaystyle \ vdots}
|
16
|
222{\ displaystyle 2 ^ {2 ^ {2}}}
|
222+1-1{\ Displaystyle 2 ^ {2 ^ {2}} + 1-1}
|
H.ωωω(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega ^ {\ omega}}} (1) -1}
|
faωω(3)-2{\ Displaystyle f _ {\ omega ^ {\ omega}} (3) -2}
|
> , liczba, którą można wyrazić tylko w notacji Conwaya z liczbą strzałek większą niż liczba Grahama .
faω2(sol){\ Displaystyle f _ {\ omega ^ {2}} (G)}![f _ {{\ omega ^ {{2}}}} (G)](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fcd6105acfc08f8330398e39c2a47fe7deba7d6) |
⋮{\ displaystyle \ vdots}
|
19
|
222+21+20{\ Displaystyle 2 ^ {2 ^ {2}} + 2 ^ {1} + 2 ^ {0}}
|
222+22-1{\ Displaystyle 2 ^ {2 ^ {2}} + 2 ^ {2} -1}
|
H.ωωω+ωω(1)-1{\ Displaystyle H _ {\ omega ^ {\ omega ^ {\ omega}} + \ omega ^ {\ omega}} (1) -1}
|
faωω(fa1(fa0(3)))-2{\ Displaystyle f _ {\ omega ^ {\ omega}} (f_ {1} (f_ {0} (3))) - 2}
|
|
(nierówności dotyczące funkcji Ackermanna A i liczby Grahama G są szczegółowo opisane w artykule „ Hierarchia szybkiego wzrostu” ).
Uogólnienia i analogiczne twierdzenia
Niech będzie ciągiem liczb całkowitych (które, jak możemy przypuszczać, są ściśle wzrastające, z ); możemy zdefiniować uogólnioną sekwencję Goodsteina, ustawiając i zapisując na każdym kroku dziedziczną notację podstawową , zastępując wszystkie przez i odejmując 1 od wyniku w celu uzyskania ; chociaż ta sekwencja może rosnąć znacznie szybciej niż zwykła sekwencja Goodsteina (odpowiadająca ), niezależnie od szybkości wzrostu ciągu , poprzedni dowód ma zastosowanie, a sekwencja zawsze kończy się na 0.
(bnie){\ displaystyle (b_ {n})}
b0=2{\ displaystyle b_ {0} = 2}
sol(m)(nie){\ Displaystyle G (m) (n)}
sol(m)(0)=m{\ Displaystyle G (m) (0) = m}
sol(m)(nie){\ Displaystyle G (m) (n)}
bnie{\ displaystyle b_ {n}}
bnie{\ displaystyle b_ {n}}
bnie+1{\ displaystyle b_ {n + 1}}
sol(m)(nie+1){\ Displaystyle G (m) (n + 1)}
bnie=nie+2{\ Displaystyle b_ {n} = n + 2}
(bnie){\ displaystyle (b_ {n})}![(b_n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ca3872ee8054312f21ff267bc6831745e42b9c9)
Paryż i Kirby skonstruowane podobnych apartamentów stosując model hydra inspirowany legendą Herkulesa walce 'z tej hydra Lerna . Są to drzewa, z których Herkules może wyciąć wierzchołek (głowę) przy każdym uderzeniu, co powoduje odrastanie dowolnej liczby drzew podrzędnych, ale na niższym poziomie; pokazujemy, zastępując każde drzewo liczbą porządkową (mniejszą niż ε 0 ), że otrzymane liczby porządkowe tworzą sekwencję malejącą, stąd wynik: jakkolwiek zła jest strategia Herkulesa i jak liczne odrastają głowy, hydra zawsze kończy bycie pokonanym; przy bardziej złożonych regułach odrastania głowy, analogiczne rozumowanie może również wymagać użycia liczebników porządkowych znacznie większych niż ε 0 .
Uwagi
-
(w) James M. Henle, An Outline of Set Theory ( czytaj online ) , str. 137-138.
-
Częstym błędem jest myślenie, że G ( m ) osiąga 0, ponieważ jest zdominowane przez P ( m ); w rzeczywistości, że P ( m ) dominuje G ( m ) nie odgrywa żadnej roli: centralnym punktem jest to, że istnieje wtedy i tylko wtedy , gdy istnieje (równoległość ciągów). Zatem jeśli P ( m ) się kończy, koniecznie również G ( m ). A G ( m ) może zakończyć się tylko osiągając 0.solk(m){\ Displaystyle G_ {k} (m)}
P.k(m){\ displaystyle P_ {k} (m)}
-
(i) L Kirby i J. Paryż , „ dostępne wyniki dla niezależność Peano arytmetyki ” , Buli. Londyn. Matematyka. Soc. , vol. 14,1982, s. 285-293 ( czytaj online ).
-
David Madore, „ Uczę się liczyć do ψ (εΩ + 1) i oswajać hydry ” , na http://www.madore.org ,16 marca 2008(dostęp 29 kwietnia 2019 ) .
Zobacz też
Bibliografia
- (en) R. Goodstein , „ O ograniczonym twierdzeniu porządkowym ” , J. Symb. Logika , vol. 9,1944, s. 33-41 ( DOI 10.2307 / 2268019 )
-
(en) EA Cichon , „ Krótki dowód dwóch niedawno odkrytych wyników niezależności przy użyciu rekurencyjnych metod teoretycznych ” , Proc. Natl. Gorzki. Matematyka. Soc. , vol. 87,1983, s. 704-706 ( czytaj online , dostęp 23 czerwca 2013 ).
-
(en) A. Caicedo , „ Goodstein's function ” , Revista Colombiana de Matemáticas , t. 41 N O 22007, s. 381-391 ( czytaj online , dostęp 23 czerwca 2013 ).
- Patrick Dehornoy , „ Czy nieskończoność jest konieczna? ", Pour la science , n o 278" Les infinis ",2000, s. 102-106 ( czytaj online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">