Le successioni di Goodstein: la potenza di una deviazione passando per infinito

Autori originali sono Michèle Artigue, Ferdinando Arzarello e Susanna Epp.
4 maggio 2012

Studiare l’evoluzione di un fenomeno naturale spesso conduce a studiare successioni numeriche, specialmente il loro comportamento a lungo termine e se esse alla fine convergono. Le successioni polinomiali, esponenziali e logaritmiche si incontrano frequentemente nella scuola secondaria, ma alcune altre successioni con definizioni molto semplici mostrano un comportamento molto più complesso. Alcuni esempi includono le successioni caotiche che emergono nello studio dei sistemi dinamici (si veda [1]) e la successione di Siracusa (o successione ), introdotta da Luther Collatz nel 1937. La successione di Siracusa ha messo in difficoltà i matematici per decenni. Nonostante il gran numero di valori che sono stati calcolati, è sconosciuto ancora oggi se la successione sia infinita o finita e se termini sempre in (si veda [2]).

Le successioni considerate in questa ‘vignette’ sono state introdotte dal logico inglese R. L. Goodstein nel 1944 (si veda [3]) e mostrano un tipo diverso di comportamento insolito. I valori iniziali aumentano così rapidamente che siamo portati a credere che essi tendano ad infinito, ma, sorprendentemente, essi finiscono sempre per decrescere e infine raggiungono lo zero.

Dimostrare questo risultato richiede una generalizzazione del principio di buon ordinamento per gli interi (si veda [4]) ai numeri transfiniti, ma l’idea di base non è difficile da comprendere. Per spiegarla, seguendo Hodgson (si veda [5]), introduciamo prima una successione, detta successione di Goodstein debole, che è più semplice ma strettamente legata ad una successione di Goodstein.

1. Successioni di Goodstein deboli

Come Hodgson, enunciamo la definizione di successione di Goodstein debole iniziando dal numero 266. Come tutti gli interi positivi, esso ammette una scomposizione unica in una somma di potenze con base (si veda [6]): . La successione di Goodstein debole con termine iniziale è definita come segue: per ottenere si copia la rappresentazione in base di ma si cambia ogni base nella base , si sottrae e si riscrive il numero ottenuto in base . Quindi . Per determinare si inizia con la rappresentazione di , si cambia ogni base nella base , si sottrae e si riscrive il numero ottenuto in base . Quindi . Si continua a generare termini della successione, fino a quando nessun termine è uguale a zero, sostituendo l’intero che è alla base del precedente termine con il successivo intero, sottraendo e riscrivendo il risultato usando la nuova base.

   

Tabella 1: Termini iniziali di una successione di Goodstein debole.

Come puoi vedere i termini della successione diventano velocemente molto grandi, perciò potresti chiederti se tutte queste successioni aumentano rapidamente. Ma non è così. Per esempio, se , allora . Se , allora , e (perché la base per è e quella per è ). Analogamente, puoi verificare che se allora i termini della successione non diventano mai più grandi di e raggiungono in cinque passi (si veda [7]).

In ogni caso, appena la scomposizione del termine iniziale include una potenza di più grande di , la crescita iniziale nei termini è molto rapida (come illustrato per ), cosa che porta a credere che la successione tenda ad infinito. Come può il fatto di sottrarre semplicemente ad ogni passo contrastare l’enorme crescita nei termini che si ottiene aumentando ogni volta di la base?

Eppure… Guardiamo più attentamente le espressioni nella tabella sopra. Nonostante i termini successivi della successione con termine iniziale crescano rapidamente, gli esponenti per le rappresentazioni nelle basi successive tendono a decrescere. Per esempio, l’esponente in non è più presente in . Allo stesso modo, l’esponente in viene rimpiazzato da in . Ed entro , esso si riduce ad , quando il coefficiente per cui è moltiplicato inizia a diminuire. Alla fine, l’esponente in è ridotto a e il continua a ridursi nei passi successivi.

