Gottinga e l'infinito

L'Università di Göttingen, in Germania

Mettetevi comodi e leggete questo fumetto di Davide Osenda. Si parla di Cantor e degli infiniti, del vecchio Kurt Gödel e del nazismo, e c'è persino l'esempio del grammofono tratto dal capolavoro di Douglas Hofstadter, Gödel Escher e Bach.
L'ho scovato grazie all'Archivio David Foster Wallace Italia (trovate il link qui a lato): pare che il nostro nuovo amico DFW fosse particolarmente sensibile a questi argomenti, visto che ci ha pubblicato anche un saggio.
Ora mi torna tutto.

Infinite density

I sensi si allenano, e ognuno di essi ha la sua palestra. Viaggiare in metropolitana ha acuito la mia percezione visiva dei volti e delle fisionomie. Una volta arrivato in banchina riesco con una sola occhiata panoramica a scandagliare tutti i visi che sono ad una ragionevole distanza e che non sono coperti da ostacoli e a captarne il grado di pericolosità. Intendo come pericolosità non il rischio che possano rivelarsi borseggiatori, stupratori o terroristi internazionali, ma che possano essere dei rompicoglioni. E' questo il genere di persone da evitare come la peste se, come il sottoscritto, hai intenzione di sfruttare al massimo il tempo di viaggio casa-ufficio ufficio-casa, un’ora netta in totale, per leggere il tuo libro. E se il libro in questione è Infinite Jest, di David Foster Wallace, il lavoro preparatorio deve essere svolto alla perfezione. In banchina sono come una specie di Terminator con la visione monocromatica rossa su sfondo nero, di ogni volto passo in esame i valori cefalometrici, li confronto con il database dei miei ricordi e sintetizzo il tutto in un fattore di rischio, dieci per il massimo, in caso di collega con il quale proprio in quella settimana sto intrattenendo intensi rapporti lavorativi (per cui sarebbe difficile non sprecare tutto il viaggio in vuote considerazioni di circostanza), zero per il minimo, in caso perfetti sconosciuti, passando per i vari gradi medi dei conoscenti da salutare con un cenno, del colleghi di qualche anno addietro da liquidare con brevi convenevoli, o dei suonatori underground, rischiosi solo in quanto rompitimpani.
Una volta che la scansione è terminata, se il risultato è a basso rischio, è possibile posizionarsi in uno degli estremi della banchina, quelli che di solito sono spopolati a causa del diffuso timore che i vagoni o non arrivino fin lì (estremo di prua) o che oltrepassino quel punto (estremo di poppa), tirar fuori il quasi chilo di carta rilegata con copertina violacea, bilanciare i pesi e attaccare.
La mia scelta di scrivere di IJ mentre lo leggo è dovuto ad alcuni innegabili vantaggi. Posso commentare a caldo le sensazioni, le difficoltà, i punti salienti, le idee che vengono dalla lettura, senza posticiparle a quando poi non avrebbero più senso, almeno per me. E posso utilizzare il blog come blocco degli appunti. Lo svantaggio, di contro, è che si rischia di dire parecchie cazzate. Ma di questo non ci siamo mai preoccupati troppo, in queste pagine.

Andando avanti con la lettura mi accorgo che la gara di velocità a chi finisce per primo IJ ipotizzata qualche giorno fa con alcuni lettori di questo blog nei commenti al post precedente, è per me improponibile. E non perché siano sopraggiunti momenti di crisi dovuti alla difficoltà dei periodi, al poco interesse dei personaggi o alle mille distrazioni esterne. Tutt'altro. E' che il librone oltre ad essere bello grosso è talmente denso da richiedere ampi momenti dedicati a rilettura e riflessione, e un’ansia da competizione non sarebbe d’aiuto.

