Come funziona la prova di Gödel
Nel 1931, il logico austriaco Kurt Gödel decise probabilmente uno dei traguardi intellettuali più sorprendenti della storia.
I matematici dell'epoca cercavano solide basi per la matematica: una serie di fatti matematici di base, o assiomi, che erano entrambi coerenti – senza mai portare a contraddizioni – e completi, servendo da elementi costitutivi di tutte le verità matematiche.
Ma i scioccanti teoremi di incompletezza di Gödel, pubblicati a soli 25 anni, schiacciarono quel sogno. Dimostrò che qualsiasi serie di assiomi che potevi considerare come una possibile base per la matematica sarà inevitabilmente incompleta; ci saranno sempre fatti veri sui numeri che non possono essere dimostrati da quegli assiomi. Ha anche dimostrato che nessun gruppo di assiomi candidati può mai dimostrare la propria coerenza.
I suoi teoremi di incompletezza significano che non può esserci alcuna teoria matematica di tutto, nessuna unificazione di ciò che è provabile e ciò che è vero. Ciò che i matematici possono dimostrare dipende dalle loro ipotesi iniziali, non da alcuna verità fondamentale da cui scaturiscono tutte le risposte.
Negli 89 anni dalla scoperta di Gödel, i matematici si sono imbattuti proprio nel tipo di domande senza risposta che i suoi teoremi avevano predetto. Ad esempio, lo stesso Gödel ha contribuito a stabilire che l'ipotesi del continuum , che riguarda le dimensioni dell'infinito, è indecidibile, così come il problema di arresto, che chiede se un programma per computer alimentato con un input casuale funzionerà per sempre o alla fine si fermerà. Questioni indecidibili sono persino sorte in fisica , suggerendo che l'incompletezza di Gödelian affligge non solo la matematica, ma – in qualche modo mal compreso – la realtà.
Ecco una carrellata semplificata e informale di come Gödel abbia dimostrato i suoi teoremi.
Numerazione di Gödel
La principale manovra di Gödel era quella di mappare le affermazioni su un sistema di assiomi su affermazioni all'interno del sistema, cioè su affermazioni sui numeri. Questa mappatura consente a un sistema di assiomi di parlare in modo convincente di se stesso.
Il primo passo di questo processo è mappare ogni possibile affermazione matematica, o serie di affermazioni, su un numero univoco chiamato numero di Gödel.
La versione leggermente modificata dello schema di Gödel presentata da Ernest Nagel e James Newman nel loro libro del 1958, Gödel's Proof , inizia con 12 simboli elementari che fungono da vocabolario per esprimere un insieme di assiomi di base. Ad esempio, l'affermazione che qualcosa esiste può essere espressa dal simbolo ∃, mentre l'addizione è espressa da +. È importante sottolineare che il simbolo s , che indica "successore di", consente di specificare i numeri; ss 0, ad esempio, si riferisce a 2.
A questi dodici simboli vengono quindi assegnati i numeri Gödel da 1 a 12.
| Segno costante | Numero di Gödel | Significato abituale |
| ~ | 1 | non |
| ∨ | 2 | o |
| ⊃ | 3 | se poi… |
| ∃ | 4 | C'è un… |
| = | 5 | è uguale a |
| 0 | 6 | zero |
| S | 7 | il successore di |
| ( | 8 | segno di punteggiatura |
| ) | 9 | segno di punteggiatura |
| , | 10 | segno di punteggiatura |
| + | 11 | più |
| × | 12 | volte |
Successivamente, le lettere che rappresentano le variabili, che iniziano con x , ye z , si mappano su numeri primi maggiori di 12 (ovvero 13, 17, 19, …).
Quindi qualsiasi combinazione di questi simboli e variabili – cioè qualsiasi formula aritmetica o sequenza di formule che possono essere costruite – ottiene il proprio numero di Gödel.
Ad esempio, considera 0 = 0. I tre simboli della formula corrispondono ai numeri di Gödel 6, 5 e 6. Gödel deve cambiare questa sequenza di tre numeri in un unico numero univoco, un numero che nessun'altra sequenza di simboli genererà. Per fare questo, prende i primi tre numeri primi (2, 3 e 5), aumenta ciascuno al numero Gödel del simbolo nella stessa posizione nella sequenza e li moltiplica insieme. Quindi 0 = 0 diventa 2 6 × 3 5 × 5 6 o 243.000.000.
La mappatura funziona perché non ci saranno mai due formule con lo stesso numero di Gödel. I numeri di Gödel sono numeri interi e i numeri interi incidono solo sui numeri primi in un unico modo. Quindi l'unica fattorizzazione in primo piano di 243.000.000 è 2 6 × 3 5 × 5 6 , il che significa che c'è solo un modo possibile per decodificare il numero di Gödel: la formula 0 = 0.
Gödel quindi fece un ulteriore passo avanti. Una dimostrazione matematica consiste in una sequenza di formule. Quindi Gödel ha dato a ogni sequenza di formule un numero Gödel unico. In questo caso, inizia con l'elenco dei numeri primi come prima – 2, 3, 5 e così via. Quindi aumenta ogni numero primo al numero di Gödel della formula nella stessa posizione della sequenza (2 243.000.000 ×…, se 0 = 0 viene per primo, per esempio) e moltiplica tutto insieme.
Metamatematica aritmetica
Il vero vantaggio è che anche le affermazioni sulle formule aritmetiche, chiamate affermazioni metamatematiche, possono essere tradotte in formule con numeri di Gödel propri.
Innanzitutto considera la formula ~ (0 = 0), che significa "zero non è uguale a zero". Questa formula è chiaramente falsa. Tuttavia, ha un numero Gödel: 2 elevato alla potenza di 1 (il numero Gödel del simbolo ~), moltiplicato per 3 elevato alla potenza di 8 (il numero Gödel del simbolo "parentesi aperta") e così via , producendo 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Poiché siamo in grado di generare numeri di Gödel per tutte le formule, anche false, possiamo parlare sensatamente di queste formule parlando dei loro numeri di Gödel.
Considera l'affermazione, "Il primo simbolo della formula ~ (0 = 0) è una tilde". Questa (vera) affermazione metamatematica su ~ (0 = 0) si traduce in un'affermazione sul numero di Gödel della formula, ovvero che il suo primo esponente è 1, il numero di Gödel per una tilde. In altre parole, la nostra affermazione dice che 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 ha solo un singolo fattore di 2. Aveva ~ (0 = 0) iniziato con qualsiasi simbolo diverso da una tilde, il suo Gödel il numero avrebbe almeno due fattori di 2. Quindi, più precisamente, 2 è un fattore di 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , ma 2 2 non è un fattore.
Possiamo convertire l'ultima frase in una formula aritmetica precisa che possiamo scrivere * usando simboli elementari. Questa formula ha ovviamente un numero di Gödel, che potremmo calcolare mappando i suoi simboli su potenze di numeri primi.
Questo esempio, ha scritto Nagel e Newman, "esemplifica una visione molto generale e profonda che sta alla base della scoperta di Gödel: le proprietà tipografiche di lunghe catene di simboli possono essere discusse in modo indiretto ma perfettamente preciso parlando invece delle proprietà di prime fattorizzazioni di interi di grandi dimensioni. "
La conversione in simboli è anche possibile per l'affermazione metamatematica, "Esiste una sequenza di formule con il numero di Gödel x che dimostra la formula con il numero di Gödel k " – o, in breve, "La formula con il numero di Gödel k può essere dimostrata". La capacità di "aritmetizzare" questo tipo di affermazione ha preparato il terreno per il colpo di stato.
G stesso
L'intuizione aggiuntiva di Gödel era che poteva sostituire il numero Gödel di una formula nella formula stessa, senza problemi.
Per vedere come funziona la sostituzione, considera 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 numero intero grande che chiameremo semplicemente 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 chiameremo il numero Gödel di questa formula? Ci sono tre informazioni da comunicare: abbiamo iniziato con la formula che ha il numero Gödel m . In esso, abbiamo sostituito m con il simbolo y . E secondo lo schema di mappatura introdotto in precedenza, il simbolo y ha il numero Gödel 17. Quindi designiamo il numero di Gödel della nuova formula sub ( m , m , 17).
La sostituzione costituisce il punto cruciale della prova di Gödel.
Ha considerato un'affermazione metamatematica sulla falsariga di "La formula con il numero di Gödel sub ( y , y , 17) non può essere dimostrata." Ricordando la notazione che abbiamo appena appreso, la formula con il numero di Gödel sub ( y , y , 17) è quella ottenuta prendendo la formula con il numero di Gödel y (qualche variabile sconosciuta) e sostituendo questa variabile y ovunque c'è un simbolo il cui numero di Gödel è 17 (ovvero, ovunque ci sia una y ).
Le cose stanno diventando allucinanti, ma tuttavia la nostra affermazione metamatematica – "La formula con il numero di Gödel sub ( y , y , 17) non può essere provata" – si tradurrà sicuramente in una formula con un numero unico di Gödel. Chiamiamolo n .
Ora, un ultimo round 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 sub di Gödel ( 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 dall'aver preso la formula con il numero di Gödel n e sostituendo n ovunque ci sia un simbolo con il numero di Gödel 17. E G è esattamente questa formula! A causa dell'unicità della fattorizzazione primaria, ora vediamo che la formula di cui parla G non è altro che G stessa.
G afferma di per sé che non può essere provato.
Ma G può essere provato? In tal caso, ciò significherebbe che esiste una sequenza di formule che dimostra la formula con il numero di Gödel sub ( n , n , 17). Ma questo è l'opposto di G, che dice che non esiste tale prova. Affermazioni opposte, G e ~ G, non possono essere vere in un sistema assiomatico coerente. Quindi la verità di G deve essere indecidibile.
Tuttavia, sebbene G sia indecidibile, è chiaramente vero. G dice, "La formula con il numero sub di Gödel ( n , n , 17) non può essere dimostrata", ed è esattamente quello che abbiamo scoperto essere il caso! Dato che G è vero ma non definibile nel sistema assiomatico usato per costruirlo, quel sistema è incompleto.
Potresti pensare di poter sostenere un qualche assioma in più, usarlo per dimostrare G e risolvere il paradosso. Ma non puoi. Gödel ha dimostrato che il sistema assiomatico aumentato consentirà la costruzione di una nuova, vera formula Gʹ (secondo un modello simile a quello precedente) che non può essere dimostrata nel nuovo sistema aumentato. Nella ricerca di un sistema matematico completo, non puoi mai prendere la tua 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ò dimostrare 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 da questi assiomi che dimostra la formula che significa, meta-matematicamente, "Questo insieme di assiomi è coerente". Con il primo teorema, questo insieme di assiomi sarebbe quindi necessariamente incompleto.
Ma "L'insieme degli assiomi è incompleto" equivale a dire: "Esiste una formula vera che non può essere dimostrata". Questa affermazione equivale alla nostra formula G. E sappiamo che gli assiomi non possono provare G.
Quindi Gödel ha creato una prova per contraddizione: se un insieme di assiomi potesse dimostrare la propria coerenza, allora saremmo in grado di dimostrare G. Ma non possiamo. Pertanto, nessun insieme di assiomi può dimostrare la propria coerenza.
La prova di Gödel uccise la ricerca di un sistema matematico completo e coerente. Il significato di incompletezza "non è stato del tutto chiarito", ha scritto Nagel e Newman nel 1958. Rimane vero oggi.
* Per i curiosi, la frase recita: “Esiste un numero intero x tale che x moltiplicato per 2 è uguale a 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 e non esiste alcun numero intero x tale che x moltiplicato per 4 è uguale a 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 ”. La formula corrispondente è:
(∃ x ) ( x × ss 0 = sss … sss 0) ⋅ ~ (∃ x ) ( x × ssss 0 = sss … sss 0)
dove sss … sss 0 sta per 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 copie del simbolo successivo s. Il simbolo ⋅ significa "e", ed è una scorciatoia per un'espressione più lunga nel vocabolario fondamentale: p ⋅ q sta per ~ (~ p ∨ ~ q ).
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/how-godels-incompleteness-theorems-work-20200714/ in data Tue, 14 Jul 2020 14:00:54 +0000.