{"id":444,"date":"2014-10-31T16:15:47","date_gmt":"2014-10-31T15:15:47","guid":{"rendered":"http:\/\/xmau.com\/wp\/ilpost\/?p=444"},"modified":"2022-10-11T13:52:26","modified_gmt":"2022-10-11T11:52:26","slug":"aritmetica-di-robinson","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2014\/10\/31\/aritmetica-di-robinson\/","title":{"rendered":"Aritmetica di Robinson"},"content":{"rendered":"

Qui sul Post ho gi\u00e0 raccontato dei teoremi di incompletezza di G\u00f6del<\/a>, e ho persino postato una dimostrazione<\/a>. (Non preoccupatevi se non ve la ricordate: riesco a seguirla, ma nemmeno io mi ricordo mai come funziona). Un punto fondamentale del teorema \u00e8 che possiamo costruire delle proposizioni indecidibili se abbiamo un sistema formale con cui \u00e8 possibile fare dell’aritmetica. Dopo la bomba iniziale g\u00f6deliana, i matematici hanno iniziato come di loro abitudine a vedere se era proprio necessario tutto l’armamentario dell’aritmetica o si poteva evitare qualcosa. Che ne \u00e8 uscito? <\/p>\n

Beh, si \u00e8 scoperto che non serve proprio tutta l’aritmetica di base, e si pu\u00f2 togliere qualcosina, anche se non molto. L’aritmetica pu\u00f2 essere definita con gli assiomi di Peano: non so se ve ne ricordate, per\u00f2 ho gi\u00e0 parlato anche di essi<\/a>. Negli assiomi di Peano abbiamo che esiste un numero che si chiama 0 e una funzione S (“successore”) che crea nuovi numeri a partire da quelli gi\u00e0 esistenti; sappiamo inoltre che numeri diversi hanno successori diversi e che 0 non \u00e8 il successore di nessun altro numero. Infine c’\u00e8 la parte pi\u00f9 rognosa, quella dell’induzione matematica: se un sottoinsieme dei naturali contiene 0 e il successore di ciascun numero contenuto nell’insieme, allora contiene tutti i numeri naturali. Da qui si prosegue definendo la somma e il prodotto (per ricorsione, cio\u00e8 usando somme e prodotti con numeri “pi\u00f9 piccoli”)<\/p>\n

Raphael Robinson (che mi hanno fatto notare che non \u00e8 quello dell’analisi non standard che ha creato gli infinitesimi) ci pens\u00f2 un po’ su e nel 1950 scopr\u00ec che l’induzione matematica non \u00e8 necessaria per finire sotto le grinfie dei teoremi di G\u00f6del, ma ci si pu\u00f2 accontentare di qualcosa di meno. Defin\u00ec cos\u00ec quella che ora chiamiamo Aritmetica di Robinson<\/b> e denotiamo di solito con Q<\/b>. In formule abbiamo questi assiomi (pi\u00f9 tutta una serie di assiomi per cos\u00ec dire “di base”, come dire che esiste un simbolo 0 e cos\u00ec via):<\/p>\n

Q1: ∀ x<\/i> (S(x<\/i>) ≠ 0)
\nQ2: ∀ x<\/i> ∀ y<\/i> (S(x<\/i>) = S(y<\/i>)) → (x<\/i> = y<\/i>))
\nQ3: ∀ x<\/i> ((x<\/i> ≠ 0) → (∃ y<\/i> (x<\/i> = S(y<\/i>))))
\nQ4: ∀ x<\/i> (x<\/i>+0 = x<\/i>)
\nQ5: ∀ x<\/i> ∀ y<\/i> (x<\/i>+S(y<\/i>) = S(x<\/i>+y<\/i>))
\nQ6: ∀ x<\/i> (x<\/i>*0 = 0)
\nQ7: ∀ x<\/i> ∀ y<\/i> (x<\/i>*S(y<\/i>) = (x<\/i>*y<\/i>)+x<\/i>))<\/p><\/blockquote>\n

L’unica piccola differenza con l’aritmetica di Peano \u00e8 che lo schema di assiomi che definisce l’induzione \u00e8 sostituito dall’assioma Q3, che afferma che ciascun numero diverso da zero \u00e8 successore di un altro numero, affermazione che con gli assiomi di Peano \u00e8 un teorema (partendo da zero otteniamo con l’induzione tutti i numeri…) Questa minima differenza ha per\u00f2 grandi effetti: per dire, un’affermazione a prima vista banale come il dire che nessun numero \u00e8 successore di s\u00e9 stesso un’asserzione indecidibile nel sistema Q<\/b>. Come mostrarlo? Semplice: inventandoci un modello apposito di Q<\/b>! Ora lo spiego con qualche parola in pi\u00f9, non preoccupatevi…<\/p>\n

Per prima cosa, ricordo che gli assiomi non hanno nulla a che fare con la realt\u00e0. Quello che succede \u00e8 che abbiamo tra le nostre mani qualcosa, per esempio i numeri naturali con le regole dell’aritmetica, e verifichiamo che essi rispettino le regole formali date dagli assiomi: in questo caso possiamo dire che quello che abbiamo tra le mani \u00e8 un modello di quella teoria assiomatica. Detto in altro modo, i numeri naturali con le regole dell’aritmetica sono un modello per mettere in pratica sia gli assiomi di Peano che gli assiomi di Robinson; chiamiamo quel modello “standard” perch\u00e9 ce l’abbiamo sempre tra i piedi. Ma esistono anche altri modelli, proprio come in geometria si pu\u00f2 dare un significato diverso a punti, rette e piani e trovare un modello per cui non valga il quinto postulato di Euclide. <\/p>\n

