Gödel, modelli e il prezzo dell’aritmetica

Quando si parla di assiomi, dimostrazioni e verità matematiche, è naturale immaginare un quadro rassicurante: fissiamo alcune regole di base, e tutto ciò che è vero dovrebbe, in linea di principio, poter essere dimostrato. La scoperta di Gödel ha incrinato definitivamente questa immagine, ma spesso se ne fraintende il motivo profondo. Non si tratta di un difetto tecnico né di una stranezza artificiale: la frattura nasce dal modo in cui l’infinito entra nell’aritmetica e dal rapporto strutturale tra sintassi e semantica.

Segni e significati: sintassi e semantica

Un sistema formale è, prima di tutto, un sistema di segni. La sintassi riguarda esclusivamente la manipolazione meccanica di simboli: formule, assiomi, regole di inferenza. In questo ambito, una dimostrazione è una sequenza finita di formule, ciascuna ottenuta secondo regole precise. Tutto è locale, discreto, controllabile.

La semantica, invece, assegna significato a quei segni. Dire che una formula è vera significa dire che essa è soddisfatta in un certo modello. Un modello può essere pensato intuitivamente come un “mondo possibile” in cui i simboli del linguaggio vengono interpretati: un dominio di oggetti, un’interpretazione di “0”, del successore, dell’addizione, ecc., tale che gli assiomi risultino veri.

Un punto decisivo è questo: gli assiomi non descrivono un solo mondo, ma una classe di mondi compatibili con essi.

Che cos’è un modello

Un modello non è una copia fisica dei numeri, ma una struttura che si comporta come richiesto dagli assiomi. Se gli assiomi dicono che ogni numero ha un successore, un modello è qualunque universo in cui esiste un’operazione che soddisfa quella proprietà. Nulla, negli assiomi del primo ordine, garantisce che quel mondo sia esattamente quello dei numeri naturali come li intendiamo intuitivamente.

Per l’aritmetica di Peano in logica del primo ordine (PA), questo ha una conseguenza cruciale: esiste il modello standard ℕ, ma esistono anche modelli non standard, che contengono “numeri” aggiuntivi, più grandi di ogni numero standard, pur soddisfacendo tutti gli assiomi.

Deducibilità e verità nei modelli

La deduzione formale è governata da una regola semplice ma severa:

Una formula è dimostrabile da un sistema di assiomi se e solo se è vera in tutti i modelli che soddisfano quegli assiomi.

Formalmente:

Γ ⊢ 𝜑 se e solo se Γ ⊨ 𝜑

Dove Γ è un sistema di assiomi e 𝜑 è una formula scritta rispettando le regole di formazione.

⊢ indica deducibilità o dimostrabilità

⊨ indica verità

Questo principio è la completezza della logica del primo ordine. Ma combinato con la pluralità dei modelli produce un effetto inatteso: una formula può essere vera nel modello standard ℕ, ma falsa in qualche modello non standard. In tal caso, non potrà mai essere dimostrata, perché la dimostrazione deve valere “una volta per tutte”, indipendentemente da quale mondo compatibile si stia considerando.

Dove avviene la rottura

La rottura non avviene nella sintassi, che resta finita e ben definita. Avviene nel passaggio dalla sintassi alla semantica:

la sintassi può parlare solo di ciò che è finitamente costruibile;
la semantica coinvolge strutture infinite;

i modelli non standard sfruttano questa distanza.

PA non riesce a distinguere tra “finito davvero” e “finito secondo il modello”. Questo è il punto esatto in cui vero non implica dimostrabile.

Realzione con il problema della fermata

Il problema della fermata di Turing afferma che non esiste un algoritmo che decida, per ogni programma e input, se l’esecuzione terminerà. Anche qui il motivo profondo non è tecnico, ma strutturale.

Dire che un programma non termina equivale a dire:

“per ogni numero finito di passi, ce n’è uno successivo”.

È una proprietà globale, infinita, non verificabile localmente. Allo stesso modo, dire che una formula è vera in ℕ può richiedere un controllo su tutti i numeri naturali.

Gödel e Turing mostrano due facce dello stesso limite:

Gödel: non tutte le verità aritmetiche sono dimostrabili;

Turing: non tutti i comportamenti infiniti sono decidibili.

In entrambi i casi, l’infinito rompe la possibilità di una procedura totale.

L’infinito: necessario e distruttivo

L’aritmetica non può fare a meno dell’infinito. Fissare un massimo per i numeri naturali distruggerebbe il successore, l’induzione e la generalità delle operazioni.

Proprio questo infinito rende impossibile una completa cattura sintattica della verità. L’aritmetica esiste solo accettando l’infinito, e proprio per questo non può essere completamente addomesticata da un sistema formale finito.

Gödel non ha scoperto un difetto dell’aritmetica, ma il suo prezzo. Ogni sistema assiomatico sufficientemente ricco da parlare dell’infinito è condannato a descrivere più mondi di quanti ne possa controllare. La verità vive in un modello; la dimostrazione deve valere in tutti. È in questo scarto, inevitabile e strutturale, che nasce l’incompletezza.

