{"id":175046010,"date":"2015-11-14T21:08:14","date_gmt":"2015-11-14T21:08:14","guid":{"rendered":"http:\/\/xmau.com\/wp\/archivi\/?p=175046010"},"modified":"2015-11-16T08:31:07","modified_gmt":"2015-11-16T08:31:07","slug":"medium-il-concetto-matematico-di-cui-non-potrei-mai-fare-a-meno-induzione-e-ricorsione","status":"publish","type":"post","link":"https:\/\/xmau.com\/archivi\/2015\/11\/14\/medium-il-concetto-matematico-di-cui-non-potrei-mai-fare-a-meno-induzione-e-ricorsione\/","title":{"rendered":"MEDIUM: Il concetto matematico di cui non potrei mai fare a meno: induzione e ricorsione"},"content":{"rendered":"

[Questo post \u00e8 apparso originariamente su Medium<\/a>. Lo archivio qua per comodit\u00e0 mia]<\/p>\n

Per l\u2019imminente Carnevale della Matematica gli amici di MaddMaths!<\/a> hanno suggerito di parlare del concetto matematico di cui ciascuno di noi non potrebbe fare a meno. In realt\u00e0 \u00e8 tutto un trucco: per esempio non credo che nessuno di noi potrebbe fare a meno dell\u2019addizione, ma non credo nemmeno che qualcuno si sia messo a fare un trattato per quanto minuscolo sull\u2019addizione. E poi diciamocelo: se uno scende cos\u00ec 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<\/a>, che oggid\u00ec \u00e8 noto per il suo delta\u200a\u2014\u200ano, non \u00e8 un fiume\u200a\u2014\u200ama che pronunci\u00f2 la famigerata frase \u201cDie ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.<\/em>\u201d Come? Non sapete il tedesco? Vabb\u00e8, per questa volta ve la traduco letteralmente: \u201cIl buon Dio ha creato i numeri interi, e tutto il resto \u00e8 opera dell uomo.\u201d Insomma, per Kronecker senza numeri interi (e senza Dio) non avremmo la matematica, e non \u00e8 un caso che egli fu uno dei pi\u00f9 feroci avversari del povero Georg Cantor che riteneva che ci si potesse avvicinare di pi\u00f9 a Dio con i numeri transfiniti\u200a\u2014\u200anome tirato fuori dal cardinale di Santa Romana Chiesa Johannes Baptiste Franzelin: poi dite che matematica e teologia non vanno d\u2019accordo\u2026\u200a\u2014\u200ama sono andato troppo fuori strada.<\/p>\n

Riprendiamo dunque i numeri interi, anzi semplicemente quelli naturali. Il concetto di cui io<\/strong> non potrei mai fare a meno sono in realt\u00e0 due concetti, che per\u00f2 come vedremo sono interallacciati: l\u2019induzione<\/strong> (matematica) e la ricorsione<\/strong>. Cominciamo con la prima, che \u00e8 quella che viene probabilmente citata pi\u00f9 a sproposito per l\u2019ottima ragione che nessuno sa esattamente a cosa serve. Per forza \u00e8 cos\u00ec: nel mondo reale induzione significa tipicamente divinare qualcosa a partire da una piccola quantit\u00e0 di dati e sperare di aver capito quello che sta succedendo, mentre in matematica nulla \u00e8 lasciato al caso.<\/p>\n

L\u2019induzione \u00e8 il quinto e ultimo degli Assiomi di Peano<\/a><\/strong>, quelli che definiscono i numeri naturali un po\u2019 come i cinque postulati di Euclide definiscono\u200a\u2014\u200acon qualche aiutino esterno\u200a\u2014\u200ala geometria euclidea. Ecco qua il testo degli assiomi.<\/p>\n

    \n
  1. Esiste un numero naturale, 0.<\/li>\n
  2. Ogni numero naturale n<\/em> ha un numero naturale successore, S(n).<\/li>\n
  3. Numeri diversi hanno successori diversi.<\/li>\n
  4. 0 non \u00e8 il successore di alcun numero naturale.<\/li>\n
  5. Ogni sottoinsieme di numeri naturali che contenga 0 e il successore di ogni suo elemento coincide con l\u2019intero insieme dei numeri naturali.<\/li>\n<\/ol>\n

    Sono certo che vi sarete accorti che l\u2019assioma dell\u2019induzione in un certo senso stona accanto agli altri, proprio come il postulato delle parallele stona accanto agli altri. In quest\u2019ultimo 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\u2019altro e fare una geometria diversa. Anche in questo caso possiamo eliminarlo e restare con qualcosa d\u2019altro, per esempio i numeri razionali o reali non negativi, ma onestamente non \u00e8 che otteniamo qualcosa di cos\u00ec eccitante. Quello che a mio parere \u00e8 fondamentale \u00e8 un\u2019altra cosa: l\u2019assioma di induzione \u00e8 un modo per impacchettare in una singola frase infinite affermazioni<\/strong>, tanto che gli assiomi di Peano non appartengono alla logica del primo ordine (il problema \u00e8 che nella logica del primo ordine va benissimo usare i quantificatori \u2200, \u201cper ogni\u201d, e \u2203, \u201cesiste\u201d: ma li si pu\u00f2 applicare solo su singole variabili, e non su sottoinsiemi qualunque), e quando si vuole definire l\u2019aritmetica 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).<\/p>\n

    Pensatela come volete, ma se il buon Dio ha creato i numeri naturali il diavolo si \u00e8 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\u2019assioma di induzione e lo schema di assiomi corrispondente ci permettono di fare tutto? Certo che lo permettono. Lo permettono proprio perch\u00e9 sono cos\u00ec potenti da fare s\u00ec che l\u2019aritmetica di Peano sia sufficientemente complessa da creare un\u2019arma di distruzione di massa: la proposizione di G\u00f6del<\/strong>, quella che il suo teorema di incompletezza costruisce. Possiamo per\u00f2 pensare positivo: i teoremi di G\u00f6del ci dicono che non possiamo dimostrare proprio tutto quello che \u00e8 vero, ma l\u2019induzione ci aiuta a dimostrare alcune di queste cose, e ce lo fa fare senza doverci preoccupare di andare fino all\u2019infinito 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.<\/p>\n

    Una dimostrazione per induzione \u00e8 relativamente facile: si verifica che il caso iniziale \u00e8\u200a\u2014\u200adi solito banalmente\u200a\u2014\u200averificato, e poi si fanno un po\u2019 di conti formali per il caso generale. Ma vi siete mai chiesti come sapere qual \u00e8 il teorema da dimostrare<\/strong>? L\u2019induzione in un certo senso funziona da sola, ma non pu\u00f2 metafisicamente fornire anche l\u2019enunciato da dimostrare. Beh, per me questo \u00e8 un altro motivo per cui non potrei fare a meno dell\u2019induzione: essa mi ricorda che la matematica non \u00e8 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\u2026<\/p>\n

    Come per\u00f2 dicevo all\u2019inizio, l\u2019induzione per me \u00e8 solo una parte della storia, e non riesco a pensarla disgiunta dalla ricorsione<\/strong>. Nel Jargon File<\/em> di Eric Raymond c\u2019\u00e8 una definizione icastica:<\/p>\n

    ricorsione<\/strong>, s.f.: vedi<\/em> ricorsione<\/p><\/blockquote>\n

    Questa \u00e8 una bella battuta, ma i matematici\u200a\u2014\u200ae gli informatici\u200a\u2014\u200asanno bene che la storia \u00e8 un po\u2019 pi\u00f9 complicata\u2026 o forse pi\u00f9 semplice, se la vediamo da un altro punto di vista. Prendiamo di nuovo i nostri assiomi di Peano: non \u00e8 difficile dimostrare che ogni numero naturale diverso da 0 ha un predecessore. (Aiutino: se ne trovate uno che non ha un predecessore<\/strong> non riuscite a far valere il quinto postulato. Ve l\u2019avevo detto che l\u2019induzione c\u2019entrava). Ma questo significa che partendo da un qualunque numero naturale e tornando indietro<\/strong> prima o poi si arriva a 0. Ecco qua il trucco dietro la ricorsione: \u00e8 vero che per dimostrare ricorsivamente una proposizione P(n<\/em>) ti rifai alla proposizione P(m<\/em>) che a prima vista \u00e8 uguale, ma hai che m<\/em><n<\/em>, 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\u00e0 riportato su per la scala delle varie proposizioni intermedie per ricavare finalmente il risultato richiesto.<\/p>\n

    Tutto questo passare in gi\u00f9 e in su \u00e8 tipicamente matematico, ne convengo: in teoria funziona perfettamente ed \u00e8 anche esprimibile in modo semplice, in pratica se ho la successione di Fibonacci definita ricorsivamente come F(0)=0, F(1)=1, F(n<\/em>)=F(n<\/em>-1)+F(n<\/em>-2) e voglio trovare F(10000) forse \u00e8 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: \u00e8 nata cos\u00ec la teoria delle funzioni generatrici<\/em> che permette di trovare una \u201cforma chiusa\u201d (un\u2019equazione, 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.<\/p>\n

    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\u00f2 arrivare dovunque. Come si pu\u00f2 farne a meno?<\/p>\n","protected":false},"excerpt":{"rendered":"

    [Questo post \u00e8 apparso originariamente su Medium. Lo archivio qua per comodit\u00e0 mia] Per l\u2019imminente Carnevale della Matematica gli amici […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[40],"class_list":["post-175046010","post","type-post","status-publish","format-standard","hentry","category-archivi","tag-medium"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yH-bQtsK","_links":{"self":[{"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/posts\/175046010","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/comments?post=175046010"}],"version-history":[{"count":2,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/posts\/175046010\/revisions"}],"predecessor-version":[{"id":175046015,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/posts\/175046010\/revisions\/175046015"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/media?parent=175046010"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/categories?post=175046010"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/archivi\/wp-json\/wp\/v2\/tags?post=175046010"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}