Breve viaggio dentro i teoremi di incompletezza di Godel

[tta_listen_btn]

Nel 1931, il logico-matematico austriaco Kurt Gödel ha creato quello che probabilmente possiamo definire uno dei risultati più sbalorditivi della storia.

I matematici dell’epoca erano alla ricerca di solide basi per la matematica: cercavano un insieme di fatti, o assiomi matematici, che fossero allo stesso tempo consistenti e completi, senza portare a contraddizioni; che potessero quindi rappresentare i pilastri essenziali di tutte le verità matematiche.

Quel sogno fu infranto dai teoremi di Gödel, pubblicati quando lo studioso aveva appena 25 anni. Egli provò che qualunque insieme di assiomi si ponga come possibile fondamento per la matematica, questi saranno sempre incompleti; ci saranno sempre delle verità sui numeri che quegli assiomi non saranno in grado di provare. Dimostrò inoltre che non esiste alcun insieme di assiomi che possa provare la sua stessa consistenza.

I suoi teoremi di incompletezza stavano a significare che non esiste una teoria matematica che abbracci tutto, nessuna teoria che unisca ciò che è provabile e ciò che è vero. Ciò che i matematici possono provare dipende delle loro assunzioni iniziali, non da una verità di base dalla quale scaturiscono tutte le risposte.

In questi 89 anni dalla scoperta di Gödel, i matematici si sono imbattuti proprio in questo tipo di domande senza risposta, che erano state previste dai teoremi. Per esempio, lo stesso Gödel aveva aiutato a stabilire che l’ipotesi del continuo, che riguarda le dimensioni dell’infinito, è indecidibile, come lo è il problema dell’arresto, nel quale ci si chiede se un programma da computer, alimentato da un input casuale, continuerà indefinitamente il suo processo o si bloccherà. Anche in fisica sono sorte delle domande indecidibili, dimostrando che l’incompletezza di Gödel non riguarda solo la matematica, ma anche la realtà.

Andiamo a vedere, in maniera semplice, come Gödel propone la dimostrazione dei suoi teoremi.

Numerazione di Gödel

Il principale obiettivo di Gödel fu quello di mappare le definizioni relative a un sistema di assiomi su delle definizioni collocate dentro il sistema stesso – cioè, dentro delle definizioni che riguardano i numeri. Questa mappatura consente a un sistema di assiomi di parlare, in maniera convincente, di se stesso.

Il primo passo di questo processo è quello di mappare ogni possibile assunto, o serie di assunti, di natura matematica, su un unico numero chiamato numero di Gödel.

Nel 1958, Ernest Nagel e James Newmann hanno pubblicato un libro, La prova di Gödel, dove presentano una versione leggermente modificata dello schema dei numeri di Gödel; questo schema inizia con 12 simboli elementari che rappresentano il vocabolario di base per esprimere un insieme di assiomi di base. Per esempio, affermare che qualcosa esiste può essere espresso dal simbolo ∃, mentre l’addizione è espressa dal simbolo +. È importante specificare che il simbolo s, che individua l’operazione successore di, fornisce un modo per specificare i numeri; per esempio, la sequenza ss0, equivale a 2.

Sotto si riporta la tavola dei numeri di Gödel:

Next, letters representing variables, starting with x, y and z, map onto prime numbers greater than 12 (that is, 13, 17, 19, …).

Quindi, ogni combinazione di questi simboli e di queste variabili – cioè, ogni formula o sequenza di formule aritmetiche che possono essere costruite – possiede il proprio numero di Gödel.

Per esempio, consideriamo l’espressione 0 = 0. I tre simboli della formula corrispondono ai numeri di Gödel 6, 5, 6. Gödel trasforma questa sequenza di tre numeri in un unico, singolo numero – un numero che non potrà essere generato da nessun’altra sequenza di simboli. Per fare questo, Gödel prende i primi tre numeri primi (2, 3 e 5), eleva ognuno di questi numeri alla potenza equivalente al numero di Gödel del simbolo che si trova nella stessa posizione della sequenza e successivamente moltiplica fra di loro questi numeri. Quindi, la relazione 0 = 0 diventa 2^6×3^5×5^6 = 243.000.000.

