Godel #3 - Aritmetizzazione della metamatematica

Il primo passaggio fondamentale per preparare la strada ai successivi ragionamenti è capire la codificazione aritmetica che Godel fa del mondo che vuole analizzare.
Questo primo gradino può sembrare solo un passaggio propedeutico ma costituisce a quanto posso capire un vero colpo di genio: Godel ha intenzione di dimostrare matematicamente cosa si può dimostrare o non dimostrare in matematica; fa il passaggio ad un livello superiore di analisi, non sta più facendo matematica ma metamatematica, un po' come quei personaggi pirandelliani che all'interno della commedia parlano della stessa commedia che stanno interpretando e fanno così "metateatro"; per fare questo passaggio ad un livello superiore Godel ha bisogno di creare un vero e proprio sistema, un edificio rigoroso e computabile. Vuole analizzare la matematica dei numeri naturali, e per farlo si avvale degli strumenti della stessa matematica dei naturali.
Visto che per parlare di matematica si usano dei simboli, la prima cosa di cui ha bisogno è tradurre in numeri questi simboli. E' necessario prendere le mosse da un sistema di rappresentazione dell'aritmetica estremamente rigoroso ma allo stesso tempo semplice e con pochi segni; questo è il calcolo proposizionale. Si tratta di un sistema di assiomi e regole di trasformazione in cui è possibile esprimere enunciati e dedurre le loro conseguenze logiche in modo del tutto formale e meccanico. Il calcolo proposizionale si basa su pochi simboli e regole ma è capace di esprimere tutti i concetti della matematica dei numeri naturali.
I simboli sono molto basilari e semplici e si suddividono in costanti e variabili.
Le costanti sono i simboli per scrivere i numeri e i segni necessari per mettere in relazione questi e le variabili ("~" che significa "non", "V" che sta per "oppure", "É" che signica "implica", o "se..., allora...", "." che significa "e", "$" che significa "esiste", "=" che sta per "è uguale a", e poi le parentesi tonde e altre poche cose). I numeri si scrivono con "0" per zero e con "S" dopo lo zero per ogni suo successore (quindi il numero 3 si scrive "SSS0", ossia il successore del successore del successore di zero). In questo modo si riducono moltissimo i simboli da tradurre e il lavoro di Godel è in parte più semplice. Poi ci sono le variabili, ossia simboli che possono rappresentare numeri, proposizioni o predicati. esistono le variabili numeriche (che rappresentano numeri, come SSS0), le variabili proposizionali (che rappresentano proposizioni tipo 0=0), le variabili predicative (che rappresentano predicati come "è maggiore di" o "è un numero primo"). Un esempio di formula o proposizione scritta con questo linguaggio potrebbe essere "($x)(x=S0)", che significa "esiste un x tale che x è il successore immediato di zero", quindi in pratica esiste il numero 1.
Le regole di trasformazione sono necessarie per passare dagli assiomi ad altre formule corrette e coerenti del sistema, quindi per fare tutti i "passaggi" delle dimostrazioni. Queste regole sono ad esempio la "regola di sostituzione" (è possibile sostituire delle formule alle variabili conservando la correttezza della proposizione) o la "regola di separazione" o "modus ponens" (che dice che se abbiamo X e X É Y, allora possiamo dedurre Y)

Quindi un teorema, ossia una dimostrazione all'interno del sistema, è qualsiasi passaggio che rispetta le regole interne del sistema e che quindi arriva a una formula partendo dagli assiomi di base e passando solo attraverso le regole di trasformazione correttamente applicate. Un po' come abbiamo imparato tutti a scuola, ed in modo completamente meccanico e tipografico (nel senso che i simboli possono essere anche del tutto scissi dal significato che rappresentano, e le regole sono solo dei meccanismi ciechi e astratti, applicabili in maniera automatica).
Godel come dicevo sopra ha bisogno di trasformare ogni simbolo in numero, ed è importante che lo faccia in modo che ad un munero corrisponda un simbolo e viceversa, e che ad una formula corrisponda un numero e viceversa, un rapporto biunivoco tra formule del sistema e numeri senza possibilità di errori o confusioni.
Potrebbe scegliere vari modi, ma opta per uno che a mio parere è elegantissimo. Parte dal facile e traduce le costanti con i primi numeri naturali:

Costante	Numero di Godel	Significato
~	1	non
V	2	oppure
É	3	implica
$	4	esiste
=	5	uguale
0	6	zero
S	7	immediato successore
(	8	aperta parentesi
)	9	chiusa parentesi
,	10	segno di separazione

Poi traduce le variabili numeriche con i numeri primi maggiori di 10.

Variabile numerica	Numero di Godel	Esempio
x	11	S0
y	13	SSSS0
z	17	0

Ovviamente altre variabili seguono come numerazione i numeri primi superiori a 17.

Alle variabili proposizionali attribuisce i numeri primi maggiori di 10 elevati al quadrato (scriverò 11^2 per intendere 11 elevato alla seconda, non conosco altri modi).

Variabile proposizionale	Numero di Godel	Esempio
t	11^2	0=0
r	13^2	($x)(x=S0)

Per le variabili predicative Godel sceglie i numeri primi maggiori di 10 elevati al cubo.

Variabile predicative	Numero di Godel	Esempio
A	11^3	numero primo
B	13^3	maggiore di

Con questo meccanismo la formuletta di prima ($x)(x=S0) diventa, sostituendo quanto nelle tabelle, 8, 4, 11, 9, 8, 11, 5, 7, 13, 9 (ho ricontrollato, è così). Questi però sono tanti numeri, è troppo complicato, pensa Godel. Quindi elabora un semplice modo per tirarne fuori uno solo: i primi numeri primi in ordine di grandezza elevati ai numeri trovati sopra e poi moltiplicati tra loro:2^8 x 3^4 x 5^11 x 7^9 x 11^8 x 13^11 x 17^5 x 19^7 x 23^13 x 29^9
Questo è il numero di Godel della formula. E' davvero grande ma, a parte la difficoltà di scriverlo per esteso, è perfettamente calcolabile con un algoritmo semplicissimo. Ai tempi di Godel il computer non esisteva nemmeno in teoria, Alan Turing solo pochi anni dopo teorizzò la sua macchina per calcolare, ma oggi il concetto di facile computabilità tramite un algoritmo è immediato da comprendere, ed è quindi ancora più apprezzabile la semplicità del metodo di Godel.Il concetto fondamentale è che esiste una corrispondenza biunivoca tra ogni formula e il suo numero di Godel, data un'espressione numerica esiste ed è semplicemente calcolabile il suo numero di Godel, e dato un numero di Godel è semplice trovare la formula a cui corrisponde.
E' chiaro che non tutti i numeri sono numeri di Godel, per essere tale il numero deve essere scomponibile in fattori primi che hanno un significato in base alle tabelle scritte sopra, altrimenti niente da fare.Esempio facile: prendiamo il numero 243.000.000 (duecentoquarantatre milioni). Come ogni altro numero (vedi il teorema fondamentale dell'aritmetica, affrontato anche in un altro post) ha una scomposizioni in fattori primi che è unica, e che in questo caso è 64 x 243 x 15625 = 2^6 x 3^5 x 5^6, ossia i primi tre numeri primi (2, 3, 5) elevati a 6, 5, 6, quindi controllando le tabelle sopra si ha che 243.000.000 è il numero di Godel dell'espressione "0=0". Non facilissimo ma semplicissimo.Un'altra cosa importante: consideriamo la dimostrazione di un teorema all'interno del calcolo proposizionale.
Ad esempio:
1)                             ($x)(x=Sy)
2)                             ($x)(x=S0)

