💻 computer science

The calculus of neo-Peircean relations

Il documento dimostra che è possibile ottenere un'assiomatizzazione completa del calcolo delle relazioni, superando i noti teoremi di impossibilità, passando da una sintassi cartesiana a una diagrammatica monoidale che definisce un "calcolo delle relazioni neo-peirciano" espressivo quanto la logica del primo ordine.

Autori originali: Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, Pawel Sobocinski

Pubblicato 2026-04-10

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, Pawel Sobocinski

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di voler spiegare come funziona il mondo usando solo disegni, senza bisogno di parole complicate o formule matematiche astratte. È esattamente ciò che fanno gli autori di questo articolo: Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon e Paweł Sobociński.

Hanno creato un nuovo modo di fare logica, che chiamano "Calcolo delle Relazioni Neo-Peircean". Per capirlo, dobbiamo fare un piccolo viaggio nel tempo e usare qualche metafora.

1. Il Problema: La Logica è diventata troppo "pesante"

Tanto tempo fa (fine dell'800), un genio di nome Charles Sanders Peirce (e prima di lui De Morgan) aveva inventato un modo per trattare le relazioni (come "è padre di", "è più grande di") come se fossero numeri, usando l'algebra. Era bello, semplice e non aveva bisogno di quantificatori complicati (come "per ogni x" o "esiste un y").

Poi, però, è arrivata la logica moderna (quella che usiamo oggi nei computer e nella filosofia). È diventata potentissima, ma anche molto complessa. Per gestire le variabili (le "scatole" dove mettiamo i nomi delle cose), la logica moderna ha bisogno di regole pesanti per non fare confusione (come evitare che una variabile "catturi" un'altra per sbaglio).

Il vecchio metodo di Peirce è stato dimenticato perché sembrava troppo semplice: non riusciva a fare tutto quello che fa la logica moderna. Inoltre, si pensava che non si potesse mai creare una lista finita di regole (assiomi) per farlo funzionare perfettamente.

2. La Soluzione: I "Disegni" invece delle "Parole"

Gli autori dicono: "E se smettessimo di scrivere formule e iniziassimo a disegnare?".

Immagina la logica non come una serie di equazioni scritte su una lavagna, ma come un circuito elettrico o un foglio di carta con dei fili.

I fili rappresentano le informazioni che viaggiano.
I blocchi (i disegni) rappresentano le operazioni (come "e", "o", "non", "esiste").

Invece di scrivere ∀x (P(x) → Q(x)), disegni un filo che entra in una scatola, si divide, passa attraverso un filtro e ne esce un altro.

3. La Magia: Due Mondi che si Incontrano

Il trucco geniale di questo lavoro è unire due mondi che sembravano nemici:

Il Mondo Bianco (Cartesiano): È il mondo delle cose che puoi copiare e buttare via facilmente. Come quando scrivi una nota su un foglio: puoi fotocopiarla (copiare) o stracciarla (buttare via). Questo mondo gestisce le cose "esistenti" (come "esiste un x tale che...").
Il Mondo Nero (Lineare): È il mondo delle cose che non puoi copiare, ma solo trasformare. Come in meccanica quantistica: non puoi clonare un atomo, puoi solo spostarlo o cambiarlo. Questo mondo gestisce le cose "universali" (come "per ogni x...").

Fino ad ora, questi due mondi erano separati. Gli autori hanno creato un "ponte" (chiamato Bicategoria di Primo Ordine) che permette ai fili bianchi e neri di mescolarsi.

Metafora: Immagina di avere due tipi di plastica: una che si può fondere e copiare (bianca) e una che è rigida e unica (nera). Il loro calcolo è come un nuovo tipo di stampante 3D che sa lavorare con entrambe contemporaneamente, creando oggetti complessi senza mai perdere pezzi.

4. Perché è importante? (Il "Tao della Logica")

Prima di questo lavoro, si pensava che non si potesse avere una logica completa (che copra tutto) e semplice (senza regole infinite) allo stesso tempo.
Gli autori hanno dimostrato che sbagliavamo.

Usando i loro disegni:

È completo: Puoi esprimere qualsiasi cosa si possa dire nella logica moderna (incluso "per ogni" ed "esiste").
È semplice: Hai una lista finita di regole (assiomi) per trasformare un disegno nell'altro. Se due disegni sono uguali secondo queste regole, allora significano la stessa cosa nel mondo reale.
È visivo: Non devi più preoccuparti di "variabili vincolate" o "sostituzioni". Se i fili si collegano, la logica funziona.

5. Un esempio pratico: Le "Scatole Vuote"

C'è un dettaglio curioso. Nella logica classica, si dice che un "mondo" (o dominio) non può essere vuoto (deve esserci almeno una cosa). Se provi a fare logica su un mondo vuoto, tutto crolla.
Nel loro sistema, i disegni gestiscono i "mondi vuoti" in modo naturale.

Metafora: Immagina di avere un contenitore. Nella logica classica, se il contenitore è vuoto, non puoi fare nulla. Nel loro sistema, il contenitore vuoto è semplicemente un disegno che non ha fili che entrano o escono, ed è perfettamente valido. Questo permette di unificare la logica "con le cose" e la logica "senza cose" (la logica proposizionale) in un unico sistema coerente.

In sintesi

Questo articolo è come se gli autori avessero preso il vecchio e potente linguaggio di Peirce, gli avessero dato un nuovo vestito fatto di diagrammi colorati (bianchi e neri), e avessero scoperto che, grazie a questa nuova forma, la logica diventa:

Più potente (fa tutto quello che fa la logica moderna).
Più bella (si vede, non si deve solo leggere).
Più semplice (regole finite e chiare).

È un ritorno alle origini (Peirce amava i disegni) ma con la tecnologia matematica più avanzata di oggi (la teoria delle categorie). È come se avessero scoperto che la logica non è un libro di regole noioso, ma un'arte di collegare i fili del pensiero.

1. Il Problema

Il Calcolo delle Relazioni (CR), introdotto da De Morgan e Peirce nel XIX secolo come estensione dell'algebra delle classi di Boole, è stato a lungo dimenticato a causa dell'ascesa della logica del primo ordine (FOL). Sebbene il CR offrisse un linguaggio rigoroso senza quantificatori, basato solo sulla sostituzione di uguali con uguali, presentava due limiti fondamentali:

Mancanza di espressività: È strettamente meno espressivo della FOL (non può esprimere negazioni o quantificatori universali in modo completo).
Impossibilità di assiomatizzazione completa: Tarski (1941) chiese se il CR ammettesse una completa assiomatizzazione. Teoremi "no-go" successivi (es. Mon, 1964) dimostrarono che non esiste un'assiomatizzazione finita completa per il calcolo delle relazioni o per molti dei suoi frammenti.

Il problema centrale è quindi: è possibile ottenere un sistema assiomatico completo per le relazioni che sia anche completo rispetto alla logica del primo ordine, mantenendo la semplicità sintattica (senza quantificatori) del calcolo delle relazioni?

2. Metodologia

Gli autori adottano un approccio radicale basato sulla semantica categoriale e sulla sintassi diagrammatica (string diagrams), abbandonando la sintassi cartesiana tradizionale (basata su termini e alberi) a favore di una sintassi monoidale.

Transizione dalla Sintassi Cartesiana a quella Monoidale: Invece di trattare le relazioni come sottoinsiemi di $X \times Y$ , le relazioni sono viste come frecce in categorie monoidali. Questo permette di gestire esplicitamente operazioni come la copia e il discard (eliminazione) delle variabili, che nella sintassi tradizionale sono implicite.
Integrazione di Strutture Categoricali: Il lavoro combina tre strutture algebriche ben note:
1. Bicategorie Cartesiane: Modellano la parte esistenziale-congiuntiva della logica (quantificatori esistenziali e congiunzioni).
2. Bicategorie Cocartesiane: Modellano la parte universale-disgiuntiva (quantificatori universali e disgiunzioni), ottenute come "negazione fotografica" delle cartesiane.
3. Bicategorie Lineari: Introdotte da Cockett e Seely, permettono di gestire due composizioni diverse ( $\circ$ e $\bullet$ ) che distribuiscono l'una sull'altra in modo lineare, riflettendo la dualità di De Morgan.
Sintesi in "First-Order Bicategories" (fo-bicategories): Gli autori definiscono una nuova struttura, le fo-bicategorie, che unifica le precedenti. In queste strutture, le strutture (co)monoidali bianche e nere sono legate da aggiunte lineari e soddisfano leggi di Frobenius lineari.

3. Contributi Chiave

A. Il Calcolo delle Relazioni Neo-Peircean (NPR)

Gli introducono il NPR ( $\Sigma$ ), un calcolo basato su string diagrams che:

È libero da quantificatori e variabili.
Utilizza una sintassi diagrammatica dove i termini sono rappresentati graficamente.
Tratta termini e predicati come entità unificate, non separate.
È altrettanto espressivo della FOL, superando i limiti del CR classico.

B. Assiomatizzazione Completa

Il contributo principale è la dimostrazione che le leggi delle fo-bicategorie forniscono un'assiomatizzazione completa per la FOL.

Teorema 3.5: Due diagrammi $c$ e $d$ sono semanticamente equivalenti (o in inclusione) se e solo se sono provabilmente uguali (o in inclusione) tramite le leggi delle fo-bicategorie.
Questo risolve negativamente i teoremi "no-go" di Tarski e altri: l'impossibilità di un'assiomatizzazione completa valeva per la sintassi cartesiana tradizionale; passando alla sintassi monoidale/diagrammatica, la completezza è raggiungibile.

C. Semantica Funzionale e Modelli

Viene definita una semantica funzionale dove i modelli sono morfismi di fo-bicategorie verso la categoria delle relazioni ($Rel$).
Gestione dei Modelli Vuoti: A differenza della FOL classica che richiede domini non vuoti, il NPR permette modelli con dominio vuoto. Questo è cruciale: i modelli vuoti corrispondono esattamente alla logica proposizionale, permettendo una generalizzazione del teorema di completezza di Gödel.

D. Codifiche e Traduzioni

Il paper dimostra come il NPR possa codificare:

Il Calcolo delle Relazioni Classico (CR).
La Logica dei Funtori Predicativi (PFL) di Quine.
I Grafici Esistenziali (EG) di Peirce (sistema $\beta$ ).
In tutti i casi, il NPR funge da linguaggio unificante che preserva la semantica.

4. Risultati Principali

Completezza: È stato provato che le leggi delle fo-bicategorie sono sufficienti per derivare tutte le verità della logica del primo ordine. La prova è un adattamento diagrammatico della dimostrazione di Henkin del teorema di completezza di Gödel.
Superamento dei Limiti di Tarski: Il paper mostra che i limiti di assiomatizzabilità del CR derivano dalla scelta sintattica (cartesiana), non dall'oggetto matematico (le relazioni) stesso.
Unificazione Algebrica: Le strutture algebriche necessarie (cartesiane, cocartesiane, lineari) sono state fuse in un'unica teoria coerente (fo-bicategorie), che può essere visualizzata attraverso il "Tao della Logica" (un diagramma che riassume le dualità e le aggiunte).
Dimostrazione di Peirce: Il lavoro fornisce fondamenti categoriale solidi alle intuizioni di Peirce, in particolare riguardo alla distribuzione lineare e alle aggiunte lineari, che Peirce aveva intuito ma non formalizzato in termini moderni.

5. Significato e Impatto

Per la Logica: Offre una nuova prospettiva sulla FOL, mostrandola come un sistema puramente equazionale basato su diagrammi, eliminando la necessità di gestire la complessità delle variabili vincolate, degli scope e delle sostituzioni.
Per l'Informatica Teorica:
- Assistenti di Prova: La natura puramente equazionale e diagrammatica rende il NPR ideale per l'implementazione in assistenti di prova automatizzati, evitando problemi di gestione delle variabili.
- Semantica dei Linguaggi di Programmazione: Fornisce un framework rigoroso per la semantica di linguaggi basati su relazioni e database.
- Fondamenti Quantistici: Le strutture di bicategorie e diagrammi a stringa sono già utilizzate nell'informatica quantistica; questo lavoro estende tali tecniche alla logica classica completa.
Storico: Ricollega la logica moderna alle radici algebriche di Peirce e Boole, dimostrando che le intuizioni di Peirce sui grafici esistenziali e le relazioni erano in anticipo sui tempi e trovano oggi la loro formalizzazione naturale nella teoria delle categorie.

In sintesi, il paper dimostra che passando da una sintassi basata su termini a una basata su diagrammi (string diagrams) e utilizzando la teoria delle bicategorie, è possibile ottenere un calcolo delle relazioni che è completo, assiomaticamente trattabile e equivalente alla logica del primo ordine, risolvendo un problema aperto da oltre 80 anni.