{"id":7733,"date":"2010-03-08T07:00:00","date_gmt":"2010-03-08T07:00:00","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2010\/03\/08\/linduzione_mate_1\/"},"modified":"2010-03-08T07:00:00","modified_gmt":"2010-03-08T07:00:00","slug":"linduzione_mate_1","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2010\/03\/08\/linduzione_mate_1\/","title":{"rendered":"L&#8217;induzione matematica [2\/2]"},"content":{"rendered":"<p><a href=\"http:\/\/xmau.com\/notiziole\/arch\/201003\/006416.html\">Qualche giorno fa <\/a>ho<br \/>\niniziato a parlare dell&#8217;induzione matematica.<br \/>\nDopo 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 2<i>n<\/i>+1 \u00e8 uguale a (<i>n<\/i>+1)<sup>2<\/sup>. Il passo iniziale \u00e8 semplicissimo: quando <i>n<\/i>=0, la somma dei numeri da 1 a 1 fa 1, che \u00e8 esattamente il quadrato di 1. Pi\u00f9 facile vederlo che spiegarlo. Immaginiamo ora che l&#8217;ipotesi valga fino a un certo <i>n<\/i>, e proviamo a vedere cosa succede con <i>n<\/i>+1. La somma dei numeri dispari da 1 a 2<i>(n+1)<\/i>+1, cio\u00e8 da 1 a 2<i>n<\/i>+3, \u00e8 pari a 2<i>n<\/i>+3 pi\u00f9 la somma dei numeri dispari da 1 a 2<i>n<\/i>+1, che per ipotesi induttiva \u00e8 (<i>n<\/i>+1)<sup>2<\/sup>, cio\u00e8 <i>n<\/i><sup>2<\/sup>+2<i>n<\/i>+1. Facendo la somma otteniamo <i>n<\/i><sup>2<\/sup>+4<i>n<\/i>+4, che guarda caso vale proprio (<i>n<\/i>+2)<sup>2<\/sup>. Fine della dimostrazione: con un solo caso generale abbiamo dimostrato l&#8217;ipotesi per gli infiniti casi particolari.<br \/>\nTutto questo \u00e8 bellissimo, ma siete stati attenti c&#8217;\u00e8 qualcosa che non va.Il guaio non \u00e8 nella dimostrazione, che non \u00e8 poi cos\u00ec difficile: si fanno giusto un po&#8217; di giochetti formali coi numeri e si arriva al risultato, e questo capita spesso quando si usa l&#8217;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&#8217;ha suggerito? Insomma, l&#8217;induzione \u00e8 un bieco trucco; riusciamo solo a dimostrare qualcosa che conosciamo gi\u00e0. La cosa \u00e8 spiazzante soprattutto per chi \u00e8 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\u00ec perch\u00e9 non potrebbero essere diversi, e che scendono dall&#8217;alto come novelli deus ex machina. No, non \u00e8 affatto cos\u00ec. La matematica avanza per tentativi ed errori, ed \u00e8 solo in un secondo tempo che ci si affretta a togliere tutte le impalcature e lasciare solo il risultato finale per l&#8217;ammirazione del popolo. Per quanto riguarda l&#8217;induzione, quello che succede di solito \u00e8 che il matematico fa un&#8217;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, \u00e8 che non si sporca le mani&#8230; a meno che la penna con cui sta scrivendo non perda inchiostro!<br \/>\nDo solo un accenno a un&#8217;estensione del principio di induzione, che potete tranquillamente lasciar che \u00e8 un parallelo della teoria cantoriana degli infiniti. L&#8217;induzione classica si applica all&#8217;infinito numerabile, ma si pu\u00f2 anche parlare di <b>induzione transfinita<\/b>; in questo caso su dice che &#8220;se una propriet\u00e0 P vale per zero, e quando vale per tutti gli ordinali minori di &psi;, allora P vale anche per &psi;, allora vale per tutti gli ordinali.&#8221; Come in tutte queste eteree propriet\u00e0 logiche, l&#8217;induzione transfinita \u00e8 indipendente da quella standard, nel senso che uno pu\u00f2 accettarla oppure no e il resto della matematica va avanti tranquillo; se lo si accetta, per\u00f2, l&#8217;induzione standard ci viene data gratis. Un esempio a riguardo \u00e8 il <a href=\"http:\/\/it.wikipedia.org\/wiki\/Teorema_di_Goodstein\">teorema di Goodstein<\/a>, che non \u00e8 decidibile usando gli assiomi di Peano ma \u00e8 vero se si ammette l&#8217;induzione transfinita.<br \/>\nTermino con un paradosso matematico basato sull&#8217;induzione, che &#8220;dimostra&#8221; come tutti i cavalli sono dello stesso colore. Prendiamo un insieme di <i>n<\/i> cavalli. Nel caso <i>n<\/i>=1 la tesi \u00e8 banalmente vera. Per un <i>n<\/i> qualunque, numeriamo i cavalli e togliamo il numero 1. Rimangono <i>n<\/i>-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 <i>n<\/i>-1 cavalli, che sono sempre dello stesso colore di prima. A questo punto, visto che i due insiemi hanno un&#8217;intersezione in comune, \u00e8 chiaro che tutti e <i>n<\/i> i cavalli sono dello stesso colore. O no?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>seconda parte delle spiegazioni sull&#8217;induzione matematica.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[214],"tags":[],"class_list":["post-7733","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-20J","jetpack-related-posts":[{"id":30274,"url":"https:\/\/xmau.com\/notiziole\/2025\/01\/01\/buon-2025-matematico\/","url_meta":{"origin":7733,"position":0},"title":"Buon 2025 matematico!","author":".mau.","date":"2025-01-01","format":false,"excerpt":"Il 2025 \u00e8 un anno il cui valore ha molte propriet\u00e0 matematiche, come racconta Greg Ross: \u00c8 un quadrato (45\u00b2). \u00c8 il prodotto di due quadrati (9\u00b2 \u00d7 5\u00b2). \u00c8 la somma dei cubi dei primi nove numeri naturali (1\u00b3 + 2\u00b3 + 3\u00b3 + 4\u00b3 + 5\u00b3 + 6\u00b3\u2026","rel":"","context":"In &quot;giochi&quot;","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":29485,"url":"https:\/\/xmau.com\/notiziole\/2024\/08\/14\/e-allora-cose-una-dimostrazione-elegante\/","url_meta":{"origin":7733,"position":1},"title":"E allora cos&#8217;\u00e8 una dimostrazione elegante?","author":".mau.","date":"2024-08-14","format":false,"excerpt":"questo \u00e8 pi\u00f9 difficile da definire, almeno per me","rel":"","context":"In &quot;mate-light-2024&quot;","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/08\/quadrato-300x289.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":32915,"url":"https:\/\/xmau.com\/notiziole\/2025\/06\/25\/il-problema-di-langford-ii\/","url_meta":{"origin":7733,"position":2},"title":"Il problema di Langford (II)","author":".mau.","date":"2025-06-25","format":false,"excerpt":"Ancora sul problema di Langford","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":34334,"url":"https:\/\/xmau.com\/notiziole\/2025\/11\/12\/un-paio-di-dimostrazioni-non-standard\/","url_meta":{"origin":7733,"position":3},"title":"Un paio di dimostrazioni non standard","author":".mau.","date":"2025-11-12","format":false,"excerpt":"A volte ci si ingegna a trovare dimostrazioni matematiche \"inutili\", perch\u00e9 pi\u00f9 complicate, ma con un loro interesse.","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":7749,"url":"https:\/\/xmau.com\/notiziole\/2010\/03\/11\/fibonacci_e_lin\/","url_meta":{"origin":7733,"position":4},"title":"Fibonacci e l&#8217;induzione","author":".mau.","date":"2010-03-11","format":false,"excerpt":"un teorema sui numeri di Fibonacci dimostrabile con l'induzione","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":9423,"url":"https:\/\/xmau.com\/notiziole\/2013\/08\/04\/quizzino-goldbach-alla-rovescia\/","url_meta":{"origin":7733,"position":5},"title":"Quizzino della domenica: Goldbach alla rovescia","author":".mau.","date":"2013-08-04","format":false,"excerpt":"Uno dei problemi di teoria dei numeri pi\u00f9 elusivo \u00e8 il dimostrare la congettura di Goldbach: ogni numero pari maggiore di 2 \u00e8 esprimibile come somma di due numeri primi. Noi stavolta ci accontentiamo di qualcosa di meno: dimostrare che ogni numero dispari maggiore di 11 \u00e8 esprimibile come somma\u2026","rel":"","context":"In &quot;giochi&quot;","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7733","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=7733"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7733\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=7733"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=7733"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=7733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}