💻 computer science

The calculus of neo-Peircean relations

Cet article démontre qu'en passant d'une syntaxe cartésienne à une syntaxe diagrammatique monoidale, il est possible d'obtenir une axiomatisation complète du calcul des relations, contournant ainsi les théorèmes d'impossibilité grâce à un cadre plus expressif nommé « calcul des relations néo-peircéennes » qui équivaut à la logique du premier ordre.

Auteurs originaux : Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, Pawel Sobocinski

Publié 2026-04-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon, Pawel Sobocinski

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Le Titre : La Calcul des Relations "Néo-Peircean"

Imaginez que la logique (la façon dont nous raisonnons) est comme une boîte à outils. Pendant plus d'un siècle, les mathématiciens ont utilisé une boîte à outils un peu vieille et encombrante appelée "logique du premier ordre". Elle fonctionne très bien, mais elle est lourde à transporter : elle utilise des variables (comme $x$ , $y$ ), des quantificateurs ("pour tout", "il existe") et des règles de substitution très strictes qui ressemblent à des manuels d'instructions ennuyeux.

Dans les années 1800, un génie nommé Charles Sanders Peirce a essayé de créer une boîte à outils plus simple, basée sur des relations (des liens entre les choses) plutôt que sur des phrases complètes. Malheureusement, sa boîte a été oubliée car elle semblait trop limitée.

Aujourd'hui, les auteurs de ce papier (Filippo Bonchi et ses collègues) disent : "Attendez ! On peut récupérer la boîte de Peirce, mais en lui donnant des super-pouvoirs modernes." Ils ont créé le Calcul des Relations Néo-Peircean.

L'Analogie Principale : Les Diagrammes vs Les Mots

Pour comprendre leur idée, imaginez deux façons de dessiner un plan de maison :

L'ancienne méthode (Logique classique) : C'est comme écrire une liste de phrases : "La cuisine est à gauche du salon. La chambre est au-dessus de la cuisine." C'est précis, mais si vous voulez changer quelque chose, vous devez réécrire toute la phrase et faire attention à ne pas effacer le mauvais mot. C'est ce qu'on appelle la syntaxe "cartésienne" (basée sur des arbres et des mots).
La nouvelle méthode (Ce papier) : C'est comme dessiner un plan architectural ou un circuit électrique. Vous avez des fils, des boîtes et des connexions. Vous ne dites pas "la cuisine est ici", vous la dessinez ici. Si vous voulez déplacer la cuisine, vous glissez simplement le dessin. C'est ce qu'on appelle la syntaxe "diagrammatique" ou "monoidale".

Le grand saut : Les auteurs disent que si on arrête d'écrire des phrases et qu'on commence à dessiner des diagrammes, on peut tout faire aussi bien que la logique classique, mais avec beaucoup plus de facilité et de clarté.

Les Deux "Couleurs" Magiques

Dans leur nouveau système, tout est coloré. Imaginez deux types de blocs de construction :

Les blocs Blancs (Le monde "Blanc") : Ils représentent ce qui est positif et existant.
- Analogie : C'est comme dire "Il y a un chat". Si je dis "Il y a un chat ET un chien", je combine deux blocs blancs. C'est la logique des "et" et des "il existe".
Les blocs Noirs (Le monde "Noir") : Ils représentent ce qui est négatif ou universel.
- Analogie : C'est comme dire "Il n'y a PAS de dragon" ou "POUR TOUS les chats, ils ont des moustaches". C'est la logique des "ou", des "non" et des "pour tout".

Le génie de ce papier, c'est qu'ils ont trouvé la règle magique pour faire jouer les blocs blancs et les blocs noirs ensemble. C'est comme si on avait deux langages différents (le blanc et le noir) et qu'ils ont inventé un dictionnaire parfait pour les traduire l'un en l'autre sans perdre d'information.

Pourquoi est-ce une révolution ?

Avant ce papier, il y avait un problème majeur avec les anciennes méthodes de Peirce : on ne pouvait pas prouver toutes les vérités logiques avec un ensemble fini de règles. C'était comme essayer de résoudre un puzzle avec des pièces manquantes.

Les auteurs disent : "Non, ce n'est pas que les pièces manquaient, c'est que vous regardiez le puzzle de travers !".

