Teorema di Goodstein

In matematica, il teorema di Goodstein è un teorema sui numeri naturali, relativamente semplice da enunciare, la cui particolarità consiste nel fatto di essere indecidibile dall'aritmetica di Peano ma dimostrabile nella teoria assiomatica degli insiemi. Esso può essere considerato un esempio di enunciato indecidibile dagli usuali assiomi dell'aritmetica più "naturale" rispetto alle complicate costruzioni dei teoremi di incompletezza di Gödel.

Per enunciare il teorema di Goodstein occorre dare alcune definizioni preliminari.

Notazione ereditaria in base n

Definiamo innanzitutto una speciale notazione numerica. Dato un numero naturale $n$ chiamiamo notazione ereditaria in base n di un numero $a$ l'espressione costruita mediante la seguente procedura:

• Scriviamo $a$ in base $n$, ottenendo un'espressione del tipo:

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

dove tutti gli $a_{i}$ sono compresi tra $0$ e $n-1$.

• Scriviamo tutti gli esponenti in base $n$ e sostituiamo l'espressione di ciascuno di essi nell'espressione sopra.
• Consideriamo ora tutti gli esponenti che compaiono negli esponenti e ancora li rimpiazziamo con la loro scrittura in base $n$.
• E così via per gli esponenti degli esponenti degli esponenti, eccetera... fino ad arrivare ad una espressione in cui compaiono solamente numeri compresi tra $0$ e $n$.

Per esempio: scriviamo 35 nella notazione ereditaria in base 2:

• Scriviamo inizialmente 35 in base 2:

$35=2^{5}+2+1=2^{5}+2^{1}+2^{0}$

• Gli esponenti sono $5$, $1$ e $0$. Gli esponenti $1$ e $0$ sono già in base $2$, per quanto riguarda $5$ la sua espressione in base $2$ è data da $2^{2}+1$, quindi rimpiazziamo questa espressione nell'espressione che avevamo prima e otteniamo

$35=2^{2^{2}+1}+2+1$

• La scrittura ottenuta è quella finale, poiché compaiono solamente numeri compresi tra $0$ e $2$.

Sequenza di Goodstein associata ad un numero

La sequenza di Goodstein associata ad un numero m è una successione G(1,m), G(2,m), G(3,m)... definita per ricorrenza nel seguente modo:

$G(1,m)=m\$

$G(k+1,m)=d(G(k,m))-1,$

ove d(G(k,m)) è l'operazione di dilatazione su $G(k,m)$ ottenuta sostituendo il numero "k+2" a tutte le occorrenze del numero "k+1" presenti nella notazione ereditaria in base k+1.

Vediamo ora passo passo:

• il primo elemento G(1,m) della sequenza è il numero m stesso
• per ottenere il secondo G(2,m) si procede così:
  • si scrive m nella notazione ereditaria in base 2
  • si sostituisce il numero 3 al posto di ogni 2
  • si sottrae 1
• per ottenere il terzo elemento G(3,m) si procede così:
  • si scrive G(2,m) nella notazione ereditaria in base 3
  • si sostituisce il numero 4 al posto di ogni 3
  • si sottrae 1
• più in generale, una volta ottenuto il k-esimo numero della sequenza G(k,m), per ottenere il termine (k+1)-esimo si procede così:
  • si scrive G(k,m) nella notazione ereditaria in base k+1
  • si sostituisce il numero k+2 al posto di ogni k+1
  • si sottrae 1

La sequenza termina in corrispondenza del primo valore del passo k tale che G(k,m)=0.

Ad esempio i primi tre termini della sequenza di Goodstein di 35 sono:

• $G(1,35)=35$
• poiché $35=2^{2^{2}+1}+2+2^{0}$ rimpiazzando $3$ al posto di $2$ e sottraendo $1$ otteniamo:

$G(2,35)=(3^{3^{3}+1}+3+3^{0})-1=3^{28}+3=22876792454964$

• per calcolare $G(3,35)$ dobbiamo scrivere in notazione ereditaria in base $3$ il numero $22876792454964$, tale scrittura risulta essere $3^{3^{3}+1}+3$

quando rimpiazziamo $4$ al posto di $3$ otteniamo circa $5,363\times {10^{136}}$ un numero enorme a cui dobbiamo sottrarre $1$. Il risultato sarà indicato con $G(3,35)$.

Altri esempi di sequenze di Goodstein

La sequenza di Goodstein che si ha partendo da 3 raggiunge presto il valore 0:

