Nel 1931, il logico austriaco Kurt Gödel mise a segno probabilmente uno dei più sorprendenti successi intellettuali della storia.
I matematici dell’epoca cercavano un solido fondamento per la matematica: un insieme di fatti matematici di base, o assiomi, che fosse al tempo stesso coerente – senza mai portare a contraddizioni – e completo, servendo come elementi costitutivi di tutte le verità matematiche.
Ma gli scioccanti teoremi di incompletezza di Gödel, pubblicati quando aveva solo 25 anni, hanno infranto quel sogno. Egli dimostrò che qualsiasi insieme di assiomi che si possa porre come possibile fondamento della matematica sarà inevitabilmente incompleto; ci saranno sempre fatti veri sui numeri che non possono essere dimostrati da quegli assiomi. Ha anche dimostrato che nessun insieme di assiomi candidati può mai provare la propria coerenza.
I suoi teoremi di incompletezza significano che non ci può essere una teoria matematica del tutto, nessuna unificazione di ciò che è dimostrabile e ciò che è vero. Ciò che i matematici possono dimostrare dipende dalle loro ipotesi di partenza, non da una verità di base fondamentale da cui scaturiscono tutte le risposte.
Negli 89 anni trascorsi dalla scoperta di Gödel, i matematici si sono imbattuti proprio nel tipo di domande senza risposta che i suoi teoremi avevano previsto. Per esempio, Gödel stesso ha contribuito a stabilire che l’ipotesi del continuo, che riguarda le dimensioni dell’infinito, è indecidibile, così come il problema dell’arresto, che chiede se un programma per computer alimentato con un input casuale funzionerà per sempre o alla fine si fermerà. Questioni indecidibili sono sorte anche in fisica, suggerendo che l’incompletezza gödeliana non affligge solo la matematica, ma – in qualche modo incomprensibile – la realtà.
Qui c’è una sintesi semplificata e informale di come Gödel dimostrò i suoi teoremi.
Numerazione di Gödel
La principale manovra di Gödel fu di mappare le affermazioni su un sistema di assiomi su affermazioni all’interno del sistema – cioè, su affermazioni sui numeri. Questa mappatura permette a un sistema di assiomi di parlare in modo convincente di se stesso.
Il primo passo in questo processo è quello di mappare ogni possibile affermazione matematica, o serie di affermazioni, a un numero unico chiamato numero di Gödel.
La versione leggermente modificata dello schema di Gödel presentato da Ernest Nagel e James Newman nel loro libro del 1958, La prova di Gödel, inizia con 12 simboli elementari che servono come vocabolario per esprimere un insieme di assiomi di base. Per esempio, l’affermazione che qualcosa esiste può essere espressa dal simbolo ∃, mentre l’addizione è espressa da +. Importante, il simbolo s, che denota “successore di”, dà un modo di specificare i numeri; ss0, per esempio, si riferisce a 2.
A questi dodici simboli vengono poi assegnati i numeri di Gödel da 1 a 12.
| Segno costante | Numero di Gödel | Significato universale |
| ~ | 1 | non |
| ∨ | 2 | oppure |
| ⊃ | 3 | se…allora… |
| ∃ | 4 | c’è un… |
| = | 5 | equals |
| 0 | 6 | zero |
| s | 7 | il successore di |
| ( | 8 | punctuation mark |
| ) | 9 | punctuation mark |
| , | 10 | punctuation mark |
| + | 11 | plus |
| × | 12 | tempi |
Prossimo, le lettere che rappresentano le variabili, a partire da x, y e z, mappano su numeri primi maggiori di 12 (cioè 13, 17, 19, …).
Poi qualsiasi combinazione di questi simboli e variabili – cioè qualsiasi formula aritmetica o sequenza di formule che può essere costruita – ottiene il proprio numero di Gödel.
Per esempio, consideriamo 0 = 0. I tre simboli della formula corrispondono ai numeri di Gödel 6, 5 e 6. Gödel ha bisogno di cambiare questa sequenza di tre numeri in un singolo, unico numero – un numero che nessun’altra sequenza di simboli genererà. Per fare questo, prende i primi tre primi (2, 3 e 5), eleva ciascuno al numero di Gödel del simbolo nella stessa posizione nella sequenza e li moltiplica insieme. Così 0 = 0 diventa 26 × 35 × 56, o 243.000.000.
La mappatura funziona perché due formule non finiranno mai con lo stesso numero di Gödel. I numeri di Gödel sono numeri interi, e i numeri interi si fattorizzano in numeri primi solo in un unico modo. Quindi l’unica fattorizzazione di 243.000.000 è 26 × 35 × 56, il che significa che c’è solo un modo possibile per decodificare il numero di Gödel: la formula 0 = 0.
Gödel ha fatto un passo avanti. Una dimostrazione matematica consiste in una sequenza di formule. Così Gödel ha dato ad ogni sequenza di formule anche un numero di Gödel unico. In questo caso, inizia con la lista dei numeri primi come prima – 2, 3, 5 e così via. Poi eleva ogni primo al numero di Gödel della formula nella stessa posizione nella sequenza (2243.000.000 × …, se 0 = 0 viene prima, per esempio) e moltiplica tutto insieme.
Aritmetizzando la metamatematica
Il vero vantaggio è che anche le affermazioni sulle formule aritmetiche, chiamate affermazioni metamatematiche, possono essere tradotte in formule con numeri di Gödel propri.
Prima si consideri la formula ~(0 = 0), che significa “zero non è uguale a zero”. Questa formula è chiaramente falsa. Tuttavia, ha un numero di Gödel: 2 elevato alla potenza di 1 (il numero di Gödel del simbolo ~), moltiplicato per 3 elevato alla potenza di 8 (il numero di Gödel del simbolo “parentesi aperta”), e così via, ottenendo 2¹ × 38 × 56 × 75 × 116 × 139.
Perché possiamo generare numeri di Gödel per tutte le formule, anche quelle false, possiamo parlare sensatamente di queste formule parlando dei loro numeri di Gödel.
Considerate l’affermazione: “Il primo simbolo della formula ~(0 = 0) è una tilde”. Questa affermazione metamatematica (vera) su ~(0 = 0) si traduce in un’affermazione sul numero di Gödel della formula – cioè, che il suo primo esponente è 1, il numero di Gödel per una tilde. In altre parole, la nostra affermazione dice che 2¹ × 38 × 56 × 75 × 116 × 139 ha un solo fattore 2. Se ~(0 = 0) iniziasse con qualsiasi simbolo diverso da una tilde, il suo numero di Gödel avrebbe almeno due fattori di 2. Quindi, più precisamente, 2 è un fattore di 2¹ × 38 × 56 × 75 × 116 × 139, ma 22 non è un fattore.
Possiamo convertire l’ultima frase in una formula aritmetica precisa che possiamo scrivere* usando simboli elementari. Questa formula ha naturalmente un numero di Gödel, che potremmo calcolare mappando i suoi simboli su potenze di primi.
Questo esempio, scrivono Nagel e Newman, “esemplifica un’intuizione molto generale e profonda che sta al cuore della scoperta di Gödel: le proprietà tipografiche di lunghe catene di simboli possono essere parlate in modo indiretto ma perfettamente accurato parlando invece delle proprietà delle fattorizzazioni dei primi di grandi numeri interi.”
La conversione in simboli è possibile anche per l’affermazione metamatematica: “Esiste una qualche sequenza di formule con numero di Gödel x che dimostra la formula con numero di Gödel k” – o, in breve, “La formula con numero di Gödel k può essere dimostrata”. La capacità di “aritmetizzare” questo tipo di affermazioni ha posto le basi per il colpo di stato.
G Itself
L’intuizione extra di Gödel era che poteva sostituire il numero di Gödel di una formula nella formula stessa, portando a non finire i problemi.
Per vedere come funziona la sostituzione, consideriamo la formula (∃x)(x = sy). (Si legge: “Esiste una variabile x che è il successore di y”, o, in breve, “y ha un successore”). Come tutte le formule, ha un numero di Gödel – un intero grande che chiameremo m.
Ora introduciamo m nella formula al posto del simbolo y. Questo forma una nuova formula, (∃x)(x = sm), che significa: “m ha un successore”. Come possiamo chiamare il numero di Gödel di questa formula? Ci sono tre informazioni da trasmettere: Siamo partiti dalla formula che ha il numero di Gödel m. In essa, abbiamo sostituito m con il simbolo y. E secondo lo schema di mappatura introdotto prima, il simbolo y ha il numero di Gödel 17. Quindi designiamo il numero di Gödel della nuova formula sub(m, m, 17).
La sostituzione forma il nocciolo della prova di Gödel.
Ha considerato un’affermazione metamatematica sulla falsariga di “La formula con numero di Gödel sub(y, y, 17) non può essere dimostrata”. Ricordando la notazione che abbiamo appena imparato, la formula con numero di Gödel sub(y, y, 17) è quella che si ottiene prendendo la formula con numero di Gödel y (qualche variabile sconosciuta) e sostituendo questa variabile y ovunque ci sia un simbolo il cui numero di Gödel è 17 (cioè ovunque ci sia una y).
Le cose stanno diventando complicate, ma tuttavia, la nostra affermazione metamatematica – “La formula con numero di Gödel sub(y, y, 17) non può essere dimostrata” – si traduce sicuramente in una formula con un numero di Gödel unico. Chiamiamolo n.
Ora, un ultimo giro di sostituzione: Gödel crea una nuova formula sostituendo il numero n ovunque ci sia una y nella formula precedente. La sua nuova formula dice: “La formula con il numero di Gödel sub(n, n, 17) non può essere dimostrata”. Chiamiamo questa nuova formula G.
Naturalmente, G ha un numero di Gödel. Qual è il suo valore? Ecco, deve essere sub(n, n, 17). Per definizione, sub(n, n, 17) è il numero di Gödel della formula che risulta prendendo la formula con numero di Gödel n e sostituendo n ovunque ci sia un simbolo con numero di Gödel 17. E G è esattamente questa formula! A causa dell’unicità della fattorizzazione dei primi, ora vediamo che la formula di cui parla G non è altro che G stesso.
G afferma di se stesso che non può essere dimostrato.
Ma G può essere dimostrato? Se sì, ciò significherebbe che esiste una qualche sequenza di formule che dimostra la formula con numero di Gödel sub(n, n, 17). Ma questo è il contrario di G, che dice che tale prova non esiste. Affermazioni opposte, G e ~G, non possono essere entrambe vere in un sistema assiomatico coerente. Quindi la verità di G deve essere indecidibile.
Tuttavia, sebbene G sia indecidibile, è chiaramente vera. G dice: “La formula con il numero di Gödel sub(n, n, 17) non può essere dimostrata”, ed è esattamente quello che abbiamo scoperto essere il caso! Poiché G è vero ma indecidibile all’interno del sistema assiomatico usato per costruirlo, quel sistema è incompleto.
Si potrebbe pensare di poter semplicemente posporre qualche assioma extra, usarlo per provare G e risolvere il paradosso. Ma non si può. Gödel ha mostrato che il sistema assiomatico aumentato permetterà la costruzione di una nuova formula vera Gʹ (secondo uno schema simile a quello di prima) che non può essere dimostrata all’interno del nuovo sistema aumentato. Nella ricerca di un sistema matematico completo, non si può mai prendere la propria coda.
Nessuna prova di coerenza
Abbiamo imparato che se un insieme di assiomi è coerente, allora è incompleto. Questo è il primo teorema di incompletezza di Gödel. Il secondo – che nessun insieme di assiomi può provare la propria coerenza – segue facilmente.
Cosa significherebbe se un insieme di assiomi potesse provare che non produrrà mai una contraddizione? Significherebbe che esiste una sequenza di formule costruite a partire da questi assiomi che prova la formula che significa, metamatematicamente, “Questo insieme di assiomi è coerente”. Per il primo teorema, questo insieme di assiomi sarebbe allora necessariamente incompleto.
Ma “L’insieme degli assiomi è incompleto” è lo stesso che dire: “Esiste una formula vera che non può essere dimostrata”. Questa affermazione è equivalente alla nostra formula G. E noi sappiamo che gli assiomi non possono provare G.
Quindi Gödel ha creato una prova per contraddizione: Se un insieme di assiomi potesse provare la propria coerenza, allora saremmo in grado di provare G. Ma non possiamo. Pertanto, nessun insieme di assiomi può provare la propria consistenza.
La prova di Gödel ha ucciso la ricerca di un sistema matematico coerente e completo. Il significato di incompletezza “non è stato pienamente compreso”, hanno scritto Nagel e Newman nel 1958. Resta vero anche oggi.
*Per i curiosi, l’affermazione recita: “Esiste un numero intero x tale che x moltiplicato per 2 è uguale a 2¹ × 38 × 56 × 75 × 116 × 139, e non esiste alcun numero intero x tale che x moltiplicato per 4 è uguale a 2¹ × 38 × 56 × 75 × 116 × 139.” La formula corrispondente è:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × ssss0 = sss … sss0)
dove sss … sss0 sta per 2¹ × 38 × 56 × 75 × 116 × 139 copie del simbolo successore s. Il simbolo ⋅ significa “e”, ed è un’abbreviazione di un’espressione più lunga nel vocabolario fondamentale: p ⋅ q sta per ~(~p ∨ ~q).
Questo articolo è stato ristampato su Wired.com.