ossia, dato che esiste un x tale che x è il successore immediato di y, se sostituiamo 0 a y (applicando la regola di sostituzione), ne consegue che esiste un x successore immediato di 0 (il famoso numero 1 di prima).
Supponiamo che il numero di Godel della prima parte sia A e supponiamo che il numero di Godel della seconda sia B; ebbene, il numero di Godel della intera dimostrazione è i primi numeri primi in ordine di grandezza elevati ai numeri di Godel delle singole espressioni e poi moltiplicati tra loro, ossia:
2^A x 3^B
questo è il numero di Godel dell'intera dimostrazione. E' enorme ma semplice da calcolare.
Ogni simbolo, ogni espressione numerica, ogni formula qualunque sia la sua complessità, ogni dimostrazione lunga quanto ti pare ha il suo specifico numero di Godel, e dato un qualsiasi numero di Godel è possibile con semplici passaggi algoritmici capire qual'è l'espressione matematica che rappresenta.
Questo metodo lo trovo fantastico.
E' il fulcro dell'intera dimostrazione, sul quale poi si basa l'intero ragionamento. Dal poco che ne so Kurt Godel è stato il primo ad ideare un meccanismo del genere, è questo che gli ha permesso il salto del livello interpretativo, dalla matematica alla metamatematica.
Io vado a nanna. Spero di non sognare numeri primi che vogliono godelizzarmi.
Alla prossima.

Comunicazione di servizio

