On a Theorem by Bezboruah & Shepherdson

Questo articolo esamina e difende il teorema di incompleteness di Bezboruah e Shepherdson contro le obiezioni di Kreisel, confrontandolo con l'estensione di Pudlák e fornendo una nuova dimostrazione basata su un'idea di Nielsen e Markov.

L'essenziale

Ecco una spiegazione del paper di Albert Visser, tradotta in un linguaggio semplice e arricchita da metafore per renderla accessibile a tutti.

Il Titolo: Una Rivalutazione di una "Vecchia" Teoria

Immagina di essere un architetto che ha scoperto un vecchio progetto di un edificio (la teoria di Bezboruah & Shepherdson del 1976) che era stato messo da parte perché considerato "difettoso" o "inutile" da un famoso critico (Kreisel). Il critico diceva: "Questo edificio è troppo piccolo e fragile per essere considerato un vero grattacielo; le sue fondamenta non reggono il peso della logica complessa".

Albert Visser, l'autore di questo articolo, dice: "Aspettate! Forse quel critico aveva torto. L'edificio è piccolo, sì, ma è ancora un edificio valido e la sua fragilità ci insegna qualcosa di importante sulla natura della verità matematica."

1. Il Grande Dibattito: Cosa significa "Consistenza"?

Il cuore della questione è il Secondo Teorema di Incompleteness di Gödel. In parole povere, Gödel ci ha detto che in qualsiasi sistema matematico abbastanza potente, ci saranno sempre delle verità che il sistema stesso non può dimostrare. Inoltre, il sistema non può mai dimostrare di non contenere contraddizioni (cioè di essere "consistente").

