{"id":447,"date":"2011-12-12T12:04:54","date_gmt":"2011-12-12T11:04:54","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=447"},"modified":"2022-10-11T10:26:52","modified_gmt":"2022-10-11T08:26:52","slug":"arriva-godel","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2011\/12\/12\/arriva-godel\/","title":{"rendered":"Arriva G\u00f6del!"},"content":{"rendered":"

Riassunto della puntata precedente<\/a>: i matematici erano assolutamente convinti che fosse possibile trovare un sistema formale che permettesse di generare automaticamente tutte e sole le proposizioni vere. Inizialmente si pensava che il sistema formale fosse quello della geometria, come specificato da Euclide; poi la scoperta delle geometrie non euclidee ha fatto scegliere una linea di attacco diversa, che ha portato prima alla scelta dell’aritmetica e infine alla teoria degli insiemi. Russell ha fatto per\u00f2 notare come la definizione ingenua di insieme come “le cose che condividono una certa propriet\u00e0” portava ai paradossi, e cos\u00ec con Whitehead ha creato un sistema rigidamente compartimentato (i “tipi”) per impedire il problema alla base dei paradossi, cio\u00e8 l’autoreferenzialit\u00e0. A questo punto arriva il giovane Kurt G\u00f6del.<\/p>\n

Prima di continuare, per\u00f2, aggiungo ancora due parole sull’autoreferenzialit\u00e0 e su come i Principia Mathematica<\/i> l’avessero voluta tenere fuori: questo sar\u00e0 molto importante nel seguito. Russell e Whitehead hanno definito una gerarchia infinita di tipi<\/i>, affermando che gli insiemi di tipo 0 non possono contenere al loro interno altri insiemi ma solo elementi, quelli di tipo 1 possono contenere anche insiemi ma solo di tipo 0, quelli di tipo 2 solo insiemi di tipo 0 e 1, e via contando. Tra l’altro il concetto di “insieme di tutti gli insiemi” in questa teoria non esiste; si parla in questo caso di classe<\/i>, che \u00e8 un modo per dire “qualcosa che sembra un insieme ma non lo \u00e8, perch\u00e9 senn\u00f2 arrivano i paradossi”. Una prova ontologica in meno per l’esistenza di un Dio panteista…<\/p>\n

Nonostante tutto il lavoro che aveva fatto, il duo britannico non era ancora riuscito a dimostrare il suo punto fondamentale: che cio\u00e8 il linguaggio formale in cui erano scritti i Principia Mathematica<\/i> dava un sistema coerente (non si pu\u00f2 mai dedurre una formula falsa applicando le sue regole) e completo (una qualunque formula vera ha una sua deduzione dagli assiomi con una catena finita di inferenze logiche). Nel 1929 si ebbe un primo, parziale, risultato positivo: un giovane austriaco dimostr\u00f2 che il calcolo dei predicati del primo ordine era completo, e quindi in esso ogni formula logicamente corretta era dimostrabile in un tempo finito. <\/p>\n

Ma che cos’\u00e8 il calcolo dei predicati del primo ordine, mi chiederete? Semplice. Avete presente tutti i sillogismi tipo “se quando piove uso l’ombrello e adesso piove, allora adesso uso l’ombrello”? Bene, si parte da queste frasi, quindi con i connettori logici ∧ (in italiano “e”), ∨ (in italiano “o”, per la precisione “almeno una delle due possibilit\u00e0”), ¬ (in italiano “non”), ⇒ (in italiano “implica”); e ci si aggiungono i quantificatori<\/b>, che sono due: ∀, che significa “per ogni” e infatti gli americani l’hanno disegnato come una A (all) rovesciata, ed ∃, che significa “esiste un” ed \u00e8 stato disegnato come una E (exist) rovesciata. I quantificatori permettono di usare delle variabili<\/b>, che sono appunto elementi che possono essere scelti a piacere. Cos\u00ec una frase italiana come “ogni numero \u00e8 divisibile per 2” si traduce nella proposizione<\/b> ∀x<\/i> ∃y<\/i> (y<\/i> + y<\/i> = x<\/i>). Che la proposizione sia vera oppure falsa dipende naturalmente dal contesto in cui gli elementi si trovano (l’universo<\/b>): supponendo implicitamente che il simbolo “+” abbia il significato di somma (altrimenti la proposizione non sarebbe una codifica corretta…), se usiamo i numeri naturali essa \u00e8 falsa, mentre se usiamo i reali \u00e8 vera. Ma dal punto di vista della logica non \u00e8 cos\u00ec importante; ripeto che quello che dice il teorema di completezza<\/b> (il nome ufficiale) \u00e8 che se la formula \u00e8 logicamente corretta allora si poteva dimostrare che discende dalle regole sintattiche, lasciando da parte la semantica.<\/p>\n

Certo, non si era ancora al risultato vagheggiato da Hilbert, quello della sua frase \u00abWir m\u00fcssen wissen, wir werden wissen\u00bb (noi dobbiamo sapere, e noi sapremo): gi\u00e0 solo l’aritmetica non poteva essere formalizzata con la logica dei predicati del prim’ordine, perch\u00e9 per catturare l’induzione occorre avere un numero infinito di assiomi, o se preferite uno “schema di assiomi” dove quello che viene quantificato non \u00e8 necessariamente una singola variabile, ma pu\u00f2 essere un qualunque sottoinsieme degli elementi dell’universo. Insomma, il solito infinito che fa capolino. Ma era comunque un risultato promettente, e si poteva considerarlo un punto di partenza. Chi era il giovane dottorando che l’aveva dimostrato? Beh, Kurt G\u00f6del. Come avrete capito, G\u00f6del era uno che con la logica ci dava dentro bene, soprattutto considerando che aveva preso a studiarla seriamente da solo un anno… Ci vollero ben altri due anni prima di pubblicare il famoso articolo \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme, I<\/i>.<\/p>\n

Come ho scritto<\/a>, il progetto hilbertiano consisteva nel dimostrare – “metadimostrare”, oserei dire – come gli assiomi dell’aritmetica permettessero di dimostrare tutte le proposizioni vere… e naturalmente il viceversa, cio\u00e8 che non si potesse dimostrare una proposizione falsa: questa seconda possibilit\u00e0 sarebbe deleteria, perch\u00e9 da una singola proposizione falsa e dimostrabile si pu\u00f2 ricavare di tutto. Un aneddoto su Bertrand Russell racconta di come fu sfidato a dimostrare che lui fosse il papa, se 1 fosse stato uguale a 2. Russell subito rispose “io e il papa siamo due persone: ma se 1=2 allora siamo una persona sola e quindi io sono il papa!”. Credo che il buon vecchio Bertie si fosse inventato da solo la storiella per farsi pubblicit\u00e0, ma non importa. Insomma, il sacro Graal dei matematici era l’uguaglianza Vero = Dimostrabile; bastava ottenerla per l’aritmetica, perch\u00e9 le altre parti della matematica erano gi\u00e0 state riportate ad essa. Il Credo del Matematico, come spiega Douglas Hofstadter in Anelli nell’io<\/i>, recita insomma <\/p>\n

 X \u00e8 vero perch\u00e9<\/i> c’\u00e8 una dimostrazione di X;
\nX \u00e8 vero e quindi<\/i> c’\u00e8 una dimostrazione di X;<\/p><\/blockquote>\n

La prima frase corrisponde ad affermare la consistenza<\/b> dell’aritmetica, mentre la seconda ne deifinsce la completezza<\/b>.<\/p>\n

Come ha fatto G\u00f6del per infrangere questo sogno? Tradotto in linguaggio corrente, ha dimostrato come partendo da un sistema di assiomi A comprendente almeno quelli di base dell’aritmetica si poteva sempre costruire un’affermazione del tipo \u00abio non sono dimostrabile nel sistema di assiomi A\u00bb. La parola “io” si riferisce all’affermazione stessa, se la cosa non fosse sufficientemente chiara: ricorda un po’ il paradosso del mentitore, vero? Vediamo il significato – se lo si pu\u00f2 chiamare cos\u00ec – di questa affermazione. Se fosse dimostrabile, allora arriviamo immediatamente a un assurdo, perch\u00e9 sarebbe allo stesso tempo dimostrabile e non dimostrabile; se invece non lo fosse, allora sarebbe vera e quindi avremmo mostrato come non tutte le affermazioni vere sono dimostrabili. Insomma, ci manca qualcosa. Certo, potremmo pensare di aggiungere quell’affermazione alla lista iniziale degli assiomi e ottenere un nuovo sistema A’ pi\u00f9 ampio e sperabilmente completo: ma proprio come nel caso dell’argomento diagonale di Cantor la terribile trappola g\u00f6deliana scatterebbe ancora, e quindi si potrebbe costruire una nuova affermazione del tipo \u00abio non sono dimostrabile nel sistema di assiomi A’\u00bb. Inutile: non si scampa.<\/p>\n

Detta cos\u00ec in effetti \u00e8 un po’ troppo facile: G\u00f6del nel suo articolo spiega esattamente come si costruisce l’affermazione di cui sopra, ma il tutto diventa troppo tecnico per essere spiegato qua. Le idee alla base della dimostrazione per\u00f2 sono abbastanza semplici; nel prossimo post (l’ho gi\u00e0 pronto, solo che mi sono accorto che postarlo qui sotto era troppo, cos\u00ec ho diviso in due parti il testo) prover\u00f2 a scriverle sotto forma di ricetta, mischiando essenzialmente la descrizione hofstadteriana che trovate nel capitolo 10 di Anelli nell’io<\/em> e la voce di Wikipedia<\/a>, e aggiungendoci parecchio di mio perch\u00e9 senn\u00f2 non ci capivo nulla. Inutile dire che il buon Doug racconta il tutto in modo molto pi\u00f9 divertente e pieno di giochi di parole… anche nella traduzione italiana. Inutile anche dire che la voce di Wikipedia \u00e8 stata scritta da uno che non si rende conto che esiste qualcuno al mondo che non ha studiato logica: tutto torna, ma solo dopo aver battuto abbastanza forte la testa contro il muro… Spero insomma che il mio schema risulter\u00e0 un po’ pi\u00f9 comprensibile!<\/p>\n","protected":false},"excerpt":{"rendered":"

Cosa dice esattamente il teorema di G\u00f6del? E perch\u00e9 \u00e8 cos\u00ec importante?<\/p>\n","protected":false},"author":1,"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":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":[1],"tags":[44,24,29],"class_list":["post-447","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-logica","tag-paradossi","tag-storia-della-matematica"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-7d","jetpack-related-posts":[{"id":449,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/20\/il-primo-teorema-di-incompletezza-di-godel\/","url_meta":{"origin":447,"position":0},"title":"Il primo teorema di incompletezza di G\u00f6del","author":".mau.","date":"20\/12\/2011","format":false,"excerpt":"La dimostrazione del teorema di incompletezza di G\u00f6del non \u00e8 complicatissima, ma \u00e8 cos\u00ec autoreferenziale che a volte sembra di vedere Ritorno al futuro II. Ho provato a sminuzzarla e descriverla.","rel":"","context":"In \"logica\"","block_context":{"text":"logica","link":"https:\/\/xmau.com\/ilpost\/tag\/logica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":445,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/13\/prima-di-godel\/","url_meta":{"origin":447,"position":1},"title":"Prima di G\u00f6del…","author":".mau.","date":"13\/09\/2011","format":false,"excerpt":"I teoremi di incompletezza di G\u00f6del hanno segnato la fine della sicurezza che i matematici hanno avuto per 2500 anni. Cosa \u00e8 successo prima che arrivasse lui?","rel":"","context":"In \"logica\"","block_context":{"text":"logica","link":"https:\/\/xmau.com\/ilpost\/tag\/logica\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2648,"url":"https:\/\/xmau.com\/ilpost\/2013\/10\/26\/godel-dio-e-repubblica\/","url_meta":{"origin":447,"position":2},"title":"G\u00f6del, Dio e Repubblica","author":".mau.","date":"26\/10\/2013","format":false,"excerpt":"Stamattina mia moglie mi aveva detto di aver letto qualcosa oggi su Repubblica a riguardo di due ricercatori che avevano \"dimostrato il teorema di G\u00f6del\". Ammetto di non averci fatto troppo caso, non ero nemmeno troppo sveglio. Poi mi \u00e8 capitato di vedere su Facebook la condivisione di questo articolo\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2474,"url":"https:\/\/xmau.com\/ilpost\/2012\/02\/06\/parole-matematiche-monotono\/","url_meta":{"origin":447,"position":3},"title":"Parole matematiche: monotono","author":".mau.","date":"06\/02\/2012","format":false,"excerpt":"Quando si inventano parole dando loro una patina di classicit\u00e0, e gli accenti contano","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":580,"url":"https:\/\/xmau.com\/ilpost\/2015\/06\/19\/maturita-2015-luci-e-ombre\/","url_meta":{"origin":447,"position":4},"title":"Maturit\u00e0 2015, luci e ombre","author":".mau.","date":"19\/06\/2015","format":false,"excerpt":"Ottima l'idea di avere un esempio pratico, meno buona quella di un quesito \"facile\" troppo generico","rel":"","context":"In \"dematematizzazione\"","block_context":{"text":"dematematizzazione","link":"https:\/\/xmau.com\/ilpost\/tag\/dematematizzazione\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":199,"url":"https:\/\/xmau.com\/ilpost\/2012\/11\/26\/il-paradosso-di-braess\/","url_meta":{"origin":447,"position":5},"title":"Il paradosso di Braess","author":".mau.","date":"26\/11\/2012","format":false,"excerpt":"Aggiungere nuove connessioni a una rete in certi casi pu\u00f2 portare a peggiorare le sue prestazioni. Sembra incredibile, ma \u00e8 una conseguenza matematica dell'ipotesi che ognuno sia egoista.","rel":"","context":"In \"paradossi\"","block_context":{"text":"paradossi","link":"https:\/\/xmau.com\/ilpost\/tag\/paradossi\/"},"img":{"alt_text":"[il paradosso di Braess]","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=350%2C200 1x, https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2012\/11\/braess.png?resize=525%2C300 1.5x"},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/447","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=447"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/447\/revisions"}],"predecessor-version":[{"id":448,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/447\/revisions\/448"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=447"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=447"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=447"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}