Mi è ad esempio capitato di soffermarmi un'intera giornata leggifera tra pagina novantaquattro e pagina cento, nel bel mezzo di un capitolo APAD. In questo paragrafone di sette pagine, che a sua volta costituisce la seconda parte di un capitolo la cui prima è il meraviglioso racconto delle crisi di astinenza da Bob Hope di Kate Gompert, compare per la prima volta Gerhard Schitt, una sorta di Grunf del gruppo TNT, non so se avete presente, con occhialoni, casco di cuoio e motocicletta BMW con il sidecar, che qui all'ETA fa l’Allenatore Capo e il Direttore Atletico. Le sue chiacchierate peripatetiche con Mario Incandenza, che a malapena riesce a capirne le parole, figuriamoci i concetti, ma chissà come riesce a rispondere sempre a tono e a porre domande pertinenti, è fenomenale. Basterebbero questi scambi a rendere le pagine degne di essere trasportate, insieme al resto dei nove etti, in giro per Roma. Ma c'è pure il contenuto, la storia della Dinamica Extra-Lineare accennata dalla nota trentaquattro e il superamento della matematica del Caos con dimostrazioni di inesistenza post Godeliane, l’assonanza tra Kant e Cantor, e poi lo Zen e gli scacchi, e il tennis come gioco infinitamente denso. E alla fine, su tutto, c'è questa domandona formulata da Mario che non si capisce come sia venuta fuori, come sia riuscito lui a condensare l’intero capitolo in una semplice ma azzeccata questione, e più o meno chiede, Ma allora il fine della vita è la morte? E che differenza ci sarebbe tra l'una e l'altra? e la risposta del crucco: Nessuna. Tranne che hai l'opportunità di giocare.
C’è poco da correre, sono pagine dense. Come il tennis. Come le ragnatele di Vedova Nera Usa.

Una nota, forse banale, sullo stile: gli eterogenei capitoli di IJ hanno una caratteristica in comune: all’inizio sono poco ospitali, è ostico cominciarli, e poi, quando stai cominciando a entrarci dentro, a comprenderli, finiscono. La festa finisce quando cominci a divertirti. Come a dire: avete capito i meccanismi? Vi piace? Beh, arrivederci. Immagino sia l’unico modo che DFW ha scovato per parlare di così tante cose per così tante pagine senza rischiare l’abbandono.

Come commiato vi lascio due chicche:

La ricostruzione dell’Enfield Tennis Academy nel disegno qui in basso, e questa succosissima e dettagliata visione panoramica (è anche possibile scaricare il lenzuolone in pdf) delle interrelazioni tra i personaggi di IJ, con alcune mappe e la struttura degli anni di cui abbiamo già accennato nel post precedente. Devo dire che ad oggi non sento ancora il bisogno impellente di consultarla come riferimento, ma probabilmente sono troppo indietro per apprezzarla appieno. Ieri ci ho navigato un po’, mi pare ben fatta. Immagino comunque che per capire a fondo tutte le implicazioni a cui queste interrelazioni accennano non basta uno schema, per quanto dettagliato sia. Ho come il sospetto che per dire tutto servirebbero milleduecentottantuno pagine fitte fitte, né una in più, né una in meno.

Godel #6 - Un raffinato mentitore

Ripassato il paradosso del mentitore? No? Cinque meno meno e prurito ai genitali vi colga. Ve lo rispolvero io. La prima versione si dice risalga ad Epimenide, il cretese che diceva che tutti i cretesi mentono. Una versione moderna e semplificata al massimo potrebbe essere un tizio che dice: "sto mentendo". Ebbene, il paradosso sta nel fatto che se dice la verità significa che sta mentendo, se sta mentendo dice la verità.
Con la formula G di Godel succede più o meno lo stesso. La G dice "non sono dimostrabile". Se quindi G fosse dimostrabile, allora la negazione di G sarebbe dimostrabile e direbbe "non è vero che non sono dimostrabile" e quindi sarebbe negata la G. Se invece la negazione di G fosse dimostrabile, allora G sarebbe dimostrabile, e direbbe "non sono dimostrabile". Se G allora ~G, se ~G allora G.
Quindi su G non si può dire nulla, nè che è dimostrabile nè che è dimostrabile la sua negazione. La proposizione G di Godel è indecidibile.
Solita regola per ottenere l'eureka: rileggere con calma.