É questa caratteristica, comune a tutte le successioni di Goodstein, che ci permetterà di dimostrare che esse convergono a . Per vederlo, abbiamo bisogno di introdurre, come promesso, i numeri ordinali transfiniti.

2. Numeri ordinali transfiniti e buoni ordinamenti

Ordinali
In linguaggio ordinario, i numeri ordinali sono usati per indicare la posizione in una lista: primo, secondo, terzo, ecc. Infatti, gli interi positivi possono essere usati in questo modo per disporre gli elementi di un qualsiasi insieme finito. L’idea di numero ordinale transfinito estende la nozione di numero ordinale. Essa è dovuta al matematico Georg Cantor, che la sviluppò in una serie di articoli alla fine del diciannovesimo secolo. Poiché l’insieme degli interi è infinito, se immaginiamo di iniziare con e contare gli interi successivi non finiremmo mai. Possiamo comunque immaginare che esista un ‘numero’ , che sia il primo numero più grande di ogni intero. Poiché gli interi più piccoli di sono infinitamente tanti, chiamiamo numero ordinale ‘transfinito’. Esso ha un successivo , che è seguito da e così via. Il più piccolo ordinale più grande di tutti gli ordinali della forma si denota con o (si veda [8]) e il più piccolo ordinale più grande di tutti gli ordinali della forma (dove è un ordinale minore di ) si denota con . Il più piccolo ordinale più grande di tutti gli ordinali della forma (dove è un ordinale minore di ) si denota con .

   

Poi è seguito da , , …, , , …, , …, , …, , ecc. e definiamo il più piccolo ordinale più grande di tutte le somme di potenze iterate di e lasciamo che il processo continui indefinitamente. Infatti, tutti gli ordinali considerati finora costituiscono solo l’inizio della catena di ordinali, siccome formano un insieme numerabile, ossia possono essere messi in corrispondenza, uno-a-uno con gli interi positivi.

Ordinali e buon ordinamento
Una differenza significativa tra gli ordinali transfiniti e gli interi non-negativi è che ogni intero più grande di ha un immediato antecedente mentre gli ordinali come , e no. In ogni caso, come l’insieme degli interi, l’insieme esteso dei numeri ordinali è ‘ben ordinato’ nel senso che ogni insieme non vuoto di ordinali ha un minimo. Grazie a questa proprietà possiamo dedurre il fatto che non può esistere una successione strettamente decrescente infinitamente lunga di numeri ordinali. Infatti, supponiamo che tale successione infinita esista. Denotiamola con e sia l’insieme di tutti i suoi termini. Dato che è non vuoto, esso ammette un minimo e quindi per qualche intero . Tuttavia, dal momento che la successione è strettamente decrescente, e quindi non è l’elemento minimo di , cosa che contraddice la supposizione fatta.

Mostreremo ora come usare i numeri ordinali per provare il risultato sulle successioni deboli di Goodstein.

3. Prova del fatto che una successione di Goodstein debole converge a zero

Ad ogni successione di Goodstein debole , associamo una successione strettamente decrescente di ordinali sostituendo la base in ogni termine di con . Poiché la base iniziale di una successione di Goodstein debole è e dato che la base si incrementa di ad ogni passo, la scomposizione di ha base . Perciò per la successione associata a , i termini iniziali di sono mostrati nella Tabella 2:

…	…	…
…	…	…

Tabella 2: La successione degli ordinali che corrisponde ad una successione di Goodstein debole

Per costruzione, ogni termine di è più grande del corrispondente termine di , ma mentre è crescente, è decrescente. Il motivo è che, nella scomposizione di nella base , o il termine dell’unità di è nullo o non lo è. Il passaggio da ogni termine al successivo perciò è compiuto in uno dei due modi seguenti:

• Se il termine dell’unità di è non nullo, allora poiché si sottrae ad ogni passo, il termine dell’unità di è uno in meno rispetto al termine dell’unità di . (Nella Tabella 2, questo accade nel passare da a , da a , da a e da a .)
• Se il termine dell’unità di è nullo, quando si riscrive la scomposizione nella nuova base, si deve spezzare il termine della scomposizione avente l’esponente più basso. (Nella Tabella 2, questo accade nel passare da a , da a e da a . Si veda la Tabella 1 per i calcoli dettagliati.) (si veda [9])

Si osservi che in entrambi i casi il nuovo termine di è strettamente minore del precedente.

Ora, poiché gli ordinali sono ben ordinati, non esiste una successione infinita strettamente decrescente di ordinali e quindi deve esistere un intero per cui . Inoltre, siccome per ogni , anche deve essere nullo. In altre parole, i termini di raggiungono in un numero finito di passi, nonostante il numero di passi possa essere estremamente grande.

Invitiamo il lettore a scrivere i termini di e iniziando con . Per quale valore di , ? Qual è dunque il valore di e quali sono i termini successivi per ognuna delle due successioni? (si veda [10]).

Siamo ora pronti per esaminare le successioni di Goodstein vere e proprie. Esse sono definite in modo leggermente differente dalle successioni di Goodstein deboli e la natura della loro crescita è molto più spettacolare. Tuttavia, sorprendentemente, la strategia per provare che esse alla fine decrescono a zero è simile a quanto abbiamo appena fatto.

4. Le successioni di Goodstein

Si consideri nuovamente la rappresentazione di in base : . Ora scriviamo gli esponenti usando solo la base : e . Come risultato, l’intera espressione per può essere riscritta interamente senza usare nessun numero più grande della base . Sia la successione di Goodstein che inizia con . Per costruire , si sostituiscano tutte le occorrenze di con , si sottragga e si riscriva il risultato senza usare alcun numero più grande della base . Poi si continui il processo iterativamente per ottenere i termini successivi di , come mostrato in Tabella 3. (Si veda [11]).

   

Tabella 3

Come si vede, la crescita dell’ordine di grandezza dei termini è spettacolare eppure questa successione, come tutte le successioni di Goodstein, ad un certo punto inizia a decrescere e finisce per convergere a . La dimostrazione è molto simile a quella per una successione di Goodstein debole. Come in quel caso, una successione è associata alla successione sostituendo ciascuna occorrenza di ogni base con . I primi pochi termini di sono i seguenti:

   

La successione di numeri ordinali è strettamente decrescente, ciò implica che essa ammetta un minimo, e, poiché i termini continuano ad essere calcolati finché non si annullano, l’elemento minimo della successione è . Analogo ragionamento può essere usato per tutte le successioni di Goodstein.

L’ordinaria aritmetica degli interi è spesso chiamata aritmetica di Peano perché Giuseppe Peano, matematico italiano del diciannovesimo secolo, formulò per primo i suoi assiomi. L’aspetto più rilevante dell’elegante dimostrazione data sopra consiste nel fatto che essa va oltre l’aritmetica di Peano per provare un teorema che può essere enunciato interamente all’interno dell’aritmetica di Peano. In altre parole, si usa una teoria generale degli insiemi che include gli ordinali transfiniti per dimostrare un teorema relativo agli interi non-negativi, più precisamente che ogni successione di Goodstein converge a . É naturale chiedersi se la convergenza delle successioni di Goodstein può essere provata senza usare gli ordinali transfiniti. La risposta è no! Questo fu dimostrato nel 1982, approssimativamente 40 anni dopo che le successioni furono introdotte, da Laurie Kirby e Jeff Paris (si veda [12]). Essi mostrarono che se la convergenza potesse essere dimostrata usando solo il principio di buon ordinamento per gli interi (ossia all’interno dell’aritmetica di Peano), allora il teorema sulle successioni di Goodstein potrebbe essere ridotto ad un teorema di Gentzen (1936), dal quale potrebbe essere dedotta la consistenza dell’aritmetica di Peano. Tuttavia noi sappiamo dal teorema di incompletezza di Gödel (1931) che la consistenza dell’aritmetica di Peano non può essere dimostrata usando solo l’aritmetica di Peano. É perciò inutile per i matematici sprecare le loro energie nel provare a cercare una simile dimostrazione!