Prendiamo ora i numeri naturali pi\u00f9 un “nuovo numero” Ω. I numeri naturali hanno le solite regole per somma e prodotto tra di loro; per quanto riguarda Ω abbiamo che S(Ω<\/i>)=Ω<\/i>, che n<\/i>+Ω = Ω+n<\/i> = Ω per ogni n<\/i>, e n<\/i>*Ω = Ω*n<\/i> = Ω per ogni n<\/i> diverso da 0, altrimenti il prodotto \u00e8 0. Potete vedere facilmente che gli assiomi da Q1 a Q7 sono soddisfatti: abbiamo insomma costruito un modello che sta in piedi per l’aritmetica di Robinson. Per\u00f2 l’affermazione “nessun numero \u00e8 successore di s\u00e9 stesso” \u00e8 evidentemente falsa, visto che il successore di Ω \u00e8 Ω stesso. D’altra parte con i numeri naturali (che – ribadisco – sono un altro modello di aritmetica di Robinson) quell’affermazione \u00e8 vera; pertanto nell’aritmetica di Robinson quell’affermazione \u00e8 indecidibile. Ma c’\u00e8 di peggio! Tra le affermazioni indecidibili ci sono “banalit\u00e0” tipo la associativit\u00e0 e commutatitiv\u00e0 dell’addizione e distributivit\u00e0 della moltiplicazione rispetto all’addizione. Insomma, con l’aritmetica di Robinson, a parte questi scherzetti, si pu\u00f2 fare ben poco.<\/p>\n

Morale di tutto questo? Ce ne sono almeno due. La prima \u00e8 che abbiamo una dimostrazione molto semplice del primo teorema di incompletezza di G\u00f6del: e dite niente! La seconda \u00e8 invece un po’ pi\u00f9 sottile, e ne ho gi\u00e0 accennato qui sopra. Noi usiamo tranquillamente i numeri naturali, e siamo intimamente convinti che non possano essere che cos\u00ec: non sono forse “naturali”? Invece non \u00e8 proprio cos\u00ec, come abbiamo visto. Per meglio dire, i numeri naturali sono s\u00ec naturali, ma bisogna essere molto attenti a come li si definisce, cio\u00e8 a definire il modello sottostante. Peggio ancora, il modello dei numeri naturali sembra proprio richiedere necessariamente l’infinito preso tutto assieme<\/b>; Robinson ha provato a mettere un infinito potenziale dove i numeri sono s\u00ec infiniti, ma li controlliamo a uno a uno, e il risultato \u00e8 stato questo qua. (Intendiamoci: dal suo punto di vista quello \u00e8 stato un risultato positivo!). Lo so, io di solito dico che la matematica \u00e8 facile: sono convinto che si possa facilmente fare tanta matematica, ma quello che sta dietro pu\u00f2 essere davvero complicato… come del resto tutti gli altri campi del sapere.<\/p>\n","protected":false},"excerpt":{"rendered":"

I teoremi di G\u00f6del vi sembrano troppo complicati? Eccovi un modo molto semplice per trovare una proposizione indecidibile secondo certe regole aritmetiche.<\/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":[95,94],"class_list":["post-444","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-assiomi","tag-logica-matematica"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-7a","jetpack-related-posts":[{"id":449,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/20\/il-primo-teorema-di-incompletezza-di-godel\/","url_meta":{"origin":444,"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":447,"url":"https:\/\/xmau.com\/ilpost\/2011\/12\/12\/arriva-godel\/","url_meta":{"origin":444,"position":1},"title":"Arriva G\u00f6del!","author":".mau.","date":"12\/12\/2011","format":false,"excerpt":"Cosa dice esattamente il teorema di G\u00f6del? E perch\u00e9 \u00e8 cos\u00ec importante?","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":444,"position":2},"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":2640,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/25\/matematica-e-liberta\/","url_meta":{"origin":444,"position":3},"title":"Matematica e libert\u00e0","author":".mau.","date":"25\/09\/2013","format":false,"excerpt":"Non ho certo le capacit\u00e0 di interloquire con il papa emerito sui temi teologici, ma forse su quelli pi\u00f9 prettamente matematici qualcosa posso dire.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"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":444,"position":4},"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":2584,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/03\/euclide-aritmetico\/","url_meta":{"origin":444,"position":5},"title":"Euclide aritmetico","author":".mau.","date":"03\/04\/2013","format":false,"excerpt":"Gli Elementi non parlano solo di geometria, ma anche di aritmetica; e anche qua brilla l'esposizione di Euclide.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.ilpost.it\/wp-content\/uploads\/bloggers\/2013\/04\/Euclids_algorithm_Book_VII_Proposition_2_3.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/444","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=444"}],"version-history":[{"count":6,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/444\/revisions"}],"predecessor-version":[{"id":457,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/444\/revisions\/457"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=444"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=444"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=444"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}