.mau. - Matematica Light - L'induzione matematica

L'induzione matematica

Lo sappiamo tutti: Sherlock Holmes è il principe della deduzione. Almeno, ci è sempre stato venduto in questo modo, anche se poi a guardar bene anche l'investigatore dal naso adunco – o meglio Arthur Conan Doyle – spesso barava e tirava fuori dal cappello alcune informazioni che non erano state date al lettore, oppure giungeva a conclusioni non certe ma altamente probabili. I filosofi affermano che il metodo holmesiano si dovrebbe più correttamente definire abduzione, come lo pseudosillogismo che da una premessa maggiore corretta ("tutti gli uomini sono mortali") e una minore molto probabile ("Giulio Andreotti dovrebbe essere un uomo") conclude con una conseguenza molto probabile ("si presume che prima o poi Andreotti morirà"). A proposito di abduzione, attenti ai falsi amici! In inglese "abduction" è il rapimento, soprattutto se da parte di alieni... ma non divaghiamo.

Il vero regno del campo deduttivo è naturalmente la matematica, dove si inizia a mettere i paletti (gli assiomi e i postulati) e da lì si va man mano avanti a dedurre i vari teoremi, come abbiamo tutti imparato quando abbiamo studiato geometria. Se ci pensarte un po', però, la deduzione è un percorso in un certo qual senso sterile; tutto quello che deduciamo, per quanto possa sembrare incredibile – avete presente il cosiddetto teorema di Napoleone? Se si disegnano le trisettrici di un triangolo qualunque, queste si incontrano a due a due nei vertici di un triangolo equilatero – era già presente in nuce negli assiomi e postulati iniziali. Non abbiamo inventato nulla, ma solo scoperto quello che c'era già fin dall'inizio. Ripensandoci, non è affatto strano che la gran maggioranza dei matematici sia fondamentalmente della scuola platonista; a furia di trarre conseguenze logiche di quello che hai, ti inizia a sorgere il dubbio che gli enti matematici sono tutti lì da qualche parte, un po' come in Flatterlandia.