Complétude : Avec leur nouveau système de diagrammes (blancs et noirs), ils ont prouvé qu'on peut déduire toutes les vérités de la logique moderne en utilisant seulement des règles de dessin simples. C'est comme si on avait trouvé la formule parfaite pour assembler n'importe quel puzzle logique.
Pas de variables : Plus besoin de se soucier de "x" ou "y". Dans un diagramme, si deux fils se touchent, c'est qu'ils sont liés. Si un fil est coupé, c'est qu'il n'y a pas de lien. C'est beaucoup plus intuitif.
Les modèles vides : En logique classique, on interdit souvent de penser à un monde où "rien n'existe" (un ensemble vide). Dans leur système, c'est permis et cela correspond à la logique des phrases simples (propositionnelle). C'est comme accepter qu'une pièce de la maison puisse être vide, ce qui rend le système plus flexible.

L'Analogie de la "Tao de la Logique"

Les auteurs utilisent un dessin qu'ils appellent "Le Tao de la Logique". Imaginez un diagramme de flux où les blocs blancs et noirs se transforment l'un en l'autre comme des yin et yang.

Un bloc blanc qui se retourne devient noir.
Un bloc noir qui se retourne devient blanc.
Ils peuvent glisser les uns sur les autres (comme des pièces de Lego) selon des règles précises.

C'est cette danse entre le blanc et le noir qui permet de capturer toute la complexité de la pensée humaine (la logique du premier ordre) sans avoir besoin de la lourdeur des phrases mathématiques traditionnelles.

En Résumé

Ce papier est une célébration de la pensée de Peirce, mise à jour avec les outils modernes de l'informatique et des mathématiques (la théorie des catégories).

Le problème : La logique traditionnelle est lourde et difficile à manipuler.
La solution : Remplacer les mots par des dessins (diagrammes) qui utilisent deux couleurs (blanc et noir) pour représenter les idées positives et négatives.
Le résultat : Un système complet, élégant et puissant qui permet de prouver n'importe quelle vérité logique simplement en "repliant" et en "reconnectant" des fils sur un papier.

C'est comme passer d'une écriture à la plume, lettre par lettre, à un langage de programmation visuelle où l'on assemble des blocs pour construire des idées complexes, le tout avec une rigueur mathématique absolue.

1. Le Problème : Les Limites du Calcul des Relations Classique

L'article s'attaque à un problème fondamental de la logique et de l'algèbre relationnelle : l'impossibilité d'obtenir une axiomatisation complète et finie pour le calcul des relations (CR) tel qu'initialement formulé par De Morgan et Peirce, puis étudié par Tarski.

Contexte historique : Le CR est une extension algébrique de l'algèbre de Boole, conçue pour manipuler des relations binaires sans utiliser de quantificateurs explicites. Cependant, il est strictement moins expressif que la logique du premier ordre (FOL) et ne possède pas d'axiomatisation complète (théorèmes "no-go" de Tarski, Monk, etc.).
Le dilemme : Pour obtenir la complétude de la logique du premier ordre, il faut généralement introduire des quantificateurs et des variables, ce qui complexifie la syntaxe (gestion des liaisons, substitution évitant la capture) et rend les preuves difficiles à automatiser.
L'objectif : Trouver un système qui conserve les avantages du CR (syntaxe sans quantificateurs, preuves purement équationnelles) tout en atteignant l'expressivité de la FOL et en admettant une axiomatisation complète.

2. Méthodologie : Du Syntaxe Cartésienne à la Syntaxe Diagrammatique

Les auteurs proposent un changement de paradigme radical : passer d'une syntaxe basée sur les termes (arborescente, cartésienne) à une syntaxe diagrammatique (monoidale), utilisant les diagrammes de cordes (string diagrams).

Approche Catégorique : Le travail repose sur la théorie des catégories, spécifiquement l'interaction entre deux structures algébriques bien connues :
1. Les bicatégories cartésiennes (pour la partie existentielle-conjonctive).
2. Les bicatégories linéaires (pour gérer la distribution linéaire et la dualité).
Structure Néo-Peircéenne (NPR) : Ils introduisent le Calcul des Relations Néo-Peircéennes (NPR $\Sigma$ ). Contrairement au CR classique qui ne traite que des relations binaires ( $X \times X$ ), le NPR traite des relations de type $X^n \times X^m$ (relations $n$ -aires).
Dualité Noire/Blanche : La syntaxe utilise deux compositions et deux produits monoidaux, distingués par des couleurs (blanc et noir) :
- Blanc (White) : Correspond à la composition relationnelle standard ( $\circ$ ) et au produit cartésien. Gère la conjonction et l'existence.
- Noir (Black) : Correspond à la composition de De Morgan ( $\bullet$ ) et au produit disjoint. Gère la disjonction et l'universalité.
- Ces deux structures sont liées par des adjonctions linéaires et des lois de Frobenius linéaires.

3. Contributions Clés