Questa mappatura funziona perché non potranno esistere due formule esprimibili con lo stesso numero di Gödel. I numeri di Gödel sono degli interi, e gli interi si possono fattorizzare, come prodotto di numeri primi, in un solo modo. Quindi, l’unico modo per fattorizzare il numero 234.000.000 come prodotto di numeri primi è proprio 2^6 x 3^5 x 5^6, e ciò vuol dire che esiste una sola possibilità per decodificare il numero di Gödel: la formula 0 = 0.

A questo punto Gödel fa un passo avanti. Una prova matematica consiste in una sequenza di formule. E quindi Gödel ha dato a ogni sequenza di formule un unico numero di Gödel. In questo caso, inizia con la lista dei numeri primi, come fatto prima – 2, 3, 5, e così via. Successivamente eleva ogni numero primo al numero di Gödel della formula che, nella sequenza, si trova nella stessa posizione (2^243.000.000x…., se 0 = 0 viene prima) e quindi moltiplica insieme tutti i fattori.

Aritmetizzare la metamatematica

Il vero vantaggio è che anche dichiarazioni su formule aritmetiche, definite dichiarazioni metamatematiche, possono essere tradotte in formule con numeri di Gödel.

Consideriamo dapprima la formula ~(0 = 0) , cioè zero non è uguale a zero. Questa formula è chiaramente falsa. Ciononostante, anche per questa formula esiste il corrispondente numero di Gödel: 2 elevato alla potenza di 1 (il numero di Gödel corrispondente al simbolo ~), moltiplicato per 3 elevato alla potenza 8 (il numero di Gödel corrispondente al simbolo “parentesi aperte”), e, così via, ottenendo il numero 2^1 x 3^8 x 5^6 x 7^5 x 11^6 x 13^9.

Dal momento che si possono generare numeri di Gödel per tutte le formule, anche per quelle false, è lecito associare quindi a queste formule il loro numero di Gödel.

Si consideri la definizione “il primo simbolo della formula ~(0 = 0) è una tilde”. Questa assunzione metamatematica (vera) sulla formula ~(0 = 0) si traduce in una definizione sul numero di Gödel della formula – ovvero, che il suo primo esponente è 1, il numero di Gödel per il simbolo tilde. In altre parole, la nostra affermazione dice che 2^1 x 3^8 x 5^6 x 7^5 x 11^6 x 13^19 ha un singolo fattore del 2. Se la formula ~(0 = 0) fosse iniziata con un simbolo diverso dal tilde, il relativo numero di Gödel avrebbe al massimo due fattori di 2. Più precisamente, 2 è un fattore di 2^1 x 3^8 x 5^6 x 7^5 x 11^6 x 13^19 , ma 2^2 non lo è.

È possibile convertire l’ultima definizione in una precisa formula matematica che può essere scritta utilizzando dei simboli molto elementari. Anche questa formula ha ovviamente il proprio numero di Gödel, calcolabile mappando i suoi simboli in potenze di numeri primi.

Anche una definizione metamatematica può essere convertita in simboli. Questo vuol dire che esiste sempre una qualche sequenza di formule, con numero di Gödel x, che prova la formula con numero di Gödel k – o, in altri termini, che la formula con numero di Gödel k può essere provata.

L’ulteriore intuizione di Gödel fu che poteva sostituire il numero di Gödel di una formula con la formula stessa, senza grossi problemi.

Per vedere come funziona la sostituzione, si consideri la formula (∃x)(x=sy). Questa formula ci dice che esiste una qualche variabile x che è successiva a y, o, in altre parole, che y ha un successore. Come tutte le formule, anche questa ha il suo numero di Gödel – un qualche numero intero che chiameremo m.

A questo punto introduciamo, nella formula, il numero m al posto del simbolo y. Questo passaggio genera una nuova formula, (∃x)(x=sm), ovvero, m ha un successore. Come potrebbe essere chiamato il numero di Gödel di questa formula? Vi sono tre pezzi di informazione da comunicare: abbiamo iniziato con la formula il cui numero di Gödel è m. In questa formula, si sostituisca m con il simbolo y. In accordo con lo schema di mappatura introdotto in precedenza, al simbolo y corrisponde il numero di Gödel 17. Il nuovo numero di Gödel della formula sarà (m, m, 17).