Certo che se la questione si fermasse qui la dimostrazione di Godel con la quale ho ammorbato la mia ormai sconfinata platea per giorni sarebbe un po' deludente... Solo una nuova versione del paradosso del mentitore, non ce lo potevi dire prima? Ci saremmo risparmiati vari ematomi alle gonadi e avremmo avuto più tempo per scaccolarci.
Ma qui c'è qualcosa in più rispetto al classico paradosso del mentitore. La G di Godel è una proposizione vera.
È un teorema matematico vero che non può essere nè dimostrato nè negato con gli assiomi della matematica. Una verità indecidibile.I tre passaggi che dimostrano che la G è vera sono in fin dei conti semplici:
- la proposizione metamatematica "la formula G non è dimostrabile" abbiamo dimostrato che è vera (la abbiamo costruita proprio così)
- la proposizione G è rappresentata dalla stessa G, esattamente come la frase di Quine: G dice proprio questo: "la formula G non è dimostrabile" - ad una proposizione metamatematica vera corrisponde una formula matematica vera.
Questo ultimo punto lo abbiamo presupposto (ormai parlo al plurale come il papa, fermatemi) sin dall'inizio: la metamatematica di Godel e la sua numerazione non sono altro che una simbolizzazione della matematica, non abbiamo fatto altro che abbinare una numerazione alle espressioni matematiche che abbiamo costruito man mano, e abbiamo costruito sempre delle proposizioni vere.
Siamo partiti dicendo  ~Dim(x,z)  ossia abbiamo scritto un qualcosa non dimostrabile, ne esistono a bizzeffe di proposizioni non dimostrabili, che so,  ~($x)(Sx=0)  che sarebbe "non esiste un numero naturale minore di zero", e lo stesso è stato per tutti i passaggi seguenti, tipo  Sost(M, 13, M), che è solo un modo per definire un numero: ripercorrete tutto passo per passo e non troverete nulla che non sia semplicemente un modo diverso di scrivere delle cose vere.
Non abbiamo fatto altro che esprimere teoremi matematici veri, corretti. La numerazione di Godel è stata solo una simbolizzazione di questa matematica vera, quindi è anche essa vera. Abbiamo sempre sostenuto (o comunque se non l'abbiamo fatto lo facciamo ora) che la simbolizzazione della matematica nulla cambia del suo significato intrinseco, se è vero il concetto simboleggiato è vera anche la sua versione trasformata mediante numerazione di Godel.
Questa è la grande innovazione rispetto ad un semplice paradosso logico.Non si tratta solo di una frase indecidibile, ma di una frase indecidibile e vera.

Ricapitolando.
Abbiamo dimostrato che con gli assiomi della matematica è sempre possibile costruire una proposizione indecidibile all'interno della struttura assiomatica ma vera.
Questo significa che la matematica non riuscirà mai a dimostrare alcune particolari verità, quindi che la matematica è incompleta.
Non servirebbe a nulla ampliare gli assiomi per includere anche la G, perchè a questo punto con tali assiomi si potrebbe comunque con lo stesso meccanismo presentato costruire una G(1) che è vera ma indecidibile all'interno del nuovo sistema.

Come abbiamo fatto allora a dimostrare la verità della G se non con la matematica? La particolarità è che la verità della frase non è stabilita con strumenti matematici, con un sistema assiomatico che anzi viene fatto fallire, ma tramite un approccio metamatematico.
E' per questo che alcuni hanno portato ad esempio il teorema di incompletezza per asserire la superiorità dell'intelligenza umana rispetto ai meccanismi automatici della matematica assiomatica e per negare la possibilita dell'intelligenza artificiale. Dicono: se l'uomo riesce a costruire una G vera non utilizzando gli assiomi (i meccanismi base di qualsiasi funzionamento meccanizzabile) ma trascendendo da essi, allora la mente umana è qualcosa di più rispetto a semplici meccanismi automatici.
Io non sono d'accordo, ma questa è una storia che forse approfondiremo in seguito.Notte.

PS: a proposito di frasi ricorsive ho trovato questa cosa di Emo Philips: "Non sono un fatalista; ma anche se lo fossi, che cosa potrei farci?".
Non capisco se è la frase ad essere ricorsiva (ma no, non lo è) o il comportamento che c'è descritto, voi forse potete aiutarmi. O forse non c'entra proprio niente, ma mi piaceva citarla.

Rinotte.

Godel #5.3 - terzo passaggio con aritmoquinazione

Passaggio difficilino perchè si intrecciano le cose dette nei primi due passaggi, quindi come prima cosa ci occorre un breve ripasso.

Primo passaggio:  (x)~Dim(x,z)    significa che “per ogni x, non si verifica mai che la sequenza di formule con numero di Godel x è una dimostrazione della formula con numero di Godel z” o, più semplicemente, "z non è dimostrabile".

Secondo passaggio:  Sost(M, 13, M)    rappresenta "il numero di Godel della formula che si ottiene dalla formula con numero di Godel M sostituendo alla variabile con numero di Godel 13 il numero M".
Nota per PdB: si tratta di ciò che Hofstadter nel suo GEB chiama aritmoquinazione, ossia il sostituire ad una variabile di un enunciato l'enunciato stesso, come nel paradosso di Quine ("produce una falsità se preceduto dalla propria citazione" produce una falsità se preceduto dalla propria citazione).

Possiamo scrivere ora un caso particolare della formula del primo passaggio

A:       (x)~Dim(x,Sost(y,13,y))

che significa "la formula con numero di Godel Sost(y,13,y) non è dimostrabile”.
Questa nuova formula, essendo una formula aritmetica come tutte le altre, ha un suo numero di Godel, che chiamiamo J. Se sostituiamo alla variabile y il numero J, si ottiene la particolare formula ricercata da Godel:

G:       (x)~Dim(x,Sost(J,13,J))

Anche la G ha un suo numero di Godel, il caso particolare è che è proprio Sost(J,13,J) che è contenuto in essa.
Infatti come abbiamo detto nel secondo passaggio Sost(J,13,J) non è altro che il numero di Godel della formula che si ottiene dalla formula con numero di Godel J sostituendo alla variabile con numero di Godel 13 (ossia a y) il numero J. Ma G è stata ottenuta proprio così, ossia sostituendo alla variabile y di A il numero di Godel di A, ossia J.
Dato che G significa “la formula con numero di Godel Sost(J,13,J) non è dimostrabile”, e siccome il numero di Godel di G è proprio Sost(J,13,J), di conseguenza G dice: “Io non sono dimostrabile”.
(Anche in questo caso si consiglia di leggere quanto sopra molto lentamente, e tutto filerà liscio: l'ho provato sulla mia pelle).
Abbiamo costruito una formula che dice di se stessa "io non sono dimostrabile".
La prossima volta capiremo meglio la potenza di una tale costruzione.
Compiti per casa: ripassare il paradosso del mentitore.
Ve sallustio.

Godel #5.2 - secondo passaggio

Una doverosa precisazione, non tanto per i lettori abituali che mi conoscono bene, quanto per quelli occasionali che dovessero imbattersi in questi obbrobri metamatematici per puro caso e forse con eccessiva fiducia: io di matematica non capisco una mazza.
Non l'ho studiata in maniera approfondita nè la pratico per professione, ricordo a malapena quella fatta al liceo o in uno o due esami all'università. Forse è proprio per questo che sono affascinato dalle spiegazioni chiare ma forse semplicistiche della letteratura divulgativa che mi diletto a leggere negli ultimi tempi.
Pertanto nei post di argomento matematico e scientifico troverete nel migliore dei casi solo compendi spero comprensibili di quello che leggo. Sono ovviamente disponibilissimo a dare i titoli delle fonti a chiunque sia interessato.

Ora andiamo avanti con il secondo passaggio necessario alla dimostrazione del teorema di incompletezza di Godel.
Devo dire la verità, questi passaggi intermedi sono un po' noiosi, ma sono necessari per preparare l'apoteosi finale (come la costruzione complessa di un'azione, con pallosi passaggi a centrocampo, necessari però per poi finalizzare in un gol acrobatico... Che ve ne pare come metafora cari lettori calciofili?).

Riprendiamo, sempre a titolo di esempio, la formula

1)                              ($x)(x=Sy)

Che ha M come numero di Godel e che significa "esiste un successore immediato di y".
La variabile y contenuta in essa ha il numero di Godel 13 (vedi post #3). Essendo y una variabile, possiamo sostituire ad essa ogni valore, le variabili servono a questo. Sostituiamo a y il numero M (il numero di Godel della formula intera) e otteniamo la nuova formula ($x)(x=SM). Significa che esiste un successore immediato di M.
Anche la formula  ($x)(x=SM) ha un numero di Godel, che sarà diverso da M. Questo sarà il numero di Godel della formula che si ottiene dalla formula con numero di Godel M sostituendo alla variabile con numero di Godel 13 il numero M. Possiamo, per convenzione, scrivere questo numero così:

                                Sost(M, 13, M)

che significa nient'altro che "il numero di Godel della formula che si ottiene dalla formula con numero di Godel M sostituendo alla variabile con numero di Godel 13 il numero M".
Se non avete capito il concetto avete letto troppo di fretta, leggete con calma e ce la farete, come ho fatto io.
...
Tranquilli, io aspetto....
...
Fatto?
ok, ora tenetelo bene a mente.
Alla prossima.

Godel #5.1 - primo passaggio

Troppa fretta. E' sempre stato uno dei miei problemi. E per dimostrarvi la mia capacità di autocritica vi autorizzo anche a facili battute a sfondo sessuale.
Da quello che ho capito dai feedback scritti e orali ricevuti, fino al post #4 era tutto più o meno chiaro. Il #5 è stato invece il fallimento totale. Facile capire che il problema è il #5, pertanto riprenderò da quello e seguendo il consiglio di buona parte dei miei lettori dedicherò un post ad ogni passo logico.

Spero che almeno la pianificazione del lavoro che apriva il post fosse sufficientemente comprensibile.
Con la codificazione numerica descritta nel #3 abbiamo solo introdotto il linguaggio che Godel intende utilizzare nella sua dimostrazione.
Ora con questo linguaggio dobbiamo:
a. costruire una formula che dice di se stessa: "io non sono dimostrabile"
b. dimostrare che questa formula è in effetti indecidibile (nè dimostrabile nè negabile)
c. dimostrare che, pur essendo indecidibile con gli assiomi del sistema di riferimento, è tuttavia vera.

L'obiettivo a. si suddivide nei tre passaggi che avevo sconsideratamente compresso nel precedente post, ma ora mi sono ricreduto, quindi analizziamo qui solo il primo passaggio, che riguarda la relazione tra una dimostrazione e la sua conclusione. Partiamo dall'esempio di dimostrazione che avevamo fatto in precedenza (attenzione, comunicazione agli utenti, la mia adorata ma un po' birichina Sallustia interpreta la E rovesciata che ho tentato di scrivere come simbolo di esistenza con un simbolo di dollaro $: se voi fino ad ora avete visto la E rovesciata bene, ma da ora in poi il $ significa "esiste").

1)                             ($x)(x=Sy)
2)                             ($x)(x=S0)

La dimostrazione qui sopra significa semplicemente che esiste un x tale che x è un immediato successore di y, quindi, per y=0, esiste un successore immediato del numero zero, quindi esiste il numero 1. A parte il significato della dimostrazione, che non è fondamentale per quanto segue, avevamo visto che il numero di Godel della 1) era M e che quello della 2) era N. In base alle notazioni condivise l'intera dimostrazione aveva come numero di Godel                          
K=2^M x 3^N
Questo è un numero stratosferico, perchè i numeri di Godel dei singoli passaggi della dimostrazione, che sono già enormi, compaiono come esponenti dei primi due numeri primi, 2 e 3. Per quanto grande possa essere, la formula qui sopra mette in relazione K (il numero di Godel dell'intera dimostrazione) e N (il numero di Godel della sua conclusione). Facciamo un esempio ancora più semplice. Nel #3 avevamo detto che ($x)(x=Sy) aveva numero di Godel
M=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 significa che esiste una relazione tra l'intero numero M e, ad esempio, la sua ultima parte 29^9 (nel caso specifico 29^9 è un divisore dell'intero numero M). Allo stesso modo esiste una relazione tra K e N in K=2^M x 3^N. Per chi ricorda qualcosa delle funzioni algebriche del liceo è come se dicessimo che K è in funzione di N, ossia K=f(N). Però per ricordarci che K è l'intera dimostrazione e N è la sua conclusione, al posto di K=f(N) scriviamo Dim(K,N) (abbreviazione di "K" è la dimostrazione di "N"), che vuol dire che esiste una relazione tra K ed N: se la relazione esiste significa che il super numero K ha in qualche modo dentro di se il numero N, e se ciò è vero vuol dire che la dimostrazione K ha dentro di se il passaggio N e che quindi N è la conclusione (o addirittura un passaggio intermedio, che è lo stesso) di K.
Dim(K,N) significa metamatematicamente “la sequenza di formule con numero di godel K è una dimostrazione della formula con numero N".

