MEDIUM: Il concetto matematico di cui non potrei mai fare a meno: induzione e ricorsione
[Questo post è apparso originariamente su Medium. Lo archivio qua per comodità mia]
Per l’imminente Carnevale della Matematica gli amici di MaddMaths! hanno suggerito di parlare del concetto matematico di cui ciascuno di noi non potrebbe fare a meno. In realtà è tutto un trucco: per esempio non credo che nessuno di noi potrebbe fare a meno dell’addizione, ma non credo nemmeno che qualcuno si sia messo a fare un trattato per quanto minuscolo sull’addizione. E poi diciamocelo: se uno scende così in basso dovrebbe portare le sue considerazioni al passo logico successivo. Non pretendo che si parli di insiemistica, ma almeno seguire la strada di Leopold Kronecker, che oggidì è noto per il suo delta — no, non è un fiume — ma che pronunciò la famigerata frase “Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.” Come? Non sapete il tedesco? Vabbè, per questa volta ve la traduco letteralmente: “Il buon Dio ha creato i numeri interi, e tutto il resto è opera dell uomo.” Insomma, per Kronecker senza numeri interi (e senza Dio) non avremmo la matematica, e non è un caso che egli fu uno dei più feroci avversari del povero Georg Cantor che riteneva che ci si potesse avvicinare di più a Dio con i numeri transfiniti — nome tirato fuori dal cardinale di Santa Romana Chiesa Johannes Baptiste Franzelin: poi dite che matematica e teologia non vanno d’accordo… — ma sono andato troppo fuori strada.
Riprendiamo dunque i numeri interi, anzi semplicemente quelli naturali. Il concetto di cui io non potrei mai fare a meno sono in realtà due concetti, che però come vedremo sono interallacciati: l’induzione (matematica) e la ricorsione. Cominciamo con la prima, che è quella che viene probabilmente citata più a sproposito per l’ottima ragione che nessuno sa esattamente a cosa serve. Per forza è così: nel mondo reale induzione significa tipicamente divinare qualcosa a partire da una piccola quantità di dati e sperare di aver capito quello che sta succedendo, mentre in matematica nulla è lasciato al caso.
L’induzione è il quinto e ultimo degli Assiomi di Peano, quelli che definiscono i numeri naturali un po’ come i cinque postulati di Euclide definiscono — con qualche aiutino esterno — la geometria euclidea. Ecco qua il testo degli assiomi.
- Esiste un numero naturale, 0.
- Ogni numero naturale n ha un numero naturale successore, S(n).
- Numeri diversi hanno successori diversi.
- 0 non è il successore di alcun numero naturale.
- Ogni sottoinsieme di numeri naturali che contenga 0 e il successore di ogni suo elemento coincide con l’intero insieme dei numeri naturali.
Sono certo che vi sarete accorti che l’assioma dell’induzione in un certo senso stona accanto agli altri, proprio come il postulato delle parallele stona accanto agli altri. In quest’ultimo caso ci sono voluti duemila anni di tentativi di dimostrarlo prima di capire che era proprio qualcosa che dobbiamo per forza accettare se vogliamo fare della geometria euclidea, oppure possiamo sostituire con qualcos’altro e fare una geometria diversa. Anche in questo caso possiamo eliminarlo e restare con qualcosa d’altro, per esempio i numeri razionali o reali non negativi, ma onestamente non è che otteniamo qualcosa di così eccitante. Quello che a mio parere è fondamentale è un’altra cosa: l’assioma di induzione è un modo per impacchettare in una singola frase infinite affermazioni, tanto che gli assiomi di Peano non appartengono alla logica del primo ordine (il problema è che nella logica del primo ordine va benissimo usare i quantificatori ∀, “per ogni”, e ∃, “esiste”: ma li si può applicare solo su singole variabili, e non su sottoinsiemi qualunque), e quando si vuole definire l’aritmetica di tutti i giorni a partire dagli assiomi di Peano siamo costretti a spacchettarlo in infinite affermazioni del primo ordine (e inventarci un nuovo concetto, quello di schema di assiomi, per scriverle tutte in un normale foglio di carta usando caratteri di dimensione normale).
Pensatela come volete, ma se il buon Dio ha creato i numeri naturali il diavolo si è mezzo di mezzo, e ha fatto in modo che noi esseri umani finiti venissimo fregati e non potessimo gestirli tutti. Ma come, direte, non hai appena mostrato come l’assioma di induzione e lo schema di assiomi corrispondente ci permettono di fare tutto? Certo che lo permettono. Lo permettono proprio perché sono così potenti da fare sì che l’aritmetica di Peano sia sufficientemente complessa da creare un’arma di distruzione di massa: la proposizione di Gödel, quella che il suo teorema di incompletezza costruisce. Possiamo però pensare positivo: i teoremi di Gödel ci dicono che non possiamo dimostrare proprio tutto quello che è vero, ma l’induzione ci aiuta a dimostrare alcune di queste cose, e ce lo fa fare senza doverci preoccupare di andare fino all’infinito a verificare se continuano davvero a essere vere. Anche in questo caso abbiamo il rovescio della medaglia, di cui probabilmente non vi sarete mai accorti se avete solo studiato matematica.
Una dimostrazione per induzione è relativamente facile: si verifica che il caso iniziale è — di solito banalmente — verificato, e poi si fanno un po’ di conti formali per il caso generale. Ma vi siete mai chiesti come sapere qual è il teorema da dimostrare? L’induzione in un certo senso funziona da sola, ma non può metafisicamente fornire anche l’enunciato da dimostrare. Beh, per me questo è un altro motivo per cui non potrei fare a meno dell’induzione: essa mi ricorda che la matematica non è la successione definizioni-enunciati-dimostrazioni-esercizi che troviamo nei libri di testo, ma un modo per verificare la correttezza di idee e modelli del mondo reale. In un certo qual senso dobbiamo prima sporcarci le mani con la pratica e solo dopo metterci a sviluppare la teoria. Dite niente…
Come però dicevo all’inizio, l’induzione per me è solo una parte della storia, e non riesco a pensarla disgiunta dalla ricorsione. Nel Jargon File di Eric Raymond c’è una definizione icastica:
ricorsione, s.f.: vedi ricorsione
Questa è una bella battuta, ma i matematici — e gli informatici — sanno bene che la storia è un po’ più complicata… o forse più semplice, se la vediamo da un altro punto di vista. Prendiamo di nuovo i nostri assiomi di Peano: non è difficile dimostrare che ogni numero naturale diverso da 0 ha un predecessore. (Aiutino: se ne trovate uno che non ha un predecessore non riuscite a far valere il quinto postulato. Ve l’avevo detto che l’induzione c’entrava). Ma questo significa che partendo da un qualunque numero naturale e tornando indietro prima o poi si arriva a 0. Ecco qua il trucco dietro la ricorsione: è vero che per dimostrare ricorsivamente una proposizione P(n) ti rifai alla proposizione P(m) che a prima vista è uguale, ma hai che m<n, e quindi sei sicuro che a un certo punto arrivi a 0 o comunque a un punto dove metti i respingenti, blocchi il percorso della ricorsione e dai il risultato di quel singolo caso particolare, che man mano verrà riportato su per la scala delle varie proposizioni intermedie per ricavare finalmente il risultato richiesto.
Tutto questo passare in giù e in su è tipicamente matematico, ne convengo: in teoria funziona perfettamente ed è anche esprimibile in modo semplice, in pratica se ho la successione di Fibonacci definita ricorsivamente come F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) e voglio trovare F(10000) forse è meglio che vada a cercare qualche altro sistema che non sia calcolare tutti e 10000 i termini della successione. I matematici, nonostante quello che sembri, sono persone ragionevoli almeno per il loro metro di giudizio: è nata così la teoria delle funzioni generatrici che permette di trovare una “forma chiusa” (un’equazione, per dirla in maniera semplice) a partire da una successione ricorsiva. Ma anche in questo caso andrei fuori dal seminato se mi mettessi a parlare di funzioni generatrici.
In definitiva, induzione e ricorsione sono il nostro modo di ottenere risultati generali lavorando sempre sul locale: una esemplificazione del detto che passo dopo passo si può arrivare dovunque. Come si può farne a meno?
Leave a comment