Il primo teorema di incompletezza di Gödel
Come promesso, eccovi la ricetta per uno schema di dimostrazione del primo teorema di incompletezza di Gödel. Ho saltato alcuni punti tecnici per i quali dovete fidarvi della parola del grande logico, se proprio non della mia; e ho cercato di spiegare il meglio possibile il significato dei singoli passi, perché altrimenti uno si chiede davvero la necessità di fare tutta quella costruzione. Vi avviso subito: non ci sono concetti molto esoterici, però bisogna avere un minimo di dimestichezza con la logica matematica per seguire la dimostrazione. Prendetevela comoda: se vi consola, ci ho messo delle settimane per riuscire a capirla in modo sufficiente da saperla riscrivere.
0. Partiamo dalla definizione di un linguaggio formale che possa codificare l’aritmetica: Gödel nel suo articolo ha preso i Principia Mathematica, ma possiamo usare per esempio l’Aritmetica di Peano detta anche “zero e i suoi successori”. Partendo dal nostro linguaggio PM, consideriamo i simboli (l’alfabeto) di questo linguaggio: lo stock standard è mostrato qui sotto. Se non vi ricordate il significato dei simboli, tornate al mio post precedente.
Lista della spesa per l’Aritmetica di Peano:
– una costante, 0
– una variabile x
– un simbolo ‘ (primo) per costruire tutte le variabili che vogliamo x‘, x”, x”’… (poi nel seguito barerò e userò anche y e z, ma il principio resta lo stesso)
– una funzione unaria s, dove sx è “il successore di x”
– il quantificatore universale ∀ e il quantificatore esistenziale ∃
– parentesi sinistra e destra ( e ) per dare un ordine alle operazioni da compiere
– i simboli logici ∧, ∨, ¬
– le funzioni binarie + e ×
– le relazioni di uguaglianza = e di ordine < (minore)
ma per fare le cose semplici adesso uso solo 0, +, =, (, ), s. A ciascuno dei simboli associamo poi un numero positivo: nel nostro caso potremmo per esempio dar loro i numeri da 1 a 6 nell’ordine.
1. Prendiamo ora una successione (una stringa) di simboli dell’alfabeto. Essendo una successione essa è automaticamente ordinata, quindi possiamo associare all’n-simo simbolo da sinistra l’n-simo numero primo, elevato alla potenza corrispondente al simbolo stesso. Insomma, a 0=0 corrisponde 21·33·51 = 270, a 0=s0 corrisponde 21·33·56·71 = 5906250 e a 0=( corrisponde 21·33·54 = 33750. Il bello è che visto che ogni numero si può fattorizzare in un solo modo c’è una corrispondenza biunivoca tra numeri positivi (a partire da 0 che è la stringa nulla) e stringhe. Questi numeri si chiamano numeri di Gödel. Scriverò G(F) per indicare il numero di Gödel di una formula F.
1 bis. Spero vi siate accorti che la corrispondenza che abbiamo definito è al momento solo un giochino tipografico: come sa chi per esempio ha avuto a che fare con l’XML, possiamo infatti avere stringhe che non hanno alcun senso come nel caso del mio terzo mio esempio. Anche tra le stringhe sensate (le fbf, formule ben formate: in inglese trovate wff che sta per well-formed formulas) abbiamo due categorie: quelle false come la seconda visto che 0 non è uguale a 1, e quelle vere come la prima.
2. È interessante notare che c’è un sistema assolutamente automatico per trovare tutte le fbf (tecnicamente si dice che sono una “classe ricorsivamente definita“); quindi l’insieme dei numeri di Gödel corrispondenti alle fbf non ha concettualmente nulla di diverso da altri insiemi come i quadrati perfetti, i numeri primi o quelli di Fibonacci. Uno potrebbe studiare le proprietà di questi numeri, e naturalmente descriverle nel linguaggio dei Principia Mathematica. Vi siete accorti di cosa è successo? Siamo partiti da PM, abbiamo tradotto le sue stringhe in numeri di Gödel, e adesso rimettiamo questi numeri dentro PM! Non abbiamo ancora l’autoreferenzialità, però: siamo solo passati a un livello superiore. Per il momento non c’è ancora nulla di strano, o se preferite siamo ancora al paradosso anti-Frege: ricordate che i PM sono nati apposta per lavorare su una scala di livelli.
3. Ma è molto più interessante scoprire che anche la classe delle formule dimostrabili è ricorsivamente definita. Le formule dimostrabili non sono nient’altro che i teoremi: se un teorema è dimostrabile, esiste una serie di passaggi formali – ricordate che i Principia Mathematica sono proprio nati per mostrare come tutta l’aritmetica può essere dimostrata automaticamente – che a partire dagli assiomi porta alla stringa corrispondente al teorema. Questo a sua volta significa che c’è un algoritmo computazionale che lavora sui numeri di Gödel corrispondenti!, e che possiamo parlare dell’insieme dei numeri di Gödel “teorematici”, che cioè corrispondono ai teoremi. 270 è un numero teorematico, visto che si può dimostrare che 0=0 (non lo credevate, vero?); mischiando al solito i livelli, possiamo enunciare in PM le affermazioni “270 è un numero teorematico” e “270 NON è un numero teorematico”. La prima è vera, la seconda falsa; quello che conta è che sono entrambe fbf. Naturalmente anche la dimostrazione stessa è esprimibile come una serie finita di passaggi logici e quindi ha un suo numero di Gödel.
3 bis. Vi siete accorti che non ho dimostrato che le formule dimostrabili, o se per questo le fbf, sono ricorsivamente definite? Ecco, questo è un punto su cui dovete fidarvi oppure leggere l’articolo originale di Gödel, o almeno la sua traduzione in inglese. Però vi garantisco che è una caratteristica molto importante.
4. Digressione: come si fa a scoprire che un numero è teorematico? La cosa non è così banale come sembra a prima vista. Con i numeri fbf la cosa, almeno in linea di principio, è semplice. Le formule che si generano man mano sono sempre più lunghe, e quindi corrispondono a numeri di Gödel sempre più grandi. Beh, non è proprio così, visto che gli esponenti dei singoli fattori potrebbero essere minori dopo la generazione della nuova formula; ma per ogni k c’è comunque un limite superiore finito per il numero corrispondente a una formula con k termini, e quando superiamo quel limite senza trovare nulla siamo certi che il numero non corrisponde a una fbf. Per i numeri teorematici non è così: può capitare che mentre generiamo le stringhe di una dimostrazione ne otteniamo una più corta della precedente, proprio come quando facevamo gli esercizi sulle espressioni e semplificavamo tutto.
4 bis. Ma è importante sapere se un numero è teorematico? Beh, lo sarebbe sì. Immaginiamo di avere un guru, o un Göru come lo chiama Hofstadter, che sappia dirci se un numero è teorematico o no. Bene: in questo caso sapremmo risolvere tutti i teoremi della teoria dei numeri. Dato un teorema T, Basta calcolare il numero di Gödel G(T) corrispondente al teorema, darlo a Göru e chiedergli se è teorematico. Se la risposta è sì, allora il teorema è vero; altrimenti è falso. Beh, questo naturalmente se è vero il Credo del Matematico!
4 ter. Se a qualcuno leggendo fin qua è venuto in mente l’Entscheidungsproblem, ha intuito tante cose :-) Ma il centenario della nascita di Alan Turing è l’anno prosssimo, quindi dovete aspettare ancora un po’ perché vi parli anche di questo. Se non gli è venuto in mente, nema problema: qui stiamo dimostrando dell’altro.
5. Ora inizia la parte davvero complicata, perché iniziamo ad avvitarci (deliberatamente!) su noi stessi. Quello che vorremmo fare è avere una formula che, letta come numero di Gödel e decodificata, parli ancora di sé stessa: peccato che, come dovreste avere intuito, la gödelizzazione costruisce numeri molto, molto maggiori di quelli di partenza e quindi non si capisce come si possa far star dentro la formula originaria dopo la decodifica. Il trucco è di usarlo allora come valore dato alla formula stessa!
Il nostro linguaggio permette infatti di scrivere formule con variabili libere, come x=ss0 (notate la differenza con ∃x:x=ss0. In questo secondo caso la x si dice quantificata. Attenzione: x=ss0 non deve necessariamente essere vera o falsa! Non è neppure un’equazione, se per questo. Per ottenere una formula vera o falsa occorre dare un valore per x. Possiamo assegnargli il valore 0 e ottenere una formula falsa, oppure assegnargli 2 e ottenere una formula vera.
6. Naturalmente anche queste espressioni con variabili libere hanno un numero di Gödel. Dato un qualunque numero n e una formula F(x), possiamo allora definire la relazione NONDIMOSTRO(n,G(F)) che afferma “n non è il numero di Gödel di una dimostrazione di F(G(F))”, cioè di F applicata al proprio numero di Gödel. Insomma, si prende il numero G(F), lo si decodifica per ottenere F che come dicevo ha una variabile libera x, si mette G(F) al posto di x e si ricodifica. Otteniamo numeri pantagruelici, ma il bello della matematica è che non ci dobbiamo preoccupare di queste quisquilie. NONDIMOSTRO è una relazione tra i due numeri n e G(F); se n non è la codifica di una dimostrazione – vale a dire l’elenco (finito) di formule che la compongono – di F(G(F)) allora NONDIMOSTRO(n,G(F)) è vero, mentre se quell’elenco è una dimostrazione di F(G(F)) allora ¬ NONDIMOSTRO(n,G(F)), cioè la sua negazione, è vero. Visto che l’elenco è finito e che sappiamo che le formule dimostrabili sono ricorsivamente definite, siamo sicuri che in un tempo finito si riesce a ottenere una delle due possibilità, e pertanto una delle due possibilità è dimostrabile.
7. Su, che ci siamo quasi. Abbiamo visto che NONDIMOSTRO(y,z) significa che y non è il numero di Gödel di una dimostrazione di z, dove z è una formula con una variabile libera che viene quantificata dando come valore alla variabile il numero di Gödel della formula stessa. Naturalmente dato uno z ci saranno alcuni y per cui NONDIMOSTRO(y,z) è vero (y non è una delle possibili dimostrazioni di z) e forse altri per cui è falso (se z è vero e dimostrabile allora c’è almeno una sua dimostrazione e quindi un numero di Gödel). Definiamo ora una nuova formula P(z) data da ∀y NONDIMOSTRO(y,z): quindi se mettiamo al posto di z un numero di Gödel G(F) , otteniamo P(G(F)) = ∀y NONDIMOSTRO(y,G(F)), o detto in modo più terra terra “la formula F(G(F)) non ammette alcuna dimostrazione”, come abbiamo visto sopra.
8. E se invece che una F qualunque prendiamo proprio P, facendo un triplo avvitamento autoreferenziale? La formula P(G(P)) equivale a ∀y NONDIMOSTRO(y,G(P)), cioè “la formula P(G(P)) non ammette alcuna dimostrazione”, cioè “io non sono dimostrabile”. Siamo finalmente arrivati alla soluzione! Infatti la nostra ipotesi iniziale, il Credo del Matematico, ci dice che una e una sola delle formule P(G(P)) e ¬ P(G(P)) è dimostrabile.
Se P(G(P)) fosse dimostrabile, prendiamo una sua dimostrazione e il suo numero di Gödel n. Per definizione di NONDIMOSTRO, otteniamo che ¬ NONDIMOSTRO(n,G(P)) è dimostrabile, e pertanto che ¬ P(G(P)) è dimostrabile. Aiuto! Contraddizione! Niente da fare, insomma.
Se invece fosse ¬ P(G(P)) ad essere dimostrabile, avremmo per definizione e per le relazioni tra i quantificatori che la formula ∃ y: ¬ NONDIMOSTRO(y,G(P)) è dimostrabile. Prendiamo un y qualunque e supponiamo che ¬ NONDIMOSTRO(y,G(P)) sia dimostrabile. Ma allora per definizione y è il numero di Gödel di una dimostrazione di P(G(P))… dimostrazione che non può esistere, per quanto visto appena sopra. Ma y era qualunque, pertanto per ogni y la nostra ¬ NONDIMOSTRO(y,G(P)) non è dimostrabile. Dunque ∃ y: ¬ NONDIMOSTRO(y,G(P)) è falsa, e pertanto ¬ P(G(P)) non è dimostrabile.
Abbiamo finito, non ve ne siete accorti ? :-) Se siete riusciti ad arrivare sin qui senza perdervi, vi faccio i miei più sinceri complimenti (e li faccio anche a me… garantisco che è stato un bagno di sangue preparare questa dimostrazione). Altrimenti provate a raccontare i vostri dubbi, e vediamo se riesco a diradarli almeno un po’.
Leave a comment