Oggi Corsa di Miguel 2011, km 10,210, conclusa in base al mio cronometro in 44 minuti e 28 secondi, una media di 4 minuti e 21 secondi al kilometro, nuovo record personale sulla distanza. Soddisfatto.
Un breve resoconto delle passate edizioni (fino all'anno scorso lo davano per km 10,335, il percorso mi pare rimasto sempre uguale, quindi o era sbagliata la misurazione prima o lo è ora, o entrambe, ma poco importa).

2006: 51 e 26
2007: 50 e 21
2008: influenza
2009: 46 e 57
2010: 45 e 17
2011: 44 e 28

Eravamo parecchi, faceva freddino ma ci siamo tenuti stretti stretti per scaldarci.

Godel #2 - Contesto

Le discipline scientifiche si suddividono in due grosse famiglie. Quelle cosidette sperimentali hanno come obiettivo di spiegare la realtà, si basano sulle osservazioni e sulle sperimentazioni, ossia su test di coerenza con ciò che succede davvero. Hanno ragione di esistere solo quando spiegano il mondo che ci circonda in modo soddifìsfacente, si sorreggono esclusivamente sulle prove e quando incontrano una singola evidenza contraria sono pronte ad essere sovvertite dalle fondamenta; a queste appartengono la fisica, la biologia, la chimica, l'astronomia. Di queste mi fido.
Altre scienze sono invece di tipo deduttivo, ossia si basano su un sistema di assiomi definiti all'inizio che si ritengono veri o perlomeno rappresentativi di un sistema coerente e su questi assiomi poi, attraverso un complesso sistema di deduzioni e passaggi logici (le dimostrazioni), sviluppano teoremi, corollari, conclusioni generali. Nei casi estremi non c'è alcun bisogno che gli assioni rappresentino qualcosa di vero, e il mestiere dello scienziato è quello di essere coerente nelle dimostrazioni, non di dimostrare necessariamente la verità (come succede nel formalismo). Di questo gruppo fanno parte la geometria, la matematica, la logica, alcuni aspetti della filosofia e della metafisica. Di queste vediamo se ci si può fidare.

La regina delle discipline deduttive è la matematica. I vari rami della matematica si basano su una manciata di pochi assiomi e creano un mondo astratto e internamente coerente (anche se a volte, anzi spesso, si è visto coincidere con i più svariati aspetti del mondo reale. Ad esempio una cosa così strana e a prima vista inconsistente come la serie di Fibonacci si trova pari pari applicata nella crescita delle pigne, ma questa è un'altra storia...)
Nel seguito limiteremo la nostra attenzione, per semplicità, alla sola teoria dei numeri (la cosidetta aritmetica, ossia la matematica dell'insieme dei numeri interi, 0, 1, 2, 3, 4....) che ammette solo le operazioni di addizione (se sommiamo due numeri interi otteniamo sempre e solo un numero intero) e moltiplicazione (idem). Escludiamo la sottrazione (che porterebbe a volte come risultato dei numeri negativi, che orrore!) e la divisione (che avrebbe, udite udite, come risultato delle frazioni o numeri razionali, ma noi, per ora e per sempre, li aborriamo). Quindi ci limitiamo a roba da prima elementare.
All'inizio del ventesimo secolo si è cercato di rendere quanto più possibile blindato e coerente il mondo dei numeri interi, studiando un insieme di postulati o assiomi auto-evidenti e dai quali si potessero tirare fuori tutti i teoremi di aritmetica, dalla somma di due numeri al teorema di Fermat.
Il matematico italiano (esistono anche loro) Giuseppe Peano tentò la formalizzazione dell'aritmetica con la formulazione di cinque assiomi di base dai quali derivare tutta la teoria dei numeri naturali. E' carino saperli, anche perchè definiscono il minimo insieme (appunto l'insieme dei numeri naturali) per il quale è applicabile il teorema di incompletezza di Godel al quale prima o poi arriverò:

1. Esiste un numero naturale, 0 (zero)
2. Ogni numero naturale ha un numero naturale successore (nel seguito lo chiameremo S)
3. Numeri diversi hanno successori diversi
4. 0 non è il successore di alcun numero naturale
5. Ogni insieme di numeri naturali che contenga lo zero e il successore di ogni proprio elemento coincide con l'intero insieme dei numeri naturali (assioma dell'induzione)

Il matematico tedesco David Hilbert, il più forte dei suoi tempi, propose negli anni venti una sfida (il programma di Hilbert) con il quale richiedeva una dimostrazione di coerenza interna ai sistemi assiomatici come l'aritmetica di Peano (o come quella definita da Russel e Whitehead nei Principia Mathematica, un po' più complessa e di moda all'epoca ma più o meno dello stesso tipo). Coerenza interna significa che all'interno del sistema non dovevano esserci contraddizioni (non si doveva poter dimostrare che (0=0) e contemporaneamente ~(0=0), dove ~ è il simbolo di negazione).
E' qui che, dopo svariate righe di assenza, arriva il nostro caro Godel che, in un articolo del 1931 dimostrò non solo l'impossibilità della prova della coerenza interna in un sistema assiomatico, ma anche, e peggio, l'esistenza, all'interno di un sistema assiomatico come l'aritmetica, di una formula vera ma non dimostrabile nè confutabile con le regole del sistema stesso. Quest'ultima roba praticamente significa che in aritmetica esistono delle congetture vere che non potranno mai essere dimostrate.
E' qui che mi sono sempre chiesto: ok, mi fai un esempio? e l'esempio nelle varie cose che ho letto non me lo fanno mai, e io non essendo come Flaiano senza esempio non capisco. Ma poi ho scoperto che di esempi in teoria dei numeri ne esistono a bizzeffe; uno dei più citati è la mitica congettura di Goldbach, secondo la quale ogni numero pari maggiore di 2 può essere scritto come somma di due numeri primi (lo stesso numero primo può essere usato due volte). Sono oltre due secoli che le migliori menti cercano di dimostrarlo ma non ci riescono, eppure empiricamente la congettura regge ad ogni tipo di sperimentazione anche con i più potenti computer, che hanno calcolato che è valida perlomeno fino a 16 · 10¹⁷Questa potrebbe essere una formula di Godel, vera ma non dimostrabile nè confutabile.
Come primo post mi pare abbastanza, ora potere pure raccogliere da terra i coglioni e passare sul vostro sito porno preferito intanto che preparo il prossimo.

Godel #1 - Introduzione e dichiarazione d'intenti

In alcuni dei libri che mi sono passati tra le mani negli ultimi anni (Hofstadter, Penrose, Nagel e Newman, Hodges e forse altri che non mi sovvengono) si fanno accenni più o meno approfonditi ai teoremi di incompletezza di Godel. Pare che siano uno degli apici logici raggiunti dall'uomo, al pari della teoria della relatività in fisica o delle composizioni di Mozart in musica, uno dei punti di arrivo delle capacità di pensiero astratto, qualcosa dalla quale, una volta concepita, non si può prescindere.
Dicevo che ho letto parecchie descrizioni del processo di dimostrazione, anche molto diverse tra loro, e varie disquisizioni sul significato dei teoremi, ma devo confessare di non averci ancora capito quasi una mazza. O meglio, alcuni passaggi mi sono chiari, capisco più o meno dove si vuole andare a parare e più o meno il significato implicito nelle conclusioni, ma mi manca assolutamente la visione d'insieme del processo logico.
Eppure i libri di cui parlavo sono assolutamente divulgativi, comprensibili senza avere conoscenze avanzate di logica o matematica (almeno così dicono), privi di passaggi tecnici che non siano elementari, ma io confermo di non averci capito quasi una mazza.
Però voglio continuare ad evolvermi e migliorare (non è questo il segreto della vita?). Quindi ho deciso di utilizzare questo blog per ripercorrere i passaggi del processo di dimostrazione e fissarmeli in mente, chissà che scrivendoli non li comprenda meglio. Già vedo l'espressione degli occhi di chi mi legge: già le labbra si increspano e si allargano in un sonoro "e sti cazzi..."... beh, questo è il mio blog, chi non lo vuole leggere può benissimo andare su morcatana, dagospia o le previsioni del meteo, qui si parlerà di Godel. E scusate se è poco.
Ovviamente, vista l'osticità dell'argomento, mi prenderò alcune libertà. Di seguito i miei diritti:
- tra il post  #1 e il #2 (e i #successivi) possono passare anche mesi senza che questo significhi che abbia abbandonato il mio intento: sto semplicemente meditando,
- nel frattempo posso scrivere altri post che parlano di cucina, di scacchi o di problemi al colon e dimenticarmi di Godel per tutto il tempo che desidero,
- posso scopiazzare da varie parti, dai libri che ho citato, da wikipedia, da qualunque altra fonte io trovi, senza il bisogno di dichiararlo,
- posso spezzettare i passaggi nei post come mi pare e interromperli dove voglio per riprenderli in seguito, o non riprenderli per niente
- posso modificare i post anche dopo averli pubblicati se mi accorgo non sono chiari (a me innanzitutto) o che prima vanno affrontati altri passaggi.
Come unico dovere mi impegno a scrivere solo cose che ho capito (quindi tutto potrebbe concludersi con il #1).
Ok, l'accordo mi pare onesto, e lo accetto (...mi sento come un tipo che firmò un contratto con gli italiani senza la controfirma da parte degli italiani...).
Alla prossima. Siate fiduciosi.

Espertoni

La suddivisione dei compiti nel corso della storia dell'uomo ha arrecato innegabili vantaggi: mi riferisco soprattutto alla possibilità per una piccola minoranza di avere parecchio tempo libero a disposizione senza l'obbligo da mane a sera di procurarsi con il sudore della fronte cibo, protezione e sesso. Far parte di questo esiguo gruppetto è stato ed è tuttora sicuramente piacevole: contadini, soldati e bottane che pensano a te e finalmente hai tutto il tempo che ti occorre per dedicarti alla speculazione, alle domande sulle ragioni delle cose, ai primi passi del pensiero astratto. Grosso passo avanti per la mente.
Purtroppo accanto a questi innegabili vantaggi l'estrema specializzazione negli ultimi secoli ha portato anche a quella che ritengo una rovina per l'uomo, a un deciso passo indietro per la mente: la comparsa dell'autorità in materia, dell'esperto di settore, dello specialista.
Un buon settanta per cento dei cosiddetti esperti non serve a molto di più che a soddisfare il nostro bisogno di fare affidamento su un'autorità qualsivoglia. E l'espertone prolifera lucrando alle nostre spalle.
Se solo uno cercasse di capire un po' meglio il proprio problema prima di affidarlo allo specialista di turno riuscirebbe nella maggior parte dei casi a risolverlo senza alcun aiuto.
Basta un semplice mal di gola per andare da un medico che dovrebbe capirne più di te del tuo corpo quando sarebbe sufficiente, soprattutto con gli strumenti di informazione oggi disponibili, cercare di interpretare i sintomi o aspettare qualche giorno per una guarigione naturale.
Basta una spia che si accende sul cruscotto dell'auto per correre dal meccanico, quando basterebbe una veloce lettura del manuale di manutenzione per risolvere il problema.
Per non parlare di quelli che pretendono di essere gli esperti dell'anima e della mente, ai quali affidiamo tutto ciò che riteniamo più importante in questa vita senza alcun problema.
Che poi questi maghi della specializzazione, questi "so tutto riguardo a poco e poco riguardo al resto", se visti da vicino nella maggior parte dei casi si rivelano semplici omini della porta accanto in tutto quello che non riguarda da vicino la propria professione.
Ci sono manager che hanno un intuito formibabile per tutto ciò che è legato al loro campo, sono dei gestori nati, sembra non gli sfugga niente del mondo che circonda il loro ufficio ma poi appena fuori dal proprio regno non sanno distinguere una cassata da una pastiera, un barolo da un vermentino, un van gogh da un picasso, un dromedario da un cammello.
Ci sono medici rinomati e rispettati dalle cui labbra pendono le sorti di decine di sventurati ma che in privato si rivelano essere semplici impiegati della medicina, che non fanno altro che applicare vecchie procedure più o meno a casaccio, sperando vada tutto bene e soprattutto che nessuno rompa i coglioni di domenica.
Non mi fiderei mai di una persona del genere. Meglio fare da solo.
Ma il popolo continua ad averne estremo bisogno, toglile il luminare e la casalinga è perduta, se incontra un cuoco di professione è persino disposta a dire che l'amatriciana che fino ad ora era stata l'orgoglio del condominio è in fin dei conti una schifezza, ma come ha fatto a non accorgersene sino ad ora e a rifilarla a figli e marito ignari.
Ma ora basta. Ribelliamoci agli specialisti, ai laureati in metodologia e funzionamento del cacciavite a croce, alle autorità del particolare, riprendiamoci la nostra mediocrità omogeneamente spalmata su più o meno tutto lo scibile e facciamone la nostra bandiera. Forse correremo qualche rischio in più ma sicuramente prenderemo le dicisioni che ci riguardano con più consapevolezza.

Buoni propositi

Da qualche tempo alcune delle persone che mi conoscono sostengono che mi sto sempre più trasformando in un orso burbero e solitario, che rifugge la compagnia e le novità, che non vuole mai uscire, conoscere gente nuova, divertirsi e viaggiare, partecipare ad una festa o, orrore degli orrori, essere festeggiato.
Analizziamo la questione. Innanzitutto ho figli piccoli e un lavoro full time. E già questo basterebbe a limitare di parecchio le mie velleità di presenzialista nella movida romana. Poi va considerato che di tempo ne ho perso anche parecchio, dai tempi del liceo ed oltre, con comitive da cui mi sarei volentieri tirato fuori, con coetanei che non stimavo, con parenti di cui mi fregava davvero poco. E cosa ne ho guadagnato? Ricordi piacevoli pochi, qualche modo di dire che tuttora rifuggo, una rete di relazioni ormai sgretolata e nessuna voglia di ricostruirla.
Sono sempre più convinto che il tempo libero è troppo prezioso per sprecarlo parlando di coglionate con chiunque, quindi ho deciso di selezionare minuziosamente chi avrà la sventura di ascoltare le mie.
Meglio orso che assomigliare ad uno che non frequenterei.