A. Définition du Calcul des Relations Néo-Peircéennes (NPR $\Sigma$ )

Les auteurs définissent une grammaire de termes et une représentation graphique basée sur des diagrammes de cordes.

Syntaxe : Pas de variables, pas de quantificateurs explicites. Les quantifications sont implicites via la structure des diagrammes (copieurs et dischargesurs).
Sémantique : Les diagrammes sont interprétés dans la catégorie des ensembles et des relations ($Rel$). La sémantique est définie inductivement de manière très simple par rapport à la FOL traditionnelle.
Expressivité : Le système est prouvé être aussi expressif que la logique du premier ordre complète (avec égalité).

B. Les Bicatégories du Premier Ordre (First-Order Bicategories)

C'est la contribution théorique majeure. Les auteurs définissent une nouvelle structure catégorique, la bicatéorie du premier ordre (fo-bicatéorie), qui combine :

Une structure de bicatéorie cartésienne (coproducts, monoides/comonoides).
Une structure de bicatéorie cocartésienne (dualité inversée).
Une structure de bicatéorie linéaire (distribution linéaire, adjonctions linéaires).
Des lois de Frobenius linéaires reliant les structures blanche et noire.

Cette structure capture exactement les interactions nécessaires pour modéliser la logique du premier ordre de manière purement algébrique.

C. Complétude et Axiomatisation

Théorème Principal : L'axiomatisation de NPR $\Sigma$ (basée sur les lois des fo-bicatégories) est complète pour la logique du premier ordre.
Preuve : La preuve de complétude est une adaptation diagrammatique de la preuve de Henkin pour le théorème de complétude de Gödel.
- Elle gère les modèles à domaine vide (souvent exclus en FOL classique), ce qui permet de distinguer les théories triviales des théories contradictoires.
- Elle montre que pour toute théorie non contradictoire, il existe un modèle (le modèle de Henkin construit à partir des constantes de la théorie).

D. Encodages et Interopérabilité

Les auteurs démontrent que le NPR peut encoder :

Le Calcul des Relations de Tarski (CR).
La Logique des Foncteurs de Prédicats de Quine (PFL).
Les Graphes Existentiels de Peirce (EG).
Cela positionne le NPR comme un langage unificateur pour plusieurs formalismes logiques historiques.

4. Résultats Techniques

Complétude : Pour tous les termes $c, d$ , $c \leq d$ (sémantiquement) si et seulement si $c \preceq d$ (dérivable syntaxiquement via les axiomes).
Gestion des Modèles Vides : Contrairement à la FOL classique qui impose des domaines non vides, le NPR permet naturellement des modèles vides. Cela permet de capturer la logique propositionnelle comme un cas particulier (théories triviales) et d'éviter les pièges liés à l'hypothèse de non-vacuité dans les preuves de complétude.
Règles de Dérivation Profonde (Deep Inference) : La structure des diagrammes permet des réécritures locales (comme dans le Calcul des Structures), offrant une flexibilité supérieure aux systèmes de déduction traditionnels.
Dualité et Négation : La négation est traitée comme une opération dérivée (miroir + inversion de couleur) plutôt qu'un opérateur primitif, ce qui simplifie la structure axiomatique.

5. Signification et Impact

Résolution d'un problème ouvert : L'article répond positivement à la question de Tarski sur l'axiomatisabilité du calcul des relations, mais en élargissant le cadre syntaxique au-delà des relations binaires vers des relations d'arité arbitraire via des diagrammes.
Fondements pour l'Informatique :
- Assistants de Preuve : La nature purement équationnelle et diagrammatique du système le rend très adapté à l'implémentation dans des assistants de preuve et à l'automatisation.
- Sémantique des Programmes : Le lien avec les catégories cartésiennes et les bicatégories linéaires offre de nouvelles perspectives pour la sémantique des langages de programmation, notamment pour les systèmes distribués, quantiques et les bases de données.
Héritage de Peirce : Le travail réalise la vision de Peirce de traiter les relations ternaires et supérieures aussi facilement que les relations binaires, en donnant une fondation catégorique rigoureuse à ses intuitions graphiques (Graphes Existentiels).
Nouveau Paradigme Logique : Il démontre que l'on peut obtenir la puissance de la logique du premier ordre sans la complexité syntaxique des quantificateurs et des variables, en utilisant la topologie des diagrammes de cordes.

En résumé, cet article propose un cadre mathématique élégant et complet qui unifie l'algèbre des relations, la logique du premier ordre et la théorie des catégories, en remplaçant la syntaxe arborescente traditionnelle par une syntaxe diagrammatique puissante et axiomatisable.