D’altro canto, cosa che potrebbe sembrare sorprendente, il fatto che le successioni di Goodstein deboli convergano a può essere provato all’interno dell’aritmetica di Peano. Il motivo è essenzialmente che i termini della successione di ordinali associata sono tutti minori di . Una dimostrazione fu data da E. A. Cichon che introdusse le successioni di Goodstein deboli nel 1983 (si veda [13]). Ad ogni termine di una successione di Goodstein debole, si può far corrispondere la -upla dei coefficienti della scomposizione in base e mostrare che le -uple soddisfano un buon ordinamento lessicografico strettamente decrescente.

5. Le successioni di Goodstein e il gioco di Idra

Nel loro articolo, Kirby e Paris menzionano un altro processo, il gioco di Idra, avente molte somiglianze con le successioni di Goodstein. Il gioco (si veda [14]) prende il suo nome da una descrizione nella mitologia greca del combattimento tra Ercole e un mostro con molte teste: l’Idra di Lerna. Ogni volta che una delle teste di Idra veniva tagliata, due nuove teste crescevano al suo posto. Nel gioco, l’idra è modellizzata da un albero e le teste dell’idra corrispondono ai vertici terminali, o foglie, dell’albero. Se Ercole taglia una testa che non è direttamente connessa alla radice dell’albero, il tratto che conduce alla testa è eliminato, ma crescono nuove teste dal nodo situato due livelli sotto la testa che è stata tagliata. Questo può essere realizzato in vari modi. Nell’esempio dato da Kirby e Paris ed usato di nuovo da Hodgson (si veda [4]), se una testa è tagliata al passo del gioco, l’idra genera copie della parte di albero uscente dal nodo situato due livelli sotto la testa che è stata rimossa. Nel diagramma qui sotto, la parte tagliata è rappresentata da una linea tratteggiata, la parte che si rigenera da una linea in rosso e la nuova parte che cresce da una linea blu.

É possibile dimostrare che qualunque sia la configurazione iniziale delle teste dell’idra e qualunque sia la strategia messa a punto da Ercole, Ercole riuscirà sempre a tagliarle tutte, anche se potrebbe aver bisogno di un tempo straordinariamente lungo per completare l’opera. Come per la convergenza delle successioni di Goodstein, la dimostrazione si basa sulla relazione tra alberi successivi ed una successione di ordinali strettamente decrescente. Come si può immaginare dal diagramma mostrato, l’albero diventa sempre più largo, ma la sua altezza è destinata a diminuire. Alla fine Ercole è in grado di eliminare tutte le teste che si trovano a più di un livello sopra la radice e a quel punto (come illustrato al passo 3) egli può tagliare le teste rimanenti una per una senza che se ne generino di nuove.

6. Lezioni tratte da questi esempi

Gli esempi in questa ‘vignette’ sono interessanti per molte ragioni. Prima di tutto essi mostrano che la logica matematica è rilevante ai fini di qualcosa di più che la metamatematica, che i teoremi come quello dell’incompletezza di Gödel ed oggetti quali gli ordinali transfiniti sono necessari per lo studio degli oggetti matematici ordinari come le successioni di interi e gli alberi matematici. Mostrando che una proprietà degli interi può essere dimostrata all’interno della teoria generale degli insiemi ma non all’interno dell’aritmetica di Peano, gli esempi richiamano la nostra attenzione anche al quadro teorico e linguistico dentro il quale si presentano le dimostrazioni. In questo caso essi mostrano che l’aritmetica di Peano è più debole della teoria generale degli insiemi.

