sabato 12 febbraio 2011

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.

1 commento:

  1. Anonimo15/11/11

    Commenti:
    #1 12 Febbraio 2011 - 20:20

    Ti ho letto brevemente e in fretta perché devo uscire per andare a una festa (che palle). Mi riservo di commentare in seguito. Per ora due sole brevi note: quando fai riferimento al post Godel n.4 forse intendi il n.3? Poi mi sa che vai troppo in fretta; non aver paura di dilungarti nel ripetere i dettagli dei passaggi perché io, di nuovo non ci sto capendo una mazza.
    utente anonimo
    #2 14 Febbraio 2011 - 11:39

    Ale ognuno dei passaggi meriterebbe un post da solo.
    Io non ho capito NULLA!
    utente anonimo

    RispondiElimina