La sostituzione costituisce il punto cruciale della prova di Gödel.

Gödel ha considerato una definizione metamatematica sulla falsariga della definizione “La formula con sottonumero di Gödel (y, 7, 17)”. Facendo riferimento alla notazione sopra descritta, la formula con il sottonumero di Gödel (y, y, 17) è quella che si ottiene prendendo la formula con numero di Gödel y (una qualunque variabile non nota) e sostituendo questa variabile y ogni qualvolta vi sia un simbolo il cui numero di Gödel sia 17 (cioè, ogni volta vi sia una y).

Anche se la faccenda si complica un po’, la definizione metamatematica – La formula con il sottonumero di Gödel (y, y, 17) non può essere provata – può sicuramente essere tradotta in una formula con un unico numero di Gödel, che chiameremo n.

Ancora un ultimo passo nella sostituzione: Gödel crea una nuova formula sostituendo il numero n laddove vi era y nella formula precedente. Questa nuova formula recita “La formula con il sottonumero (n, n, 17) non può essere provata. Questa formula verrà chiamata G.

Naturalmente, anche G ha il suo numero di Gödel. E il suo valore non può che essere il sottonumero (n, n, 17). Per definizione, il sottonumero (n, n, 17) è il numero di Gödel della formula che scaturisce prendendo la formula con numero di Gödel n e sostituendo n ogni qualvolta vi sia un simbolo con il numero di Gödel 17. E G è esattamente questa formula! Grazie all’unicità della fattorizzazione dei numeri primi, è possibile vedere che la formula che esprime G non è altro che G stessa.

Se G può essere provata, significa che vi è una qualche sequenza di formule che prova la formula, con sottonumero di Gödel (n, n, 17). Ma questa formula è opposta a G, e quindi non esiste alcuna prova. Definizioni opposte, G e -G, non possono essere contemporaneamente vere in un sistema assiomatico consistente. Quindi la verità di G deve essere indecidibile.

Comunque, sebbene G sia indecidibile, è chiaramente vera. G afferma “La formula con sottonumero di Gödel (n, n, 17) non può essere provata” e questo è ciò che effettivamente è stato trovato. Poiché G è contemporaneamente vera e indecidibile nel sistema assiomatico utilizzato per costruirla, allora il sistema è incompleto.

Si potrebbe pensare di inventare un nuovo sistema assiomatico, utilizzarlo per provare la formula G e quindi risolvere il paradosso. Ma ciò non è possibile. Gödel ha dimostrato che un sistema assiomatico superiore darebbe la possibilità di costruire una nuova, e vera, formula G’, che non può essere provata nell’ambito del nuovo sistema.

Nessuna prova di consistenza

Si è detto quindi che se un insieme di assiomi è consistente, allora deve essere incompleto. Questo è proprio il primo teorema di incompletezza di Gödel. Il secondo teorema – che nessun insieme di assiomi può provare la sua stessa consistenza – segue molto facilmente.

Se un insieme di assiomi potrebbe provare che non produrrà mai una contraddizione, allora dovrà esistere una sequenza di formule, costruite a partire da questi assiomi, che prova la formula che significa, matematicamente, “questo insieme di assiomi è consistente”. Per effetto del primo teorema, questo insieme di assiomi dovrebbe essere necessariamente incompleto.

Ma dire “l’insieme di assiomi è in completo” è come dire “Esiste una formula vera che non può essere provata”. Questa affermazione è equivalente alla formula G. E sappiamo anche che gli assiomi non possono provare G.

In questo modo Gödel ha creato una prova per contraddizione: se un insieme di assiomi potrebbe provare la sua stessa consistenza, allora dovremmo essere capaci di provare G. Ma ciò non è possibile. Pertanto, non esiste alcun insieme di assiomi che può provare la sua stessa consistenza.

La prova di Gödel ha ucciso la ricerca di un sistema matematico consistente e completo. Nel 1958 Nagel e Newmann scrissero che il significato dell’incompletezza non era stato ancora ben compreso.

Questa affermazione rimane valida ancora oggi.

Fonte: quantamagazine.org