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.
Commenti:
RispondiElimina#1 08 Marzo 2011 - 22:39
1) sono lusingato della nota personalizzata. 2) mi compiaccio che le cose lisce le provi sulla tua pelle da lumacone. 3) diciamo pure eureka, anche se 7 secondi dopo averlo letto già non saprei più spiegarlo nemmeno a me stesso. 4) ahooo! S. Sveglia! T'ho dato un giorno di vantaggio per commentare, il povero tacchino credeva di aver perso tutti i suoi lettori non anonimi (gli unici maschi credo, le grupies gli staranno già lanciando le mutande). 5) comunque mi impegno come compito a casa a rileggerlo ogni giorno nell'attesa del prossimo. Pdb
utente anonimo
#2 08 Marzo 2011 - 23:31
Correzione al commento precedente: ciò che al punto 4 avevo scritto per S. Va inteso per E. Me ne scuso con gli interessati. Pdb
utente anonimo
C'è forse un passaggio che mi sfugge: come si dimostra che le formule ben formate sono ricorsivamente definite? Da dove s'evince che(x)~Dim(x,z), cioè che non esistono dimostrazioni di z?
RispondiEliminaciao.
RispondiEliminainnanzitutto mi sono accorto che l'impaginazione di alcuni post pare della dimostrazione è saltata. domani mattina proverò a ricomporla, oggi non ho il mio PC e dall'ipad è complicato.
Riguardo alla tua domanda, non ti sfugge nessun passaggio, la formula non si evince, la poniamo così come parte della costruzione della dimostrazione. E' come se dicessimo "supponiamo che". Se sei andato avanti con la lettura forse ti sarà già stato più chiaro.
Altrimenti scrivimi di nuovo.
Il primo teorema di Godel, da quel che ho capito, afferma che se un sistema formale, F, è corretto e coerente, allora è incompleto; il secondo, invece, mi pare che affermi che un sistema di questo tipo, che è sufficientemente potente, non può dire di sé stesso d'essere corretto. Un sistema si dice corretto se in esso son dimostrabili solo verità; coerente se non s'incappa in delle contraddizioni; sufficientemente potente se è autoreferenziale.
RispondiEliminaDimostrazione del primo teorema
Se si considera la frase autoreferenziale che di sé stessa dice "io non sono dimostrabile all'interno del sistema formale F-corretto", allora, per definizione di sistema corretto, la frase in questione è dimostrabile: è vero che non è dimostrabile, dato che essa afferma proprio di non esserlo; di conseguenza, il suo contrario è falso: se, infatti, fosse vero, allora sarebbe refutabile. Tirando le somme, ci si trova innanzi ad una frase indecidibile né dimostrabile, né refutabile all'interno del sistema esaminato.
Dimostrazione del secondo teorema
Assumendo che F-corretto possa dire di sé stesso d'essere appunto corretto, allora dovrebbe poterlo arguire sfruttando le proposizioni, gli assiomi, le formule in esso definite; tuttavia, dato che contiene al suo interno un assunto indecidibile - quello autoreferenziale -, non può esser sicuro della propria correttezza: occorre che sia un altro sistema a stabilirne l'eventuale correttezza.
Esempio
Se s'assume d'essere in un sistema in cui valgono gli assiomi validi sia per i numeri naturali che per quelli razionali, questi non può dire di sé stesso d'esser corretto: la formula sqrt(d^2)= r, ove "d" ed "r" son numeri reali non irrazionali, non ha che soluzioni irrazionali. Il sistema in esame, per come è stato definito, non ha gli strumenti necessari per poter esprimersi in merito ad essa; per cui, ai suoi "occhi", è indecidibile. La conclusione è che ci si trova in un sistema incompleto dove la formula sopra menzionata è autoreferenziale proprio perché indecidibile.
Questo è all'incirca quel che ho capito visionando le video-lezioni di Odifreddi.
Tornando al punto 5.3 del tuo post, temo d'aver ancora della confusione in testa: continuo a non capire perché si debba supporre che la proposizione "(x)~Dim(x,z)" è vera, se è proprio quello che dev'essere dimostrato: come posso dare per scontato che la formula corrispondente a "z" non ha alcuna dimostrazione? Ricapitolando: alla formula ($x)(x=Sy), F(y), s'associa un determinato numero di Godel, G(F(y)) = M, secondo il modus operandi di Godel da te esposto; poi si sostituisce alla variabile "y" proprio G(M), ottenendo la formula F(M) con numero di Godel G(F(M)). Dopodiché non riesco più a seguirti nel ragionamento.
post scriptum:
non leggo il PS.
Eliminada quello che ho capito, si prende come ipotesi di partenza un z non dimostrabile, immagino esista, e si basa su questo l'intero meccanismo. se ti risulta semplice puoi anche supporre che z sia un teorema non appartenente al sistema di partenza, quindi non dimostrabile, per esempio 2+2=5.
Ho provato a ripercorrere i passi che espongo nel post con questo presupposto, mi pare che funzioni, basta sostituire il numero di godel delle formule dove indicato, il paradosso giunge alla fine.
A mio parere non devi impuntarti su quel passaggio, se arrivi in fondo ti rendi conto che quel z può essere qualsiasi formula non dimostrabile.
Ma non sono un matematico, potrei sbagliarmi.
Grazie comunque del commento.
Ok, ora quel passaggio m'è chiaro... Hai ragione: basta considerare un teorema indecidibile all'interno d'un determinato sistema formale, ed effettivamente di teoremi simili se ne possono ricavare a valanghe (basta considerare l'irrazionalità della diagonale del quadrato, indimostrabile in un sistema sorretto da regole valide solo per numeri razionali). A volte son un po' duro di comprendonio. Ora tento di capire l'ultimo passaggio, quel triplo avvitamento carpiato che al momento mi risulta un po' ostico da assimilare.
RispondiEliminarisulta difficile anche per me, ogni volta che lo ripercorro. del resto mi risulta difficile anche il,paradosso del barbiere, ma alla fine succede che dopo un po' ottengo l'iluminazione...
EliminaCiao,non capisco il senso dell'espressione sost(y,13,y), dato che y è una variabile, non un preciso valore numerico (qual è, invece, M). Se sost(M,13,M) è indicativa del numero di Gödel della formula che ci si ricava sostituendo M, che è un preciso numero gödeliano, alla variabile y (alla quale è convenzionalmente associato il numero gödeliano 13), che senso potrà mai avere sostituire una variabile con un'altra variabile (tu, tra l'altro, sostituisci y con sé stessa). Usando il tuo linguaggio, è come se scrivessi: "sost(y,13,y) rappresenta il numero di Gödel della formula che si ottiene dalla formula con numero di Gödel y sostituendo alla variabile con numero di Gödel 13 il numero y". Dato che y non è un valore numerico ma una variabile, non riesco a dare un significato a questo "terzo passaggio con aritmoquinazione".
RispondiElimina