Se la tale relazione metamatematica non esiste, quindi se N non è in relazione con K, e quindi se N non è la formula conclusiva del processo di dimostrazione identificato con K, allora possiamo scrivere ~Dim(K,N).  In quest'ultimo caso preferisco scegliere lettere diverse da Ke N perchè nel nostro esempio K è davvero una dimostrazione di N, quindi per non fare confusione cambierò le lettere in x e z per simboleggiare un altro processo di dimostrazione e un'altra conclusione non in relazione tra loro: scriverò pertanto

~Dim(x,z)

Abbiamo concluso che ~Dim(x,z) significa “la sequenza di formule con numero di Godel x non è una dimostrazione della formula con numero di Godel z”.
E questo è il primo passaggio.
E' più chiaro? Attendo almeno un paio di feedback tipo "eureka", altrimenti non proseguo oltre.

Godel #5 - Una parete ripida prima della vetta

Fino ad ora abbiamo costruito un linguaggio metamatematico (vedi post #3).
Ora, utilizzando questo linguaggio, dobbiamo:
a. costruire una formula che dice di se stessa: io non sono dimostrabile.
b. dimostrare che questa formula è in effetti indecidibile (nè dimostrabile nè negabile)
c. dimostrare che tuttavia è vera.

In questo post ci occupiamo dell'obiettivo a, e per far ciò dobbiamo affrontare alcuni passaggi intermedi.

Primo passaggio.
Ritorniamo al piccolo esempio di dimostrazione presentato precedentemente:
1)                             ($x)(x=Sy)
2)                             ($x)(x=S0)

