Goodsteinova věta
V matematice a přesněji v matematické logice je Goodsteinova věta aritmetickým výrokem týkajícím se sekvencí , který se nazývá Goodsteinovy sekvence . Goodsteinovy sekvence jsou extrémně rychlé zpočátku rostoucí sekvence celých čísel a teorém uvádí, že (navzdory zdání) každá Goodsteinova sekvence končí číslem 0. Za své jméno vděčí svému autorovi, matematikovi a logikovi Reubenovi Goodsteinovi .
Goodsteinova věta není prokazatelná v aritmetice Peano prvního řádu, ale lze ji demonstrovat v silnějších teoriích, jako je teorie množin ZF (jednoduchý důkaz používá ordinály až ), nebo aritmetika druhého řádu . Věta tedy dává, v konkrétním případě aritmetiky prvního řádu, příklad nerozhodnutelného tvrzení přirozenějšího než tvrzení získaná Gödelovými teorémami o neúplnosti .
ε0{\ displaystyle \ varepsilon _ {0}}
Definice sekvence Goodstein
Před definováním sekvence Goodstein si nejprve definujeme základní dědičnou notaci . Chcete-li napsat přirozené celé číslo s takovým zápisem, napíšeme ho nejprve klasickou formou dekompozice base- n :
naknek+nak-1nek-1+⋯+na0{\ displaystyle a_ {k} n ^ {k} + a_ {k-1} n ^ {k-1} + \ cdots + a_ {0}}kde každé je celé číslo mezi 0 a n-1 . Poté aplikujeme stejné zacházení na exponenty k , k-1 , ... iterativně, dokud nezískáme výraz skládající se pouze z celých čísel mezi 0 a n-1 .
nai{\ displaystyle a_ {i}}
Například 35 je napsáno v základně 2 a dědičná notace (známá také jako bodování iterované ) základna 2 .
25+2+1{\ displaystyle 2 ^ {5} + 2 + 1}222+1+21+1{\ displaystyle 2 ^ {2 ^ {2} +1} + 2 ^ {1} +1}
Goodstein sekvence celé číslo m , označený G ( m ), je definována následovně: první prvek sekvence je m . Abychom získali následující prvek, zapíšeme m dědičnou notaci do základny 2, poté každé 2 změníme na 3 a nakonec od výsledku odečteme 1. Pak máme druhý prvek sekvence. Abychom získali třetí, zapíšeme prvek dříve vypočítaný v dědičné notaci do základny 3, změníme 3 s na 4 a odečteme 1. Takto pokračujeme, dokud nezískáme 0 (což se vždy stane, jak je znázorněno níže).
Formálně je posloupnost definována iterací následujících dvou operací: v kroku n (pózováním ):
G(m){\ displaystyle G (m)}G1(m)=m{\ displaystyle G_ {1} (m) = m}
- Celé číslo zapište dědičnou notací do základny n + 1 a nahraďte n + 1 n + 2;Gne(m){\ displaystyle G_ {n} (m)}
- Odečíst 1; takto se dostaneme .Gne+1(m){\ displaystyle G_ {n + 1} (m)}
Výrok věty
Goodsteinova věta - Ať už je počáteční hodnota m jakákoli , Goodsteinova sekvence G ( m ) končí 0.
Příklady apartmánů Goodstein
Goodsteinova první pokračování rychle končí.
- Pro G (1) tedy:
-
G1{\ displaystyle G_ {1}}(1) = 1,
-
G2{\ displaystyle G_ {2}}(1) = 1 - 1 = 0
- A pro G (2):
-
G1{\ displaystyle G_ {1}}(2) = 2 = 2 1
-
G2{\ displaystyle G_ {2}}(2) = 3 1 - 1 = 2
-
G3{\ displaystyle G_ {3}}(2) = 2 - 1 = 1
-
G4{\ displaystyle G_ {4}}(2) = 1 - 1 = 0
Ale sekvence Goodstein obecně rostou během velkého počtu fází, jak uvidíme přesněji v poslední části . Například sekvence G (4) a G (5) začínají následovně:
Hodnota
|
Dědičná notace
|
---|
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
|
|
...
|
|
|
Hodnota
|
Dědičná notace
|
---|
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
|
|
...
|
|
- Pokud jde o posloupnost G (4), jev pozorovaný pro báze 6, 12 a 24 je reprodukován pro všechny báze ve tvaru p = 3 × 2 n : předchozí hodnota nezahrnuje jednotkový člen (člen (p- 1) 0 ), a proto se v základu p zobrazuje výkonový člen 0 rovný (p-1), se současným snížením výkonového členu 1 nebo 2 o jednu jednotku.
Když tedy dosáhneme základny b = 3 × 2 27 - 1 = 402 653 183, člen posloupnosti se rovná b 2 = 162 129 585 780 031 489. Další člen je ( b + 1) 2 - 1 , tj. v základu ( b + 1): b ( b + 1) + b , a následující člen bude tedy b ( b + 2) + b - 1 atd., takže již nebude existovat žádný člen síla 2 nebo vyšší v dědičné notaci.
Když dosáhneme základny B = ( b + 1) 2 b - 1 = 3 × 2 402 653 210 - 1, člen posloupnosti se rovná B (posloupnost byla také konstantní ze základny ( B + 1) / 2). Další hodnota je tedy B-1, to znamená, že posloupnost se konečně začne snižovat a dosáhne nulové hodnoty pro základnu 2 B + 1 = 3 × 2 402 653 211 - 1 , což je d 'jinde a Woodall číslo (protože 3 × 2 402 653 211 = 402 653 184 × 2 402653184 ). .
Základ, na kterém později G (4) končí s více než 120 miliony čísel, což znamená, že počet členů posloupnosti G (4) je řádově 10 120 000 000 .
- Přestože posloupnost G (5) neroste mnohem rychleji, roste o tolik déle a obvyklé exponenciální notace nám již neumožňují vyjádřit největší dosaženou základnu. Pózování:
G(ne)=ne2ne{\ displaystyle g (n) = n2 ^ {n}}
Gk=G∘G∘⋯∘G{\ displaystyle g ^ {k} = g \ circ g \ circ \ cdots \ circ g} k krát
M=G3(64)=270+270+2702270{\ displaystyle M = g ^ {3} (64) = 2 ^ {70 + 2 ^ {70} + 2 ^ {70} 2 ^ {2 ^ {70}}}}
NE=GM(M), P=GNE(NE), Q=GP(P),{\ displaystyle N = g ^ {M} (M), \ P = g ^ {N} (N), \ Q = g ^ {P} (P),}
počet členů posloupnosti G (5) je pak Q - 2 (zdůvodnění tohoto výpočtu viz poslední část). Toto číslo nelze přesně vyjádřit pomocí Knuthovy šipkové notace , ale je (v této notaci) řádu 2 ↑↑↑ 6, nebo opět pomocí Ackermannovy funkce řádu A (5, 4).
- Tyto dva příklady však zatím neposkytují dostatečnou představu o tom, jak rychle může Goodsteinova sekvence růst. Tak, G (19) roste mnohem rychleji a začíná takto:
I přes tento rychlý růst (v řádu o n n 7 , a to pro řadu kroků, mnohem větší , než je počet Graham ), sekvence nakonec klesne na nulu.
Důkaz
Goodsteinovu větu lze demonstrovat (metodou, která je mimo Peanovu aritmetiku) pomocí ordinálů : vzhledem k celému číslu m a jeho Goodsteinově posloupnosti G ( m ) vytvoříme paralelní posloupnost P ( m ) ordinálů tak, že P ( m ) striktně klesá a končí. Pak to bude stejné pro pokračování Goodsteinu G ( m ), které může skončit až po jeho zrušení.
Přesněji řečeno, pro každé celé číslo n je člen posloupnosti P ( m ) získán aplikací transformace na konec Goodsteinovy posloupnosti m následujícím způsobem: vezmeme dědičné zastoupení v základu n +1 pojmu a nahradíme každý výskyt n +1 prvním nekonečným pořadovým číslem, ω; tak například a . Sčítání, násobení a umocňování ordinálních čísel je dobře definováno a výsledkem je ordinál reprezentovaný v Cantorově normální formě . Navíc, když provádíme základní změnu v Goodsteinově sekvenci, která má jít od do , máme : je to ústřední bod této konstrukce (například ).
Pne(m){\ displaystyle P_ {n} (m)}Fne+1{\ displaystyle f_ {n + 1}}Gne(m){\ displaystyle G_ {n} (m)}Gne(m){\ displaystyle G_ {n} (m)}G1(3)=3=21+20{\ displaystyle G_ {1} (3) = 3 = 2 ^ {1} + 2 ^ {0}}P1(3)=F2(G1(3))=ω1+ω0=ω+1{\ displaystyle P_ {1} (3) = f_ {2} (G_ {1} (3)) = \ omega ^ {1} + \ omega ^ {0} = \ omega +1}Gne(m){\ displaystyle G_ {n} (m)}Gne+1(m){\ displaystyle G_ {n + 1} (m)}Pne(m)=Fne+1(Gne(m))=Fne+2(Gne(m)){\ displaystyle P_ {n} (m) = f_ {n + 1} (G_ {n} (m)) = f_ {n + 2} (G_ {n} (m))}F4(3⋅444+3.40)=3ωωω+3=F5(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)}
Po odečtení 1 bude přísně méně než :
Pne+1(m)=Fne+2(Gne(m))-1=Fne+2(Gne+1(m)){\ displaystyle P_ {n + 1} (m) = f_ {n + 2} (G_ {n} (m)) - 1 = f_ {n + 2} (G_ {n + 1} (m))}Pne(m){\ displaystyle P_ {n} (m)}
- když Cantorova normální forma je ve tvaru s , = . Takže je přísně větší než ;Pne(m){\ displaystyle P_ {n} (m)}X+α.ω0{\ displaystyle X + \ alpha. \ omega ^ {0}}α≠0{\ displaystyle \ alpha \ neq 0}Pne+1(m){\ displaystyle P_ {n + 1} (m)}Pne(m){\ displaystyle P_ {n} (m)}F4(3⋅444+3)=3ωωω+3{\ displaystyle f_ {4} (3 \ cdot 4 ^ {4 ^ {4}} + 3) = 3 \ omega ^ {\ omega ^ {\ omega}} + 3}F5(3⋅555+3)-1)=3ωωω+2{\ displaystyle f_ {5} (3 \ cdot 5 ^ {5 ^ {5}} + 3) -1) = 3 \ omega ^ {\ omega ^ {\ omega}} + 2}
- stejným způsobem, když je limita řadová, je přísně nižší, tedy je přísně vyšší než ;Pne(m){\ displaystyle P_ {n} (m)}Pne+1(m){\ displaystyle P_ {n + 1} (m)}F4(3⋅44)=3ωω{\ displaystyle f_ {4} (3 \ cdot 4 ^ {4}) = 3 \ omega ^ {\ omega}}F5(3⋅55-1)=F5(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}
- v obou případech jsme dospěli k závěru, že paralelní posloupnost P ( m ) striktně klesá.
Jakmile je stanoveno přísné snížení posloupnosti P ( m ), argument pokračuje následovně: kdyby posloupnost G ( m ) nedosáhla 0, byla by nekonečná (protože by byla vždy definována). Takže P ( m ) by bylo také nekonečné (protože by také bylo vždy definováno). Ale P ( m ) se přísně snižuje; nyní standardní řád < na množině ordinálů menší než je dobrý řád , neexistuje tedy striktně klesající nekonečná posloupnost ordinálů , nebo jinými slovy, jakákoli striktně klesající posloupnost ordinálů končí a nemůže být tedy nekonečná. Tento rozpor ukazuje, že posloupnost G ( m ) končí a proto dosahuje 0 (mimochodem, protože existuje přirozené celé číslo k takové, že = 0, a podle definice P ( m ) máme také = 0).
Gk+1(m){\ displaystyle G_ {k + 1} (m)}Pk+1(m){\ displaystyle P_ {k + 1} (m)}ε0{\ displaystyle \ varepsilon _ {0}}Gk(m){\ displaystyle G_ {k} (m)}Pk(m){\ displaystyle P_ {k} (m)}
Zatímco důkaz Goodsteinovy věty je poměrně snadný, věta Laurence Kirbyho a Jeffa Paříže, která uvádí, že Goodsteinovu větu nelze v Peanově aritmetice dokázat, je technická a podstatně obtížnější. Důkaz Kirbyho a Paříže využívá spočítatelné nestandardní modely Peanovy aritmetiky k redukci Goodsteinovy věty na Gentzenovu větu , která dává konzistenci aritmetiky indukcí až k ordinální hodnotě ε 0 (horní hranice ordinálů použitých pro důkaz Goodsteinovy věty teorém).
Délka sekvence jako funkce počáteční hodnoty
Funkce Goodstein , je definována „ je délka Goodstein sekvence G ( n )“ (který se uplatňuje , jako všechny apartmány Goodstein konci). Velmi rychlý růst může být měřena pomocí připojení k různým hierarchie funkcí indexovaných ordinals, jako jsou funkce v hierarchii Hardy (v) , nebo funkce v rychle rostoucí hierarchie LOB a Wainer:
G:NE→NE{\ displaystyle {\ mathcal {G}}: \ mathbb {N} \ do \ mathbb {N} \, \!}G(ne){\ displaystyle {\ mathcal {G}} (n)}G{\ displaystyle {\ mathcal {G}} \, \!}Hα{\ displaystyle H _ {\ alpha} \, \!} Fα{\ displaystyle f _ {\ alpha} \, \!}
- Ukázali to Kirby a Paris (1982)
G{\ displaystyle {\ mathcal {G}} \, \!}roste přibližně tak rychle jako (a tedy jako ); přesněji dominuje všemu a dominuje
Hε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}Fε0{\ displaystyle f _ {\ varepsilon _ {0}} \, \!}G{\ displaystyle {\ mathcal {G}} \, \!}Hα{\ displaystyle H _ {\ alpha} \, \!}α<ε0{\ displaystyle \ alpha <\ varepsilon _ {0} \, \!}Hε0{\ displaystyle H _ {\ varepsilon _ {0}} \, \!}G.{\ displaystyle {\ mathcal {G}} \, \!.}
(pro dvě funkce říkáme, že dominuje, pokud pro všechny dostatečně velké). Přesněji řečeno, Cichon (1983) to ukázal
F,G:NE→NE{\ displaystyle f, g: \ mathbb {N} \ až \ mathbb {N} \, \!}F{\ displaystyle f \, \!} G{\ displaystyle g \, \!}F(ne)>G(ne){\ displaystyle f (n)> g (n) \, \!}ne{\ displaystyle n \, \!}
G(ne)=HR2ω(ne+1)(1)-1,{\ displaystyle {\ mathcal {G}} (n) = H_ {R_ {2} ^ {\ omega} (n + 1)} (1) -1,}
kde je výsledek zápisu n v dědičném zápisu základny 2, poté nahrazení všech 2 znakem ω (jako v důkazu Goodsteinovy věty).
R2ω(ne){\ displaystyle R_ {2} ^ {\ omega} (n)}
- Caicedo (2007) ukázal, že pokud se poténe=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},}
G(ne)=FR2ω(m1)(FR2ω(m2)(⋯(FR2ω(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}.
Zde jsou nějaké příklady :
ne
|
G(ne){\ displaystyle {\ mathcal {G}} (n)}
|
---|
1
|
20{\ displaystyle 2 ^ {0}}
|
2-1{\ displaystyle 2-1}
|
Hω(1)-1{\ displaystyle H _ {\ omega} (1) -1}
|
F0(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}
|
F1(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}
|
F1(F0(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}
|
Fω(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}
|
Fω(F0(3))-2{\ displaystyle f _ {\ omega} (f_ {0} (3)) - 2}
|
> A (5,4) (kde A je Ackermannova funkce )
|
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}
|
Fω(F1(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}
|
Fω(F1(F0(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}
|
Fω+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}
|
Fω+1(Fω(3))-2{\ displaystyle f _ {\ omega +1} (f _ {\ omega} (3)) - 2}
|
> f ω + 1 (64)> G, Grahamovo číslo
|
⋮{\ 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}
|
Fωω(3)-2{\ displaystyle f _ {\ omega ^ {\ omega}} (3) -2}
|
> , číslo, které lze vyjádřit pouze v Conwayově zápisu s počtem šipek větším než Grahamovo číslo .
Fω2(G){\ displaystyle f _ {\ omega ^ {2}} (G)} |
⋮{\ 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}
|
Fωω(F1(F0(3)))-2{\ displaystyle f _ {\ omega ^ {\ omega}} (f_ {1} (f_ {0} (3))) - 2}
|
|
(nerovnosti zahrnující Ackermannovu funkci A a Grahamovo číslo G jsou podrobně popsány v hierarchii rychlého růstu článku ).
Zobecnění a analogické věty
Dovolit být posloupnost celých čísel (u kterých můžeme předpokládat, že se budou přísně zvyšovat ); můžeme definovat všeobecný sekvenci Goodstein nastavením a psaní na každém kroku v dědičném základním zápisu , nahradí všechny aplikace , a odečtením 1 z výsledku se získá ; i když tato sekvence může růst mnohem rychleji než obvyklá Goodsteinova sekvence (odpovídající ), bez ohledu na rychlost růstu sekvence platí předchozí důkaz a posloupnost vždy končí na 0.
(bne){\ displaystyle (b_ {n})}b0=2{\ displaystyle b_ {0} = 2}G(m)(ne){\ displaystyle G (m) (n)}G(m)(0)=m{\ displaystyle G (m) (0) = m}G(m)(ne){\ displaystyle G (m) (n)}bne{\ displaystyle b_ {n}}bne{\ displaystyle b_ {n}}bne+1{\ displaystyle b_ {n + 1}}G(m)(ne+1){\ displaystyle G (m) (n + 1)}bne=ne+2{\ displaystyle b_ {n} = n + 2}(bne){\ displaystyle (b_ {n})}
Paris a Kirby postavena podobné apartmány s využitím modelu Hydra inspirovaný legendou Hercules 'boje s na Hydra z Lerna . Jedná se o stromy, ze kterých může Hercules při každém úderu vyříznout vrchol (hlavu), což způsobí, že libovolný počet dílčích stromů doroste, ale na nižší úrovni; prokazujeme nahrazením každého stromu ordinálem (méně než ε 0 ), že získané ordinály tvoří klesající posloupnost, proto výsledek: jakkoli špatná může být Herkulesova strategie a jakkoli mnoho hlav, které dorůstají, hydra vždy končí být poražen; se složitějšími pravidly pro opětovný růst hlavy může analogické uvažování také vyžadovat použití ordinálů mnohem větších než ε 0 .
Poznámky
-
(in) James M. Henle, Nástin teorie množin ( číst online ) , s. 137-138.
-
Častou chybou je myslet si, že G ( m ) dosáhne 0, protože v něm dominuje P ( m ); ve skutečnosti, že P ( m ) dominuje G ( m ), nehraje žádnou roli: ústředním bodem je to , že existuje právě tehdy, pokud existuje (paralelismus sekvencí). Pak pokud P ( m ) končí, nutně také G ( m ). A G ( m ) může skončit pouze dosažením 0.Gk(m){\ displaystyle G_ {k} (m)}Pk(m){\ displaystyle P_ {k} (m)}
-
(en) L. Kirby a J. Paris , „ Dostupné výsledky nezávislosti pro aritmetiku Peano “ , Bull. Londýn. Matematika. Soc. , sv. 14,1982, str. 285-293 ( číst online ).
-
David Madore, „ Učím se počítat do ψ (εΩ + 1) a krotit hydry “ , na adrese http://www.madore.org ,16. března 2008(přístup 29. dubna 2019 ) .
Podívejte se také
Bibliografie
- (en) R. Goodstein , „ K omezené ordinální větě “ , J. Symb. Logic , sv. 9,1944, str. 33-41 ( DOI 10.2307 / 2268019 )
-
(en) EA Cichon , „ Krátký důkaz dvou nedávno objevených výsledků nezávislosti pomocí rekurzivních teoretických metod “ , Proc. Hořký. Matematika. Soc. , sv. 87,1983, str. 704-706 ( číst online , přístup k 23. červnu 2013 ).
-
(en) A. Caicedo , „ Goodsteinova funkce “ , Revista Colombiana de Matemáticas , roč. 41, n O 22007, str. 381-391 ( číst online , přístup k 23. červnu 2013 ).
- Patrick Dehornoy , „ Je nekonečno nutné? ", Pour la science , n o 278" Les infinis ",2000, str. 102-106 ( číst online )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">