Teorema di Goodstein
In matematica , e più precisamente nella logica matematica , il teorema di Goodstein è un'affermazione aritmetica relativa a sequenze , chiamate sequenze di Goodstein . Le sequenze di Goodstein sono sequenze di interi a crescita iniziale estremamente rapida, e il teorema afferma che (nonostante le apparenze) ogni sequenza di Goodstein finisce con 0. Deve il suo nome al suo autore, il matematico e logico Reuben Goodstein .
Il teorema di Goodstein non è dimostrabile nell'aritmetica di Peano del primo ordine, ma può essere dimostrato in teorie più forti, come la teoria degli insiemi ZF (una semplice dimostrazione usa gli ordinali fino a ), o l' aritmetica del secondo ordine . Il teorema fornisce quindi, nel caso particolare dell'aritmetica del primo ordine, un esempio di enunciato indecidibile più naturale di quelli ottenuti dai teoremi di incompletezza di Gödel .
ε0{\ displaystyle \ varepsilon _ {0}}![\ varepsilon _ {0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acb0a8377db20e42274444cb181d51b5532b5844)
Definizione di una sequenza di Goodstein
Prima di definire una successione di Goodstein, definiamo innanzitutto la notazione ereditaria in base n . Per scrivere un intero naturale con tale notazione, lo scriviamo prima nella forma classica della scomposizione in base n :
aKnonK+aK-1nonK-1+⋯+a0{\ 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)
dove ognuno è un numero intero compreso tra 0 e n-1 . Quindi, applichiamo lo stesso trattamento agli esponenti k , k-1 , ... iterativamente, fino a ottenere un'espressione composta solo da numeri interi compresi tra 0 e n-1 .
aio{\ displaystyle a_ {i}}![avere}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bc77764b2e74e64a63341054fa90f3e07db275f)
Ad esempio, 35 è scritto in base 2 e la notazione ereditaria (nota anche come punteggio iterato ) in base 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)
La sequenza di Goodstein di un intero m , indicato con G ( m ), è definita come segue: il primo elemento della sequenza è m . Per ottenere il seguente elemento, scriviamo m in notazione ereditaria in base 2, quindi cambiamo ogni 2 in 3 e infine sottraiamo 1 dal risultato. Abbiamo quindi il secondo elemento della sequenza. Per ottenere il terzo, scriviamo in base 3 l'elemento precedentemente calcolato in notazione ereditaria, cambiamo 3s in 4, e sottraiamo 1. Continuiamo in questo modo fino ad ottenere 0 (cosa che accade sempre, come mostrato sotto).
Più formalmente, la sequenza è definita dall'iterazione delle seguenti due operazioni: nel passaggio n (ponendo ):
G(m){\ displaystyle G (m)}
G1(m)=m{\ displaystyle G_ {1} (m) = m}![{\ displaystyle G_ {1} (m) = m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c516cdde06ab2153a6b11f4170abcf28ba8fe633)
- Scrivi l'intero in notazione ereditaria in base n + 1 e sostituisci n + 1 con n + 2;Gnon(m){\ displaystyle G_ {n} (m)}
![{\ displaystyle G_ {n} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a21238038e9c99c5ff1ec444cd919123ca31e0f2)
- Sottrai 1; ecco come otteniamo .Gnon+1(m){\ displaystyle G_ {n + 1} (m)}
![{\ displaystyle G_ {n + 1} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ac78d977424e7e468bd9155b29a0689c0018629)
Enunciato del teorema
Teorema di Goodstein - Qualunque sia il valore iniziale di m , la sequenza di Goodstein G ( m ) termina con 0.
Esempi di suite Goodstein
I primissimi sequel di Goodstein finiscono rapidamente.
- Quindi, per G (1):
-
G1{\ displaystyle G_ {1}}
(1) = 1,
-
G2{\ displaystyle G_ {2}}
(1) = 1-1 = 0
- E per 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
Ma le sequenze di Goodstein generalmente crescono durante un gran numero di fasi, come vedremo più precisamente nell'ultima sezione . Ad esempio, le sequenze G (4) e G (5) iniziano come segue:
Valore
|
Notazione ereditaria
|
---|
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
|
|
...
|
|
|
Valore
|
Notazione ereditaria
|
---|
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
|
|
...
|
|
- Per quanto riguarda la successione G (4), il fenomeno osservato per le basi 6, 12 e 24 si riproduce per tutte le basi della forma p = 3 × 2 n : il valore precedente non include un termine unitario (termine di (p- 1) 0 ), e quindi compare in base p il termine di potenza 0 uguale a (p-1), con contemporanea riduzione di una unità del termine di potenza 1 o 2.
Quindi, quando raggiungiamo la base b = 3 × 2 27 - 1 = 402 653 183, il termine della sequenza è uguale a b 2 = 162 129 585 780 031 489. Il termine successivo è ( b + 1) 2 - 1 , cioè in base ( b + 1): b ( b + 1) + b , e il termine successivo sarà quindi b ( b + 2) + b - 1, ecc., in modo che non ci sia più alcun termine di potenza 2 o superiore in notazione ereditaria.
Quando raggiungiamo la base B = ( b + 1) 2 b - 1 = 3 × 2402 653 210 - 1, il termine della sequenza è uguale a B (anche la sequenza era costante dalla base ( B + 1) / 2). Il valore successivo è quindi B-1, vale a dire che la sequenza inizia finalmente a diminuire, e raggiunge il valore zero per la base 2 B + 1 = 3 × 2402653 211 - 1 , che è d 'altrove un Woodall numero (perché 3 × 2 402 653 211 = 402 653184 × 2 402653184 ). .
La base su cui successivamente G (4) termina con oltre 120 milioni di numeri, il che significa che il numero di termini della sequenza G (4) è dell'ordine di 10 120 000 000 .
- Sebbene la sequenza G (5) non cresca molto più velocemente, lo fa molto più a lungo, e le solite notazioni esponenziali non ci permettono più di esprimere la base più grande raggiunta. In posa:
g(non)=non2non{\ displaystyle g (n) = n2 ^ {n}}
gK=g∘g∘⋯∘g{\ 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 volte
M=g3(64)=270+270+2702270{\ displaystyle M = g ^ {3} (64) = 2 ^ {70 + 2 ^ {70} + 2 ^ {70} 2 ^ {2 ^ {70}}}}
NON=gM(M), P=gNON(NON), Q=gP(P),{\ Displaystyle N = g ^ {M} (M), \ P = g ^ {N} (N), \ Q = g ^ {P} (P),}
il numero di termini della sequenza G (5) è quindi Q - 2 (vedere l'ultima sezione per una giustificazione di questo calcolo). Questo numero non può essere espresso esattamente usando la notazione a freccia di Knuth , ma è (in questa notazione) dell'ordine di 2 ↑↑↑ 6, o ancora, usando la funzione di Ackermann , dell'ordine di A (5, 4).
- Tuttavia, questi due esempi non danno ancora un'idea sufficiente di quanto velocemente può crescere la sequenza di Goodstein. Pertanto, G (19) cresce molto più velocemente e inizia come segue:
Nonostante questa rapida crescita ( dell'ordine di n n 7 , e questo per un numero di passi molto maggiore del numero di Graham ), la sequenza alla fine diminuisce, fino a zero.
Prova
Il teorema di Goodstein può essere dimostrato (con un metodo che è al di fuori dell'aritmetica di Peano) usando gli ordinali : dato un intero me la sua sequenza di Goodstein G ( m ), costruiamo una sequenza parallela P ( m ) di ordinali tale che P ( m ) strettamente diminuisce e finisce. Sarà quindi lo stesso per la continuazione di Goodstein G ( m ) che può terminare solo quando viene annullata.
Più precisamente, per ogni intero n , il termine della successione P ( m ) si ottiene applicando una trasformazione alla fine della sequenza di Goodstein di m come segue: prendiamo la rappresentazione ereditaria in base n +1 del termine , e sostituiamo ogni occorrenza di n +1 con il primo ordinale infinito, ω; quindi, ad esempio, e . L'addizione, la moltiplicazione e l'esponenziazione dei numeri ordinali sono ben definiti e il risultato è un ordinale rappresentato nella forma normale di Cantor . Inoltre, quando eseguiamo un cambiamento di base nella sequenza di Goodstein da cui andare a , abbiamo : è il punto centrale di questa costruzione (per esempio, ).
Pnon(m){\ displaystyle P_ {n} (m)}
fnon+1{\ displaystyle f_ {n + 1}}
Gnon(m){\ displaystyle G_ {n} (m)}
Gnon(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}
Gnon(m){\ displaystyle G_ {n} (m)}
Gnon+1(m){\ displaystyle G_ {n + 1} (m)}
Pnon(m)=fnon+1(Gnon(m))=fnon+2(Gnon(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)}![{\ 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)
Dopo aver sottratto 1, sarà rigorosamente inferiore a :
Pnon+1(m)=fnon+2(Gnon(m))-1=fnon+2(Gnon+1(m)){\ displaystyle P_ {n + 1} (m) = f_ {n + 2} (G_ {n} (m)) - 1 = f_ {n + 2} (G_ {n + 1} (m))}
Pnon(m){\ displaystyle P_ {n} (m)}![{\ displaystyle P_ {n} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31625db7317b61049867349ca95e2fe77739030f)
- quando la forma normale di Cantor è della forma con , = . Quindi è strettamente maggiore di ;Pnon(m){\ displaystyle P_ {n} (m)}
X+α.ω0{\ displaystyle X + \ alpha. \ omega ^ {0}}
α≠0{\ displaystyle \ alpha \ neq 0}
Pnon+1(m){\ displaystyle P_ {n + 1} (m)}
Pnon(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}![{\ 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)
- allo stesso modo, quando è un ordinale limite, è strettamente inferiore, quindi è strettamente superiore a ;Pnon(m){\ displaystyle P_ {n} (m)}
Pnon+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}![{\ 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)
- in entrambi i casi, concludiamo che la successione parallela P ( m ) diminuisce strettamente.
Stabilito il netto decremento della sequenza P ( m ), l'argomento prosegue come segue: se la sequenza G ( m ) non arrivasse a 0, sarebbe infinita (perché sarebbe sempre definita). Quindi anche P ( m ) sarebbe infinito (poiché anche sarebbe sempre definito). Ma P ( m ) è strettamente decrescente; ora l'ordine standard < sull'insieme di ordinali minore di è un buon ordine , quindi non esiste una sequenza infinita di ordinali rigorosamente decrescente , o, in altre parole, qualsiasi sequenza strettamente decrescente di ordinali finisce e non può quindi essere infinita. Questa contraddizione mostra che la successione G ( m ) finisce e quindi raggiunge 0 (a proposito, poiché esiste un intero naturale k tale che = 0, e per definizione di P ( m ), abbiamo anche = 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)}![{\ displaystyle P_ {k} (m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fcfeaf040ec713f95849f7e5e70d289d4e9d18d4)
Mentre la dimostrazione del teorema di Goodstein è relativamente facile, il teorema di Laurence Kirby e Jeff Paris che afferma che il teorema di Goodstein non può essere dimostrato nell'aritmetica di Peano, è tecnico e notevolmente più difficile. La dimostrazione di Kirby e Paris utilizza modelli numerabili non standard dell'aritmetica di Peano per ridurre il teorema di Goodstein al teorema di Gentzen , che dà la consistenza dell'aritmetica per induzione fino all'ordinale ε 0 (il limite superiore degli ordinali usati per la dimostrazione del teorema di Goodstein teorema).
La lunghezza della sequenza in funzione del valore iniziale
La funzione Goodstein , è definita da " è la lunghezza della sequenza Goodstein G ( n )" (che si applica , come tutte le suite Goodstein fine). La crescita estremamente rapida può essere misurata collegandosi a varie gerarchie di funzioni indicizzate da ordinali, come le funzioni della gerarchia Hardy (in) o le funzioni della gerarchia in rapida crescita di Löb e Wainer:
G:NON→NON{\ displaystyle {\ mathcal {G}}: \ mathbb {N} \ to \ mathbb {N} \, \!}
G(non){\ displaystyle {\ mathcal {G}} (n)}
G{\ displaystyle {\ mathcal {G}} \, \!}
Hα{\ displaystyle H _ {\ alpha} \, \!}
fα{\ displaystyle f _ {\ alpha} \, \!}![f _ {\ alpha} \, \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/f734dfa8e00d082904b61eff0a65083eeaf4d6ea)
- Kirby e Paris (1982) lo hanno dimostrato
G{\ displaystyle {\ mathcal {G}} \, \!}![{\ mathcal {G}} \, \!](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e490be527974ca05b195679c7ab1a5a930e7577)
cresce all'incirca alla stessa velocità (e quindi quanto ); più precisamente, domina per tutto e domina
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}} \, \!.}![{\ mathcal {G}} \, \!.](https://wikimedia.org/api/rest_v1/media/math/render/svg/60d5867efca8cac9f546d4beb8780e1ca3c7feba)
(per due funzioni , diciamo che domina se per tutte abbastanza grande). Più precisamente ancora, Cichon (1983) lo ha dimostrato
f,g:NON→NON{\ displaystyle f, g: \ mathbb {N} \ to \ mathbb {N} \, \!}
f{\ displaystyle f \, \!}
g{\ displaystyle g \, \!}
f(non)>g(non){\ displaystyle f (n)> g (n) \, \!}
non{\ displaystyle n \, \!}
G(non)=HR2ω(non+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)
dove è il risultato di scrivere n in notazione ereditaria in base 2, quindi sostituire tutto 2 con ω (come nella dimostrazione del teorema di Goodstein).
R2ω(non){\ displaystyle R_ {2} ^ {\ omega} (n)}
- Caicedo (2007) ha dimostrato che se con alloranon=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)
G(non)=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}![{\ 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)
.
Ecco alcuni esempi :
non
|
G(non){\ 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) (dove A è la funzione di Ackermann )
|
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}
|
> LA 3 (3,3) = LA ( LA (61, 61), LA (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, il numero di Graham
|
⋮{\ 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}
|
> , un numero che può essere espresso solo in notazione Conway con un numero di frecce maggiore del numero di Graham .
fω2(G){\ 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}
|
fωω(f1(f0(3)))-2{\ displaystyle f _ {\ omega ^ {\ omega}} (f_ {1} (f_ {0} (3))) - 2}
|
|
(le disuguaglianze che coinvolgono la funzione di Ackermann A e il numero di Graham G sono dettagliate nell'articolo sulla gerarchia della crescita rapida ).
Generalizzazioni e teoremi analoghi
Sia una sequenza di numeri interi (che possiamo supporre essere strettamente crescente, con ); possiamo definire una sequenza di Goodstein generalizzata impostando e scrivendo ad ogni passaggio nella notazione di base ereditaria , sostituendo tutto il by e sottraendo 1 dal risultato da ottenere ; sebbene questa sequenza possa crescere molto più velocemente della solita sequenza di Goodstein (corrispondente a ), qualunque sia la velocità di crescita della sequenza , si applica la dimostrazione precedente e la sequenza finisce sempre per raggiungere 0.
(bnon){\ displaystyle (b_ {n})}
b0=2{\ displaystyle b_ {0} = 2}
G(m)(non){\ displaystyle G (m) (n)}
G(m)(0)=m{\ displaystyle G (m) (0) = m}
G(m)(non){\ displaystyle G (m) (n)}
bnon{\ displaystyle b_ {n}}
bnon{\ displaystyle b_ {n}}
bnon+1{\ displaystyle b_ {n + 1}}
G(m)(non+1){\ displaystyle G (m) (n + 1)}
bnon=non+2{\ displaystyle b_ {n} = n + 2}
(bnon){\ displaystyle (b_ {n})}![(b_n)](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ca3872ee8054312f21ff267bc6831745e42b9c9)
Paris e Kirby costruirono suite simili utilizzando un modello di idra ispirato alla leggenda della battaglia di Ercole con l' Idra di Lerna . Questi sono alberi da cui Hercules può tagliare un vertice (una testa) ad ogni colpo, il che fa ricrescere un numero arbitrario di sottoalberi, ma a un livello inferiore; dimostriamo sostituendo ogni albero con un ordinale (minore di ε 0 ) che gli ordinali ottenuti formano una sequenza decrescente, da qui il risultato: per quanto cattiva possa essere la strategia di Ercole, e per quante teste ricrescano, l'idra finisce sempre essere sconfitto; con regole di ricrescita della testa più complesse, un ragionamento analogo può anche richiedere l'uso di ordinali molto maggiori di ε 0 .
Appunti
-
(a) James M. Henle, An Outline of Set Theory ( leggi online ) , p. 137-138.
-
Un errore comune è pensare che G ( m ) arrivi a 0 perché è dominato da P ( m ); infatti che P ( m ) domina G ( m ) non gioca alcun ruolo: il punto centrale è che esiste se e solo se esiste (parallelismo di successioni). Allora se P ( m ) finisce, necessariamente anche G ( m ). E G ( m ) può terminare solo raggiungendo 0.GK(m){\ displaystyle G_ {k} (m)}
PK(m){\ displaystyle P_ {k} (m)}
-
(en) L. Kirby e J. Paris , " Risultati dell'indipendenza accessibile per l'aritmetica di Peano " , Bull. Londra. Matematica. Soc. , vol. 14,1982, p. 285-293 ( leggi in linea ).
-
David Madore, " Sto imparando a contare fino a ψ (εΩ + 1) e ad addomesticare le idre " , su http://www.madore.org ,16 marzo 2008(visitato il 29 aprile 2019 ) .
Vedi anche
Bibliografia
- (en) R. Goodstein , " Sul teorema ordinale ristretto " , J. Symb. Logica , vol. 9,1944, p. 33-41 ( DOI 10.2307 / 2268019 )
-
(en) EA Cichon , " Una breve dimostrazione di due risultati di indipendenza scoperti di recente utilizzando metodi teorici ricorsivi " , Proc. Amaro. Matematica. Soc. , vol. 87,1983, p. 704-706 ( letto online , accesso 23 giugno 2013 ).
-
(en) A. Caicedo , " La funzione di Goodstein " , Revista Colombiana de Matemáticas , vol. 41, n o 22007, p. 381-391 ( letto online , accesso 23 giugno 2013 ).
- Patrick Dehornoy , "L' infinito è necessario? ", Pour la science , n . 278" Les infinis ",2000, p. 102-106 ( leggi in linea )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">