Dove il numero di Godel della dimostrazione completa è K=2^M x 3^N.
E’ abbastanza semplice notare che esiste una relazione matematica tra K e N, quindi che K dipende da N. Ciò significa inoltre, dal punto di vista metamatematico, che esiste una relazione tra il numero K, che è tutta la dimostrazione, e il numero N, che è la sua conclusione (ad esempio ricordando come funziona la costruzione del numero di Godel, è facile notare che N deve essere un divisore di K). Esiste quindi, ed è ben definita, una relazione tra la dimostrazione K e la conclusione N, e la possiamo scrivere Dim(K,N). Quindi Dim(K,N) significa metamatematicamente “la sequenza di formule con numero di godel K è una dimostrazione della formula con numero di godel N”. Il concetto di verità passa in questo modo dalla dimostrazione matematica (tutti i passaggi logici dalla premessa alla conclusione) alla effettività della relazione metamatematica tra i numeri di Godel della dimostrazione e della conclusione: se esiste la relazione definita tra i due numeri di Godel, la dimostrazione e la conclusione sono vere. Se la relazione metamatematica non esiste questo si scrive ~Dim(x,z), che significa “la sequenza di formule con numero di Godel x non è una dimostrazione della formula con numero di Godel z” (ho cambiato le lettere e le ho generalizzate con “x” e “z” per discostarmi dall’esempio concreto che avevo fatto, che invece è vero).