Eppure anche in matematica c'è un modo per tirare fuori qualcosa di nuovo: l'induzione ("induzione matematica" se si vuole fare i precisini, ma in genere l'aggettivo si omette perché è chiaro che si sta facendo matematica). Anche nel mondo di tutti i giorni si parla di "procedimento induttivo" , ma in realtà è tutta un'altra cosa; si vedono alcune correlazioni, per esempio che quando spunta il sole settembrino dopo un temporale si trovano molti funghi, e si stabilisce una legge generale, che il sole dopo la pioggia faccia crescere i funghi. Tale legge può però essere vera o falsa, ed è solo un risultato empirico che fa rabbrividire un qualunque matematico se applicato alla propria scienza. Qui si tratta di qualcosa di completamente diverso.

La formalizzazione dell'induzione matematica è stata data da Giuseppe Peano nella sua definizione dei numeri naturali. Gli assiomi di Peano sono cinque, come i postulati della geometria euclidea; l'induzione è l'ultimo e il più complicato da spiegare, proprio come in geometria euclidea. Dopo avere stabilito per legge che 0 è un numero, che esiste una funzione S ("successore") tale che se n è un numero anche S(n) è un numero ("per quanto grande sia un numero, posso sommarci uno"), che non esiste un numero x tale che S(x) = 0 ("zero è il primo numero"), e che se ci sono due numeri m e n per cui S(m) = S(n) allora m = n ("posso mettere tutti i numeri in fila"), il quinto assioma dice che "Se una proprietà P vale per 0 – cioè P(0) è vera – e sappiamo inoltre che se P vale per n allora vale anche per S(n), allora P vale per tutti i numeri naturali". Per amor di precisione, il quinto assioma di Peano afferma che non ci sono altri numeri naturali al di fuori di questi, ma è un punto secondario. In un certo senso, questo quinto assioma ricorda il postulato delle parallele: molto più complicato degli altri, uno si chiede se è proprio necessario e non si possa invece farne a meno. La risposta è però molto diversa, come vedremo subito.

La cosa che dovrebbe subito saltare alla vista è che il quinto assioma di Peano, a differenza degli altri, tratta con l'infinito. Gli altri assiomi lavorano tutti con un numero o due; anche dire "se esiste il numero un fantastiliardo, allora esiste anche un fantastiliardo e uno" è una proprietà locale. Col quinto assioma, invece, dobbiamo prendere tutti i numeri contemporaneamente. L'immagine che io ho in mente è quella di un numero infinito di tessere del domino messe ritte in piedi una vicina all'altra. Forse avete visto quei video in cui ci si limita a dare un colpetto alla prima tessera, che cadendo tocca la seconda che a sua volta cade colpendo la terza... finché tutta la costruzione finisce giù per terra. Ecco, l'induzione è esattamente la stessa cosa, solo che le tessere sono infinite. Per la cronaca, esistono due definizioni di induzione: nell'induzione forte, invece che solo per n, la proprietà P deve valere per tutti i numeri inferiori o uguali a n, perché valga anche per n+1. Ma in realtà le due formulazioni sono equivalenti, e si può scegliere l'una o l'altra a seconda della comodità. Inoltre non è affatto detto che l'ipotesi induttiva debba partire necessariamente da 0; la proprietà può essere valida da un certo numero k, e ovviamente il risultato sarà valido per ogni intero maggiore o uguale a k. Così, se vogliamo dimostrare per induzione che la somma degli angoli di un poligono convesso di n lati è pari a n-2 angoli piatti, partiremo dal triangolo e non certo da un ipotetico poligono con zero lati!

Dopo aver parlato di induzione solo dal punto di vista teorico, vediamo un esempio esplicito di dimostrazione per induzione, mostrando che la somma dei numeri dispari da 1 a 2n+1 è uguale a (n+1)². Il passo iniziale è semplicissimo: quando n=0, la somma dei numeri da 1 a 1 fa 1, che è esattamente il quadrato di 1. Più facile vederlo che spiegarlo. Immaginiamo ora che l'ipotesi valga fino a un certo n, e proviamo a vedere cosa succede con n+1. La somma dei numeri dispari da 1 a 2(n+1)+1, cioè da 1 a 2n+3, è pari a 2n+3 più la somma dei numeri dispari da 1 a 2n+1, che per ipotesi induttiva è (n+1)², cioè n²+2n+1. Facendo la somma otteniamo n²+4n+4, che guarda caso vale proprio (n+2)². Fine della dimostrazione: con un solo caso generale abbiamo dimostrato l'ipotesi per gli infiniti casi particolari.

Tutto questo è bellissimo, ma siete stati attenti c'è qualcosa che non va.Il guaio non è nella dimostrazione, che non è poi così difficile: si fanno giusto un po' di giochetti formali coi numeri e si arriva al risultato, e questo capita spesso quando si usa l'induzione, tanto che a volte mi chiedo se nessuno abbia mai fatto un sistema di intelligenza artificiale che sappia risolvere problemi per induzione. Ma come facevamo a sapere che il risultato era proprio quello indicato nel teorema? Chi ce l'ha suggerito? Insomma, l'induzione è un bieco trucco; riusciamo solo a dimostrare qualcosa che conosciamo già. La cosa è spiazzante soprattutto per chi è rimasto alla concezione che purtroppo viene insegnata a scuola, vale a dire che la matematica sia qualcosa di perfettamente lucidato, con i teoremi che sono così perché non potrebbero essere diversi, e che scendono dall'alto come novelli deus ex machina. No, non è affatto così. La matematica avanza per tentativi ed errori, ed è solo in un secondo tempo che ci si affretta a togliere tutte le impalcature e lasciare solo il risultato finale per l'ammirazione del popolo. Per quanto riguarda l'induzione, quello che succede di solito è che il matematico fa un'ipotesi su quale possa essere il risultato, e poi controlla se ha ragione; proprio come un meccanico che ascolta il rumore di un motore e fa una diagnosi. Il vantaggio del matematico, se volete, è che non si sporca le mani... a meno che la penna con cui sta scrivendo non perda inchiostro!

Do solo un accenno a un'estensione del principio di induzione, che potete tranquillamente lasciar che è un parallelo della teoria cantoriana degli infiniti. L'induzione classica si applica all'infinito numerabile, ma si può anche parlare di induzione transfinita; in questo caso su dice che "se una proprietà P vale per zero, e quando vale per tutti gli ordinali minori di ψ, allora P vale anche per ψ, allora vale per tutti gli ordinali." Come in tutte queste eteree proprietà logiche, l'induzione transfinita è indipendente da quella standard, nel senso che uno può accettarla oppure no e il resto della matematica va avanti tranquillo; se lo si accetta, però, l'induzione standard ci viene data gratis. Un esempio a riguardo è il teorema di Goodstein, che non è decidibile usando gli assiomi di Peano ma è vero se si ammette l'induzione transfinita.

Termino con un paradosso matematico basato sull'induzione, che "dimostra" come tutti i cavalli sono dello stesso colore. Prendiamo un insieme di n cavalli. Nel caso n=1 la tesi è banalmente vera. Per un n qualunque, numeriamo i cavalli e togliamo il numero 1. Rimangono n-1 cavalli, che per ipotesi induttiva sono tutti dello stesso colore. Ma se rimettiamo il numero 1 e ne togliamo un altro, abbiamo di nuovo n-1 cavalli, che sono sempre dello stesso colore di prima. A questo punto, visto che i due insiemi hanno un'intersezione in comune, è chiaro che tutti e n i cavalli sono dello stesso colore. O no?