Un’altra lezione che si trae da questi esempi è l’utilità dell’approcciarsi ad un problema più difficile (la convergenza di successioni di Goodstein generiche) modificandolo in uno più accessibile (la convergenza di successioni di Goodstein deboli). Inoltre, gli esempi mostrano come un esempio generico – una successione il cui valore iniziale sia – può illustrare tutte le caratteristiche importanti di un caso generale. Gli esempi sono anche istruttivi poiché illustrano i limiti della nostra intuizione. Le successioni che sembrano tendere ad infinito in realtà non lo fanno; esse in definitiva iniziano a decrescere e convergere a in un numero finito di passi. Infine, gli esempi ci rendono capaci di vedere sia la potenzialità sia i limiti della tecnologia dal momento che la tecnologia ci dà una percezione concreta della rapida crescita dei termini della successione, ma il suo uso è limitato se messo di fronte all’esplosione numerica generata dalla definizione della successione.

Note e riferimenti bibliografici.

[1] Elert, Glenn (1995-2007). The Chaos HypertextbookTM, Bodnar, M. & Ramsden P. Discrete Logistic Equation, Wolfram Demonstrations Project. Perrin, D. (2008). La suite logistique et le chaos.

[2] Lagarias, J. C. (2001) The Syracuse Problem. In Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer.

[3] Goodstein, R. L. (1944). On the Restricted Ordinal Theorem, Journal of Symbolic Logic, 9, 33-41.

[4] Il principio di buon ordinamento per gli interi afferma che se ogni elemento in un insieme di interi è più grande di un qualche intero allora ammette minimo.

[5] Hodgson B. (2004). Herculean of Sisyphean tasks? EMS Newsletter, March 2004, pp. 11-16.

[6] Dato un intero con , ogni intero positivo ammette un’unica scomposizione in base b: , dove tutti i sono interi compresi tra e e . Si osservi che . Questa è una generalizzazione del modo in cui scomponiamo i numeri usando la base dieci.

[7] Se , allora , , , e . Iniziando da , ogni termine successivo è minore di rispetto al termine precedente perché in ciascun caso la base è maggiore del termine precedente.

[8] Estendiamo le operazioni di somma e prodotto dagli interi ai numeri ordinali transfiniti, notando comunque che la commutatività dell’addizione e della moltiplicazione non si preservano.

[9] In generale, quando il termine dell’unità di è zero, allora il più piccolo termine di è della forma , dove è un intero positivo e . Perciò, dal momento che la base si è incrementata di e si sottrae al risultato, la scomposizione di finisce con

   

Quindi il coefficiente della più piccola potenza della base è ridotto di e il termine dell’unità diventa minore di rispetto alla nuova base.

[10] Le risposte sono le seguenti: quando e perciò . Per ottenere , si sostituisca la base con la base e si sottragga . Di conseguenza e quindi . Dato che la base di è e che , iniziando dall’indice le successioni e hanno esattamente gli stessi termini. Esse formano una successione aritmetica decrescente con differenza costante , da cui segue che .

[11] I termini di mostrati in Tabella 3 sono stati calcolati usando http://www.wolframalpha.com.

[12] Kirby, L. e Paris, J. (1982). Accessible Independence Results for Peano Arithmetic, Bulletin of the London Mathematical Society, 14, 285-293.

[13] Cichon, E. A. (1983). A Short Proof of Two Recently Discovered Independence Results Using Recursion Theoretic Methods, Proc. Amer. Math. Soc., 87, 704-706.

[14] Bauer, A. Java applet for the Hydra Game. (Se l’applet non funziona in un browser, provare in un altro.) Dehornoy, P. (2001) L’infini est-il nécessaire? Pour la Science, Dossier, e Dehornoy, P. (2009) Cantor et les infinis.

PDF