Secondo passaggio.
Riprendiamo, sempre a solo titolo di esempio, la formula
1)                              ($x)(x=Sy)
 
Che ha M come numero di Godel. La variabile y contenuta in essa ha il numero di Godel 13 (vedi post #3). Essendo y una variabile, possiamo sostituire ad essa ogni valore. Sostituiamo a y il numero M (il numero di Godel della formula intera) e otteniamo la nuova formula ($x)(x=SM). Significa che esiste un successore immediato di M. Anche la formula  ($x)(x=SM) ha un numero di Godel: il numero di Godel della formula che si ottiene dalla formula con numero di Godel M sostituendo alla variabile con numero di Godel 13 il numero M.
Possiamo scrivere questo numero così:

                                         Sost(M, 13, M)

che significa esattamente "il numero di Godel della formula che si ottiene dalla formula con numero di Godel M sostituendo alla variabile con numero di Godel 13 il numero M".


Terzo passaggio.
Riprendiamo la ~Dim(x,z), che dice: "la sequenza di formule con numero di Godel x non è una dimostrazione della formula con numero di Godel z".
Scriviamo poi una nuova formula. Visto che “per ogni x” si scrive "(x)" scriviamo:
(x)~Dim(x,z)
che significa che “per ogni x, non si verifica mai che la sequenza di formule con numero di Godel x è una dimostrazione della formula con numero di Godel z”. In pratica la formula dice che z non è dimostrabile.

Possiamo scrivere poi un caso particolare della formula di sopra:
A:       (x)~Dim(x,Sost(y,13,y))
che significa "la formula con numero di Godel Sost(y,13,y) non è dimostrabile”.
Questa nuova formula, essendo una formula aritmetica come tutte le altre, ha un suo numero di Godel, che diciamo essere J. Se sostituiamo alla variabile y il numero J, si ottiene la particolare formula ricercata da Godel:
G:       (x)~Dim(x,Sost(J,13,J))
Ovviamente anche questa G ha un suo numero di Godel, che se ci riflettiamo è proprio Sost(J,13,J) che è contenuto in essa.
Infatti Sost(J,13,J) non è altro che il numero di Godel della formula che si ottiene dalla formula con numero di Godel J sostituendo alla variabile con numero di Godel 13 (ossia a y) il numero J. Ma G è stata ottenuta proprio così, ossia sostituendo alla variabile y di A il numero di Godel di A, ossia J.
Ma siccome G significa “la formula con numero di Godel Sost(J,13,J) non è dimostrabile”, e siccome il numero di Godel di G è proprio Sost(J,13,J), di conseguenza G dice: “Io non sono dimostrabile”!!! (io non uso mai il punto esclamativo e nemmeno il grassetto, ma stavolta non ne posso fare a meno)... questa è roba forte, questo qui sopra è il pezzo più difficile dell'intera dimostrazione di Godel ma ne costituisce la quintessenza, il vero colpo di genio: è in pratica la strutturazione matematica del paradosso del mentitore, da ora in poi le cose fileranno via abbastanza lisce, ma costruire una struttura del genere credo sia stata uno degli apici del ragionamento logico umano.
Abbiamo raggiunto l'obiettivo a, ossia abbiamo costruito una formula che dice di se stessa: io non sono dimostrabile.
Alla prossima, io vado, ho una festa a sorpesa che mi aspetta.

Godel #4 - Ricreazione

Primo: una ovvia ma doverosa considerazione sulla puntata precedente. Come ho già detto non tutti i numeri sono numeri di Godel. Per essere di Godel un numero deve avere una particolare struttura nella sua scomposizione in fattori primi (ogni numero è scomponibile in un modo solo in fattori primi, teorema fondamentale dell'aritmetica). Prendiamo il numero mille. Prima considerazione: non è minore di dieci, quindi non è il simbolo di una costante. Scomposto in fattori primi mille è: 2^3 x 5^3. La struttura dei numeri di Godel dice che i numeri primi devono comparire tutti e in sequenza, qui manca il 3, quindi 1000 non è un numero di Godel. Più o meno allo stesso modo esistono numeri che pur essendo godeliani non significano nulla. Ad esempio il numero 30 è uguale a 2^1 x 3^1 x 5^1, quindi la struttura pare rispettata, ma i simboli 1, 1, 1 (esponenti dei fattori primi di 30) stanno per "~~~", che non significa un gran che.

Secondo: la preparazione del passo successivo si sta dimostrando particolarmente impegnativa, me devo dire che me lo aspettavo. Mi appello quindi al primo dei miei diritti (tra due post possono passare anche mesi senza che questo significhi che abbia abbandonato il mio intento) e mi prendo una pausa di riflessione. Cercherò di mettere ordine alle idee e concretizzare nei prossimi giorni. Sempre che non vada di nuovo a sciare con la famiglia, nel qual caso il mio equilibrio psicofisico ne sarebbe talmente scosso che in seguito potrei scrivere solo di brufoli e tarzanelli (che non è escluso sia per molti versi più interessante di Godel).

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.

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.