Qualche giorno fa ho
iniziato a parlare dell’induzione matematica.
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)2. 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)2, cioè n2+2n+1. Facendo la somma otteniamo n2+4n+4, che guarda caso vale proprio (n+2)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?
Ultimo aggiornamento: 2010-03-08 07:00
Chi volesse capire perché può guardare qui o, se ha occhi che distinguono bene le sfumature di colore, qui.
C’è non poca gente – soprattutto adolescenti – che scopre questo risultato autonomamente e, spesso, resta frustrata dalla propria incapacità di dimostrarlo, di solito formulata come “ma è vero per tutti i numeri? Io ho controllato fino a N”. Secondo me fare teoremi per il puro piacere di farlo è un istinto innato in quasi tutti gli esseri umani, che viene di solito soffocato dalla scuola.
@Barbara: alle superiori una mia prof di matematica (una toscanaccia) ci faceva fare per esercizio dimostrazioni di geometria piana e alcune piccole cose di algebra. Ho un buon ricordo di lei, anche se una volta in fondo al compito in classe anziché CVD mi scrisse CVC (Come volevasi Cannare) esponendomi al pubblico ludibrio :-).
Non tutti i ragazzi vedono il processo dimostrativo come naturale in sè, ma secondo me è la curiosità innata nei giovani nel tentare di capire qualcosa che li incuriosisca che è la chiave di tutto. E la scuola, tranne alcune persone che con il loro talento riescono a fare diversamente, fa di tutto per sopire questa nobile pulsione.
@Daniele: adesso posso spiegare la mia risposta.
La dimostrazione del passo induttivo è indubbiamente deduttiva, come del resto tutte le dimostrazioni matematiche: la matematica è una gigantesca tautologia, e la parte più importante in un certo senso sono le definizioni (da cui appunto si deduce tutto il resto).
Però il passare da un numero indefinito di passi induttivi a dire che la proposizione vale per tutti gli interi è un salto logico che non è affatto deduttivo, ma è in un certo senso un atto di fede (se preferisci, lo si deve mettere come assioma: la cosa è in fin dei conti la stessa). L’induzione è insomma quel passaggio; il fatto che noi non lo percepiamo come tale implica semplicemente che dopo quasi un secolo e mezzo siamo così abituati a lavorare con l’infinito attuale che non ci sorprendiamo più della cosa.
(Mi scuso per la filosofumena: non sapendo più fare matematica passo alla filosofia come fanno in tanti)
Sui cavalli: no.
Ovviamente c’è un piccolo errore nella dimostrazione ;-)
Per induzione si può dimostrare che un uomo non ha orecchie.
La matematica applicata alla medicina non fa tanto bene. Ma un medico come me applicato ad un matematico, il mio ragazzo, si! ;-)
Dopo aver visto questo video ho avuto l’onore di farmi spiegare cos’è l’induzione.
L’induzione matematica [1/2]
che cos’è l’induzione?
@Kualunque: la matematica ha importanti applicazioni alla medicina, ma i medici non le conoscono. Ad esempio a suo tempo ho dovuto spiegare al mio medico curante cos’è l’astigmatismo e perché si indica con due numeri (e non con uno come la miopia).
A me questa faccenda dell’indecidibilità fa venire un mal di pancia che non ti dico.
“Il vantaggio del matematico, se volete, è che non si sporca le mani” parla per te :-). Io faccio i conti alla lavagna e sono sempre sporca di gesso.
@ .mau.: Ben vengano le filosoferie! Non sono sicurissimo di aver capito: intendi che anche se l’induzione matematica è formalmente un procedimento deduttivo (applico fatti già dimostrati e assiomi per dimostrare qualcosa) psicologicamente porta a qualcosa di “più nuovo” rispetto ad altri tipi di ragionamento?
@daniele: provo a ridirlo in maniera diversa
– se tu dimostri come ho fatto che dato un qualsiasi numero dispari 2n-1 la somma dei numeri da 1 a 2n-1 è pari a n2, allora stai facendo deduzione.
– se tu dici che per tutti i numeri dispari 2n-1 la somma dei numeri da 1 a 2n-1 è pari a n2, allora quella è induzione.
Tornando alla filosofia, è la differenza tra l’infinito potenziale (Euclide dice che tu puoi estendere una retta quanto vuoi, ma in pratica usa sempre un segmento) e l’infinito attuale (per noi la retta è infinita e basta). Riconosco che non è affatto un concetto banale, e non è un caso che ci siano voluti due millenni e mezzo per trovare una quadra.
@ .mau.: Allora se ho ben capito stai parlando di due induzioni diverse. Una è quella deduttiva, giustificata dall’opportuno assioma di Peano, mentre l’altra è una vera induzione euristica, più simile a quello che fa uno scienziato sperimentale, di chi, facendo ricerca o anche solo capendo per conto suo qualcosa di noto da millenni, intuisce che qualcosa vale per tutti i naturali (e poi eventualmente lo dimostrerà comme il faut).
In fondo, ogni volta che diciamo “e così via” – in matematica e fuori – stiamo facendo un’induzione “vera” che non sempre si può o si vuole dimostrare…
@daniele: no, o meglio io come matematico non parlo dell’induzione euristica e ritengo che l’aggiunta dell’assioma di Peano vada fuori dalla deduzione. Se qualcun altro dei miei ventun lettori vuole aggiungere qualcosa, è il benvenuto!
@Barbara:
beh, in fondo confermi l’ipotesi di .mau.: il gesso è evidentemente “una penna che perde”.
Ricorsione
due parole sulla ricorsione, o come si può definire una cosa per mezzo di sé stessa.
Sappiate che tutto ciò è inutile perché Edward Nelson (http://en.wikipedia.org/wiki/Edward_Nelson) in una conferenza recente al Dipartimento di matematica di Milano ha assicurato che entro due anni dimostrerà l’incoerenza degli assiomi di Peano. ;-) :-p