Il problema:
Nel 1976, Bezboruah e Shepherdson hanno provato che anche un sistema matematico molto debole (chiamato $PA^-$, che è come un sistema logico "in miniatura" che non sa nemmeno fare bene l'addizione commutativa) non può dimostrare la propria consistenza.

L'obiezione di Kreisel:
Il grande logico Georg Kreisel ha detto: "Ma questo risultato non ha senso! Per dire che un sistema è 'consistente', le sue regole devono essere abbastanza forti da capire cosa significa 'prova'. Il sistema $PA^-$ è troppo stupido per capire cosa sia una prova. Quindi, la frase che dice 'sono consistente' in quel sistema non significa davvero 'sono consistente', significa solo una cosa matematica astratta senza significato filosofico."

La risposta di Visser:
Visser ribatte: "Kreisel sta sbagliando. Anche se il sistema è debole, la frase 'sono consistente' ha lo stesso significato che avrebbe in un sistema forte. È come chiedere se un bambino che non sa ancora leggere possa dire 'non ho commesso errori'. Il fatto che non sappia leggere non cambia il fatto che stia affermando di non aver sbagliato. Se il sistema non può dimostrare la propria consistenza, è un risultato tecnico importante, indipendentemente da quanto sia 'debole' il sistema."

2. Due Modi Diversi di Arrivare alla Stessa Conclusione

Visser confronta due approcci per dimostrare che un sistema non può dimostrare la propria sicurezza:

• L'approccio moderno (Pudlák): È come usare un trapano elettrico. È potente, sofisticato e funziona su quasi tutti i sistemi matematici. Usa tecniche avanzate per mostrare che se un sistema prova la sua sicurezza, allora è già crollato (inconsistente).
• L'approccio di Bezboruah & Shepherdson: È come usare un coltellino svizzero o un trucco di magia. È molto specifico, funziona solo su sistemi piccolissimi e richiede costruzioni molto particolari.

Visser dice che questi due approcci sono come due strade diverse che portano allo stesso punto di vista, ma ci mostrano cose diverse lungo il cammino. Il metodo moderno è potente ma "pesante"; il metodo vecchio è fragile ma ci mostra esattamente come si può costruire un sistema che sembra sicuro ma contiene una trappola nascosta.

3. La Nuova Prova: Il Codice "Markov"

La parte più tecnica (e creativa) del paper è la nuova dimostrazione di Visser.
Immagina di dover scrivere una storia (una "prova" matematica) usando solo due tipi di mattoncini speciali.

• Il vecchio metodo (Bezboruah & Shepherdson): Usavano un codice complicato (la funzione $\beta$) per impilare i mattoncini.
• Il nuovo metodo di Visser (Codifica Markov): Usa una metafora matematica basata su matrici (tabelle di numeri) che assomigliano a un gioco di costruzioni.

L'analogia della costruzione:
Immagina di avere due tipi di mattoncini:

1. Un mattoncino che dice "Tutto è a posto" (l'assioma).
2. Un mattoncino che dice "C'è un errore" (la contraddizione).

Visser costruisce un "mondo" (un modello matematico) dove questi mattoncini sono disposti in una sequenza lunghissima.

• All'inizio della sequenza, ci sono milioni di mattoncini "Tutto è a posto".
• Alla fine, ci sono milioni di mattoncini "C'è un errore".

In un mondo "normale" (standard), questa sequenza non è una prova valida perché c'è un salto logico nel mezzo: non puoi passare dai "tutto è a posto" agli "errori" senza una regola che lo permetta.
Tuttavia, Visser crea un mondo "strano" (un modello non standard) dove, a causa di come sono misurati i mattoncini, quel salto sembra sparito. In quel mondo strano, la sequenza appare come una prova valida che porta all'errore.

Il risultato:
Questo dimostra che il sistema matematico debole ($PA^-$) non può vedere la differenza tra la sequenza valida e quella che sembra valida ma non lo è. Quindi, il sistema non può dimostrare di essere sicuro, perché nel suo "mondo" esiste una prova che dice il contrario.

4. Perché è importante?

Visser ci insegna tre cose fondamentali:

1. Non sottovalutare i sistemi piccoli: Anche i sistemi matematici più semplici hanno limiti profondi. Non serve essere "intelligenti" (forti) per fallire nel dimostrare la propria sicurezza; basta essere un sistema logico.
2. La creatività conta: Anche se un risultato è stato criticato decenni fa, rivederlo con nuovi occhi (come il codice Markov) può rivelare nuove verità.
3. La verità è relativa al contesto: A volte, ciò che sembra una prova valida in un mondo "strano" non lo è nel nostro, ma il sistema matematico non riesce a fare la distinzione.

In Sintesi

Albert Visser sta dicendo: "Non buttate via il vecchio lavoro di Bezboruah e Shepherdson solo perché un critico lo ha sminuito. È un gioiello nascosto. Ho preso la loro idea, l'ho rivestita con un nuovo codice matematico (Markov) e ho dimostrato che funziona ancora meglio di quanto pensassimo. Ci ricorda che la logica ha dei limiti fondamentali, anche quando è molto semplice."

È come se avessimo trovato un vecchio orologio rotto che un esperto aveva detto essere inutile. Visser lo ha riparato con un nuovo meccanismo e ha scoperto che, anche se non segna l'ora perfettamente come un orologio atomico, il suo ticchettio ci racconta una storia affascinante sul tempo stesso.

Sommario tecnico

Ecco una sintesi tecnica dettagliata del paper "On a Theorem by Bezboruah & Shepherdson" di Albert Visser, strutturata secondo le sezioni richieste.

1. Il Problema

Il lavoro si concentra sul risultato di incompleteness dimostrato da Bezboruah e Shepherdson nel 1976 ([BS76]), il quale afferma che la teoria debole $PA^-$ (la teoria della parte non negativa di un anello commutativo ordinato discretamente) non prova la propria consistenza (né quella di teorie estese molto deboli come $BeSh$).

Il problema centrale affrontato da Visser è duplice:

1. La critica di Kreisel: Georg Kreisel aveva obiettato che il risultato di Bezboruah & Shepherdson fosse privo di significato filosofico. La sua argomentazione era che, in teorie così deboli come $Q$ (Robinson Arithmetic) o $PA^-$, le formule standard che esprimono la consistenza non soddisfano le condizioni di Hilbert-Bernays o di Löb. Di conseguenza, secondo Kreisel, queste formule non esprimerebbero realmente il concetto di "consistenza", ma solo una proprietà algebrica, rendendo il teorema di incompleteness inapplicabile o banale in questo contesto.
2. L'oblio tecnico: Nonostante la sua importanza tecnica, il paper del 1976 è stato trascurato. Visser mira a dimostrare che l'obiezione di Kreisel non regge e a fornire una nuova dimostrazione del teorema basata su un codificamento di sequenze diverso da quello originale (basato sulla funzione $\beta$ di Gödel), utilizzando invece un codificamento basato sulla matematica dei gruppi liberi (Markov coding).

2. Metodologia

Visser adotta un approccio che combina analisi logica, teoria dei modelli e algebra.

• Analisi Logica e Critica Filosofica: Nella Sezione 2, Visser smonta l'obiezione di Kreisel. Sostiene che il significato di una formula (come quella della consistenza) non debba dipendere dalla capacità della teoria debole di provare le proprietà del predicato di dimostrabilità. Se accettiamo un'aritmetica vera come semantica di riferimento, la formula $con(Q)$ esprime la consistenza indipendentemente dal fatto che $Q$ possa provare le condizioni di Löb. Visser distingue tra il significato della formula e la capacità dimostrativa della teoria.
• Confronto Teorico: Nella Sezione 3, il paper confronta il risultato di Bezboruah & Shepherdson con il Teorema di Incompletezza di Gödel-Pudlák. Visser mostra che, sebbene entrambi portino allo stesso risultato per $Q$ (non provano la propria consistenza), le loro metodologie e i loro ambiti di applicazione sono radicalmente diversi.
• Costruzione di Modelli e Codificamento Matematico: Nella Sezione 4, Visser fornisce una nuova prova del teorema utilizzando il codificamento di Markov.
  • Sfrutta l'isomorfismo tra il monoide libero su due generatori e il sottogruppo $SL_2(\mathbb{N})$ delle matrici $2\times2$ a coefficienti interi non negativi con determinante 1.
  • Utilizza modelli non standard dell'aritmetica vera ($M$ e $N$, dove $N$ è un'estensione elementare finale di $M$).
  • Costruisce un modello $K$ (parte non negativa di un sottogruppo generato da prodotti di matrici) che soddisfa $PA^-$ e tutte le frasi universali vere, ma in cui una specifica sequenza codificata tramite matrici appare come una prova di contraddizione ($\bot$), pur non essendolo nel modello più grande.

3. Contributi Chiave

1. Rifutamento dell'obiezione di Kreisel: Visser dimostra che l'argomentazione di Kreisel non è valida. Anche se $PA^-$ non soddisfa le condizioni di Löb, la formula di consistenza mantiene il suo significato intensionale. Il fatto che una teoria debole non possa provare la propria consistenza rimane un risultato significativo e tecnicamente interessante.
2. Distinzione tra Risultati di Incompletezza: Il paper chiarisce che il teorema di Bezboruah & Shepherdson e il teorema di Gödel-Pudlák sono risultati distinti con sovrapposizioni parziali:
   • Il risultato di Pudlák si basa sull'interpretabilità di $S^1_2$ (una teoria per la computabilità in tempo polinomiale) all'interno di $Q$ su un "taglio" definibile. È molto generale e si applica a qualsiasi teoria che interpreti $Q + con(Q)$.
   • Il risultato di Bezboruah & Shepherdson è specifico per $PA^-$ e dipende fortemente dal sistema di codifica delle sequenze (inizialmente la funzione $\beta$). Non si generalizza facilmente a versioni basate sull'interpretabilità.
3. Nuova Dimostrazione con Codificamento di Markov: Visser presenta una prova alternativa del teorema di Bezboruah & Shepherdson che non utilizza la funzione $\beta$ di Gödel, ma il codificamento delle sequenze tramite matrici in $SL_2(\mathbb{R}^+)$. Questo approccio offre una nuova prospettiva tecnica e dimostra la robustezza del risultato indipendentemente dal metodo di codifica scelto.
4. Costruzione di Modelli Specifici: Viene costruita una struttura di modello $K$ che soddisfa $PA^-$ più tutte le frasi universali vere, contenente una "prova" di inconsistenza che è visibile nel modello ma che manca del punto critico di transizione (dove si passa dagli assiomi alle conclusioni) se vista dall'esterno.

4. Risultati Principali

• Teorema 3.5 (Versione di Bezboruah & Shepherdson): Se si usa la funzione $\beta$ per codificare le sequenze, $PA^-$ non prova la consistenza della teoria $BeSh$ (una teoria estremamente debole con assiomi $\bot \to \bot$ e regola Modus Ponens). Di conseguenza, nessuna sotto-teoria di $PA^-$ prova la consistenza di $BeSh$ o di sue estensioni (incluso $Q$ e $R$).
• Teorema 4.1 (Nuova Prova): Se si usa il codificamento di Markov (basato su $SL_2$) per codificare le sequenze, la teoria $PA^-$ (estesa con tutte le frasi universali vere) non prova la consistenza di $BeSh$.
• Risultato sulla Struttura dei Modelli: Il modello costruito da Visser (e quello originale di Bezboruah & Shepherdson) contiene una prova di $\bot$ che è una sequenza di tipo $\omega$ seguita da una sequenza di tipo $\omega$ inverso. Nel modello, questa sequenza è valida come prova perché il punto di transizione critico (dove la sequenza cambia da assiomi a conclusioni) non è "riconoscibile" o presente all'interno del modello stesso.
• Conferma della Validità Tecnica: Il paper conferma che la sfida tecnica di dimostrare l'incompletezza per teorie deboli come $Q$ è legittima e risolvibile, fornendo costruzioni di anelli ordinati discretamente con proprietà speciali.

5. Significato

Il lavoro di Visser ha un'importanza significativa per la logica matematica e la filosofia della matematica:

• Rivalutazione Storica: Ripristina la rilevanza del paper del 1976 di Bezboruah & Shepherdson, che era stato oscurato dalle critiche di Kreisel e dallo sviluppo successivo di Pudlák.
• Chiarezza Concettuale: Risolve un dibattito filosofico sul significato della consistenza in teorie deboli, affermando che l'incapacità di una teoria debole di provare la propria consistenza non è un artefatto di una definizione "sbagliata" della consistenza, ma una proprietà intrinseca della teoria.
• Innovazione Tecnica: L'introduzione del codificamento di Markov (tramite matrici $SL_2$) offre un nuovo strumento potente per lo studio della dimostrabilità e della consistenza in teorie aritmetiche deboli, mostrando che risultati simili possono essere ottenuti con diverse strutture algebriche.
• Didattica: Le costruzioni di modelli presentate hanno valore didattico, permettendo di visualizzare prove di inconsistenza in modelli di teorie deboli, cosa che non è possibile con le prove di inconsistenza standard in modelli di teorie più forti come $S^1_2$.

In sintesi, il paper di Visser non solo difende un risultato storico contro critiche filosofiche infondate, ma lo arricchisce con nuove prove tecniche, chiarendo la relazione tra diverse forme del Teorema di Incompletezza di Gödel.