L’induzione matematica [1/2]

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!
[non è tutto qua, vai alla seconda parte]

Ultimo aggiornamento: 2010-03-05 07:00

11 pensieri su “L’induzione matematica [1/2]

  1. max

    La lettura di questo articolo mi ha portato ai tempi dell’universita’ quando, iscritto a scienze dell’informazione, cercavo di capire questo metodo invano. Forse e’ anche un po’ colpa sua se ho lasciato Pisa per un’altro ateneo. Forse aveva ragione l’autore David Ruelle quando diceva che per fare matematica ci vuole le idee molto chiare ed io, evidentemente, non le avevo affatto.
    Aspetto la seconda parte :)

  2. Barbara

    @max: “per fare matematica ci vuole le idee molto chiare” “un’altro ateneo”. La matematica è un linguaggio con delle regole ben precise (gli assiomi di Peano sono fra queste). Mi pare naturale che chi ha già dei problemi con la grammatica della propria lingua la trovi difficile :-P.
    Anche nel mio caso ci sono ricordi sgradevoli: durante la prima esercitazione post-assiomi, mi hanno mandata alla lavagna a dimostrare la proprietà commutativa dell’addizione usando solo gli assiomi di Peano e la definizione induttiva. Alla fine me la sono cavata, ma solo dopo numerosi suggerimenti da parte dell’esercitatore, fetentemente ridacchiante. Ed era pure il mio compleanno.

  3. Daniele A. Gewurz

    .mau., visto che la fai tanto lunga con la deduzione, l’abduzione e l’induzione, forse potresti menzionare il fatto che l’induzione (matematica) in realtà è un procedimento deduttivo! Oppure sto “spoilando” qualcosa che devi dire nella seconda parte?

  4. .mau.

    @barbara: e come si fa? a+a = a+a e vai per induzione sulla differenza tra i due addendi?
    @daniele: ehm… (la seconda parte è già scritta, uscirà lunedì) Però non sono del tutto d’accordo, e la ragione la spiegherò nei commenti lunedì.

  5. Barbara

    @.mau.: induzione doppia partendo da 0+0=0. La definizione (totalmente asimmetrica) è a+0=a, a+Sb=S(a+b) dove S è il successore. Non saprei come fare l’induzione sulla differenza visto che ancora la differenza non l’hai neanche definita :).
    Lascio a te indovinare il nome dell’esercitatore, ma ti dò un aiutino: non era di algebra.

  6. .mau.

    lo so che la differenza non è ancora definita, ma nella mia idea la si definiva nel mezzo della dimostrazione.

  7. Daniele A. Gewurz

    @ L.A.Bachevskij: sì, ma in effetti stiamo facendo k dimostrazioni distinte (se il passo è di lunghezza k), una per i multipli di k, una per i naturali congrui a 1 modulo k, e così via.
    Sempre a proposito di apparenti “casi base molteplici”, una cosa non sempre facilissima da spiegare è la situazione in cui bisogna svolgere a mano alcuni dei primi casi, prima che ingrani il ragionamento che va bene per tutti gli n. Questo succede soprattutto con l’induzione forte, per esempio per dimostrare qualche proprietà di una successione definita ricorsivamente.
    Diciamo di voler dimostrare che per tutti gli n maggiori di 11 si può esprimere n come somma di un multiplo di 4 e di un multiplo di 5. Il caso base è uno solo, e cioè che 12 è uguale a 3 per 4 e quindi soddisfa la tesi. L’idea per l’n generico è che se gli sottraiamo 4, ricadiamo in un caso noto. Quindi bisogna fare a mano anche 13, 14 e 15. Ma questi non sono, come pensa qualcuno, ulteriori casi base. Sono i primi tre passi dell’induzione che, accidentalmente, vanno dimostrati in modo diverso dagli altri.

I commenti sono chiusi.