Il secondo ordine: unicità del mondo e nuovo prezzo da pagare

Di fronte alla proliferazione dei modelli non standard, nasce un’esigenza naturale: se il problema è che gli assiomi del primo ordine non riescono a fissare un solo mondo aritmetico, perché non rafforzare il linguaggio? È questa la motivazione profonda che spinge a riformulare l’aritmetica di Peano nella logica del secondo ordine.

Nel primo ordine le formule possono quantificare solo su individui: numeri, elementi del dominio. Nel secondo ordine il linguaggio compie un salto di livello: le formule possono quantificare anche su insiemi di numeri, ovvero su proprietà, relazioni, predicati. Non si parla più solo degli oggetti, ma anche di tutte le proprietà possibili degli oggetti. È un vero e proprio meta-livello interno al linguaggio.

Questo cambia radicalmente il principio di induzione. In PA del primo ordine, l’induzione vale per ogni formula del linguaggio; in PA del secondo ordine, l’induzione vale per ogni sottoinsieme di ℕ. Intuitivamente, non si dice più: “ogni proprietà esprimibile vale per tutti i numeri”, ma: “ogni proprietà, punto e basta, vale per tutti i numeri”. È questa mossa che elimina i modelli non standard. Il sistema diventa categorico: esiste un solo modello, quello standard. Finalmente, il linguaggio sembra parlare esattamente del mondo che avevamo in mente.

Vittoria semantica dal costo altissimo.

Quantificare su tutti i sottoinsiemi di ℕ significa introdurre una totalità immensamente più grande, non numerabile. Le formule del secondo ordine non possono più essere enumerate in modo efficace, e soprattutto non esiste un sistema di regole di inferenza che catturi tutte le verità semantiche del linguaggio. La logica del secondo ordine, con la sua semantica standard, non è completa: esistono formule vere nell’unico modello, ma non derivabili da alcun sistema formale finito o ricorsivo.

L’incompletezza qui è di natura diversa da quella di Gödel. Nel primo ordine, l’incompletezza nasce perché il sistema ha troppi modelli; nel secondo ordine nasce perché il sistema ha troppa semantica. Non è più la verità aritmetica a sfuggire alla dimostrazione, ma l’intero apparato deduttivo a non poter essere chiuso. Potremmo dire che il secondo ordine produce una incompletezza strutturale del linguaggio stesso: non tutto ciò che è vero può essere neppure, in linea di principio, formalizzato come teorema.

In questo senso, il secondo ordine risolve il problema dell’unicità del mondo sacrificando la controllabilità della dimostrazione. Il primo ordine, al contrario, conserva una sintassi governabile ma accetta una pluralità di mondi. Non esiste una terza via: o si controllano le regole, o si controlla il significato. L’infinito, ancora una volta, non concede sconti.

Breve approfondimento

Nel primo ordine l’induzione dice:

“ogni proprietà che riesco a dire vale per tutti i numeri”.

Nel secondo ordine l’induzione dice:

“ogni proprietà che esiste, anche se non la so dire, vale per tutti i numeri”.

È esattamente questa differenza — dire vs esistere — che elimina i modelli non standard ma rende impossibile una teoria completa delle dimostrazioni.

Qui passa la linea di frattura tra controllo sintattico e controllo semantico.

Vediamo perché nel secondo ordine avviene l’eliminazione dei modelli non standard

In un modello non standard di PA₁ esistono elementi che:

• soddisfano tutte le equazioni aritmetiche,
• hanno un predecessore, un successore, ecc.,
• ma non sono ottenibili partendo da 0 e iterando finitamente il successore.

Dal nostro punto di vista sono “numeri infiniti”, ma dentro il modello sono normali elementi del dominio.

Il primo ordine non riesce a escluderli perché:

• non può esprimere “x è ottenibile da 0 con un numero finito di successori”,
• “finito” è una nozione globale, non catturabile con una formula di primo ordine.

L’assioma di induzione del secondo ordine dice:

Qualunque insieme che contiene 0 ed è chiuso rispetto al successore contiene tutti i numeri.

Ora chiediamoci:
qual è l’insieme più piccolo con queste due proprietà?

Intuitivamente è:

l’insieme dei numeri ottenibili partendo da 0 e applicando il successore un numero finito di volte.

Nel modello standard questo insieme è ℕ stesso.
Nel primo ordine non possiamo dire che questo è l’insieme minimo; nel secondo ordine possiamo quantificare direttamente su quell’insieme.

Consideriamo la proprietà:

“x è raggiungibile da 0 con un numero finito di applicazioni del successore”.

Questa proprietà:

• esiste semanticamente,
• ma non è definibile nel linguaggio del primo ordine.

Nel secondo ordine, però, possiamo fare questo passo decisivo:

quantificare su tutti gli insiemi, inclusa questa proprietà.

Chiamiamo $X$ proprio quell’insieme.