Base	Notazione ereditaria	Valore	Note
2	21 + 1	3	1 sta per 20.
3	31 + 1 − 1 = 3	3	Rimpiazziamo i 2 nella precedente espressione con dei 3 e poi sottraiamo 1. Quello che otteniamo è 3 che è già espresso nella nuova base, che è appunto 3.
4	41 − 1 = 3	3	Rimpiazziamo i 3 nella precedente espressione con 4 e sottraiamo 1. Poiché il valore da rappresentare in base 4 è 3 che è minore della base, la rappresentazione è ancora 3
5	3 − 1 = 2	2	Dovremmo rimpiazzare i 4 della precedente espressione con dei 5, ma non ce ne sono, quindi l'espressione rimane 3 a cui dobbiamo sottrarre 1.
6	2 − 1 = 1	1
7	1 − 1 = 0	0

È sufficiente considerare la successione di Goodstein associata a 4 per vedere invece i valori della successione crescere a lungo:

Base	Notazione ereditaria	Valore
2	2²	4
3	2·3² + 2·3 + 2	26
4	2·4² + 2·4 + 1	41
5	2·5² + 2·5	60
6	2·6² + 6 + 5	83
7	2·7² + 7 + 4	109
...
11	2·11² + 11	253
12	2·12² + 11	299
...
1000	1000²+18·1000+ 535	1018535
1001	1001²+18·1001+ 534	1020553
...

Gli elementi di questa successione continuano a crescere fino a raggiungere in corrispondenza della base 3 · 2^402653209 il valore massimo di 3 · 2^402653210 − 1, poi la successione rimane stazionaria per altri 3 · 2^402653209 passi e infine inizia a decrescere fino a raggiungere lo zero in corrispondenza della base 3 · 2^402653211 − 1.

L'esempio della successione che inizia da 4 tuttavia non è ancora un buon esempio di quanto rapidamente può crescere una successione di Goodstein. Se partiamo da 19 otteniamo la sequenza di valori:

Notazione ereditaria	Valore
$2^{2^{2}}+2+1$	19
$3^{3^{3}}+3$	7625597484990
$4^{4^{4}}+3$	circa 1.3 × 10154
$5^{5^{5}}+2$	circa 1.8 × 102184
$6^{6^{6}}+1$	circa 2.6 × 1036305
$7^{7^{7}}$	circa 3.8 × 10695974
$7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7)}$ $+7\times 8^{(7\times 8^{7}+7\times 8^{6}+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+6)}$ $+...\,\;$ $+7\times 8^{(8+2)}+7\times 8^{(8+1)}+7\times 8^{8}+7\times 8^{7}+7\times 8^{6}$ $+7\times 8^{5}+7\times 8^{4}+7\times 8^{3}+7\times 8^{2}+7\times 8+7$	circa 6 × 1015151335
$7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+7)}$ $+7\times 9^{(7\times 9^{7}+7\times 9^{6}+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6)}$ $+...\,\;$ $+7\times 9^{(9+2)}+7\times 9^{(9+1)}+7\times 9^{9}+7\times 9^{7}+7\times 9^{6}$ $+7\times 9^{5}+7\times 9^{4}+7\times 9^{3}+7\times 9^{2}+7\times 9+6$	circa 4.3 × 10369693099
...

L'enunciato del teorema

Nonostante questa crescita vertiginosa il teorema di Goodstein asserisce che

Tutte le sequenze di Goodstein, qualunque sia il valore iniziale, raggiungono lo 0.

Dimostrazione

Data una successione di Goodstein associata ad un qualsiasi numero m costruiamo una successione "parallela" di numeri ordinali.

Abbiamo visto che ad ogni termine della sequenza è associata una base partendo da 2 per il primo (cioè m) e aumentando progressivamente di 1. Accanto alla sequenza dei valori possiamo quindi considerare la sequenza delle loro rappresentazioni nella corrispondente base come abbiamo visto nelle tabelle sopra rappresentate.

La successione parallela di ordinali è costruita considerando la successione di tutte le rappresentazioni ereditarie e sostituendo alle corrispondenti basi il numero ordinale ω. Ricordiamo che per i numeri ordinali sono ben definite le operazioni di addizione, moltiplicazione e potenza.

Nell'esempio considerato precedentemente con m=4 abbiamo quindi:

Notazione ereditaria	Valore	Base	Successione parallela
2²	4	2	ωω
2·3² + 2·3 + 2	26	3	2·ω² + 2·ω + 2
2·4² + 2·4 + 1	41	4	2·ω² + 2·ω + 1
2·5² + 2·5	60	5	2·ω² + 2·ω
2·6² + 6 + 5	83	6	2·ω² + ω + 5
2·7² + 7 + 4	109	7	2·ω² + ω + 4
...
2·11² + 11	253	11	2·ω² + ω
2·12² + 11	299	12	2·ω² + 11
...
1000²+18·1000+ 535	1018535	1000	ω²+18·ω+ 535
1001²+18·1001+ 534	1020553	1001	ω²+18·ω+ 534
...

Nel caso in cui un termine delle due successioni fosse uguale a 0 deve essere 0 anche il termine della successione parallela. Dunque l'idea per la dimostrazione del teorema è dimostrare che la sequenza parallela di ordinali converge a 0.

Un primo passo consiste nell'osservare che la successione parallela, quando è non nulla, è strettamente decrescente rispetto alla relazione d'ordine di cui sono dotati naturalmente gli ordinali. A tale scopo ricordiamo che gli ordinali espressi nella forma che stiamo considerando corrispondono a tutti gli ordinali minori di $\varepsilon _{0}$, la cui struttura di insieme ordinato è isomorfa all'insieme delle funzioni reali di una variabile reale che si hanno considerando le analoghe espressioni con la variabile x al posto di ω e dotandolo della seguente relazione d'ordine:

$p(x)<_{\rm {psf}}\,q(x)$ se e solo se il grafico di p(x) si stabilizza al di sotto del grafico di q(x) da un certo x in poi;

(le lettere "psf" abbreviano "per segmenti finali").

Come si può vedere, nell'esempio la successione di ordinali è decrescente rispetto a questa relazione d'ordine, ovvero: $x^{x}>_{\rm {psf}}\,2x^{2}+2x+2>_{\rm {psf}}2x^{2}+2x+1>_{\rm {psf}}...>_{\rm {psf}}x^{2}+18x+535>_{\rm {psf}}...$ dunque a differenza della successione originale, la successione parallela degli ordinali è decrescente. Questo accade perché l'operazione di cambiamento di base non ha alcun effetto sulla successione parallela, mentre quando scriviamo un termine della successione nella base corrispondente e sottraiamo 1 e lo riscriviamo nuovamente nella stessa base, l'ordinale associato sarà in ogni caso minore del precedente.

In generale se abbiamo una successione strettamente decrescente di numeri naturali possiamo concludere che questa deve raggiungere lo 0 in un numero finito di passi grazie al principio di induzione. Nel nostro caso abbiamo a che fare con una successione decrescente di numeri ordinali, e per concludere che questa deve raggiungere lo 0 possiamo avvalerci del principio di induzione transfinita.

Indipendenza nell'aritmetica di Peano

La dimostrazione sopra esposta fa uso di un principio (l'induzione transfinita sugli ordinali minori di $\varepsilon _{0}$) che non è formalizzabile nell'aritmetica di Peano. Questa è una conseguenza di due teoremi dovuti a Gödel e Gentzen: il primo ha dimostrato che se una teoria sufficientemente potente è coerente allora non può dimostrare la propria coerenza, il secondo ha dimostrato che la coerenza dell'aritmetica di Peano si può dimostrare tramite il principio di induzione transfinita fino all'ordinale $\varepsilon _{0}$. Dunque a meno che l'aritmetica di Peano non sia incoerente non può essere in grado di formalizzare il principio di induzione transfinita fino all'ordinale $\varepsilon _{0}$.

È naturale quindi chiedersi se il teorema sia o no dimostrabile nell'aritmetica di Peano (eventualmente in altri modi). La questione è stata risolta dal teorema di Kirby e Paris (la cui dimostrazione è considerevolmente più tecnica e difficile di quella del teorema di Goodstein) il quale sfrutta il teorema di Goodstein per dimostrare che l'aritmetica di Peano è una teoria coerente. La dimostrazione di Kirby e Paris assieme con i teoremi di incompletezza di Gödel implica che il teorema di Goodstein è indecidibile nell'aritmetica di Peano.

Bibliografia

• Goodstein, R., On the restricted ordinal theorem, Journal of Symbolic Logic, 9 (1944), 33-41.
• Kirby, L. and Paris, J., Accessible independence results for Peano arithmetic, Bull. London. Math. Soc., 14 (1982), 285-93.

Collegamenti esterni

• (EN) Eric W. Weisstein, Teorema di Goodstein, su MathWorld, Wolfram Research.
• (EN) Sito contenente una definizione di sequenze di Goodstein nei linguaggi di programmazione Ruby e Haskell ed un grafico su larga scala si possono trovare qui