💻 computer science

Interpolation in Proof Theory

Ce chapitre présente une vue d'ensemble des méthodes proof-théoriques, notamment celles de Maehara et Pitts, pour établir les propriétés d'interpolation dans divers logiques, en mettant l'accent sur des techniques constructives et syntaxiques qui éclairent les liens entre ces propriétés et les systèmes de preuve modernes.

Auteurs originaux : Iris van der Giessen, Raheleh Jalali, Roman Kuznets

Publié 2026-02-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Iris van der Giessen, Raheleh Jalali, Roman Kuznets

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 Grand Défi : Trouver le "Pont" entre deux idées

Imaginez que vous avez deux personnes qui parlent deux langues différentes ou qui ont des opinions très éloignées.

Personne A dit : « Si j'ai un gâteau, alors je suis content. »
Personne B dit : « Si je suis content, alors je vais danser. »

La logique nous dit que si A a un gâteau, B va danser. Mais quelle est la cause intermédiaire ? Quel est le lien secret qui permet de passer de "Gâteau" à "Danse" ?

En logique, ce lien secret s'appelle un interpolant. C'est une phrase qui ne contient que les mots communs aux deux parties (ici, "être content") et qui fait le pont entre la prémisse et la conclusion.

Ce chapitre de livre est un guide de survie pour les architectes de la logique. Il explique comment construire ces ponts (les interpolants) de manière mécanique, en utilisant des outils appelés calculs de séquents.

🏗️ Les Outils du Bâtisseur : Les "Calculs de Séquents"

Pour construire ces ponts, les auteurs utilisent des outils appelés calculs de séquents.
Imaginez un squelette ou un plan de construction. Au lieu de juste écrire une phrase, on la décompose en pièces détachées (des règles) que l'on assemble comme des Lego.

Le texte présente trois grandes méthodes pour assembler ces Lego :

1. La Méthode de Maehara : Le Démontage Intelligent

C'est la méthode classique (comme un vieux manuel de bricolage).

L'idée : Prenez une preuve logique (un bâtiment fini) et démontez-la pièce par pièce, de haut en bas.
L'astuce : À chaque fois que vous démontez une pièce, vous séparez les ingrédients qui viennent de la gauche (la cause) de ceux qui viennent de la droite (l'effet).
Le résultat : En remontant le processus, vous reconstruisez un nouveau petit bâtiment (l'interpolant) qui ne contient que les ingrédients partagés par les deux côtés.
La limite : Parfois, ce démontage ne fonctionne pas bien si le bâtiment est trop complexe ou si on utilise des "ponts" (règles de coupe) qui cachent des ingrédients.

2. La Méthode de Pitts : Le Miroir Universel

C'est une méthode plus sophistiquée, conçue pour une logique particulière (la logique intuitionniste, qui est un peu plus stricte que la logique classique).

L'idée : Au lieu de regarder une seule preuve, on imagine toutes les preuves possibles d'une même idée.
L'astuce : On cherche un "super-objet" qui fonctionne comme un filtre universel. Peu importe comment vous arrivez à la conclusion, ce filtre vous dit exactement ce qui est nécessaire.
L'analogie : C'est comme si vous aviez un tamis magique. Peu importe le mélange de sable et de cailloux que vous versez dessus, il ne laisse passer que le sable pur, peu importe la taille des cailloux. Ce tamis est l'interpolant uniforme.

3. Les "Séquents Étiquetés" : La Carte au Trésor

Pour les logiques les plus complexes (comme la logique modale, celle qui parle du "possible" et du "nécessaire"), les méthodes classiques échouent. Il faut aller plus loin.

Le problème : Les règles classiques sont trop rigides.
La solution : On ajoute des étiquettes (des noms de lieux) aux formules. Au lieu de dire "Il pleut", on dit "Au lieu A, il pleut".
L'analogie : Imaginez que vous ne construisez plus un pont sur une rivière, mais un réseau de ponts entre plusieurs îles. Chaque île est un "monde" possible. Les règles de construction doivent maintenant tenir compte de la géographie (qui est connecté à qui).
Le résultat : Cela permet de construire des ponts (interpolants) pour des logiques qui semblaient impossibles à résoudre auparavant.

🌍 Pourquoi tout cela est important ? (La Théorie Universelle)

Le texte ne se contente pas de donner des recettes de cuisine. Il essaie de comprendre pourquoi certaines cuisines ont des recettes parfaites et d'autres non.

La grande question : Existe-t-il une règle universelle pour savoir si une logique donnée possède un "pont" (interpolant) ?
La réponse : Oui ! Les auteurs ont découvert que si les règles de construction d'une logique sont "propres" et bien organisées (ce qu'ils appellent des règles "semi-analytiques"), alors on peut toujours construire le pont.
La conséquence inverse : Si une logique n'a pas de pont, c'est qu'elle n'a pas de règles de construction "propres". C'est comme dire : "Si vous ne pouvez pas trouver de chemin, c'est que votre carte est mal dessinée."

Cela permet de classer les logiques :

Celles qui sont bien construites (elles ont des interpolants).
Celles qui sont "désordonnées" (elles n'en ont pas, et donc on ne peut pas les modéliser facilement avec ces outils).

🎓 En résumé, pour le grand public

Ce document est un manuel de génie civil pour les mathématiciens.

Le but : Trouver le mot ou la phrase manquante qui relie deux idées.
La méthode : Utiliser des règles de construction précises (comme des Lego) pour déconstruire les arguments et reconstruire le lien manquant.
L'innovation : Quand les Lego classiques ne suffisent pas, on ajoute des étiquettes et des cartes géographiques (séquents étiquetés) pour naviguer dans des mondes plus complexes.
La leçon finale : Si vous voulez que votre système logique soit robuste et capable de faire des ponts, vous devez vous assurer que vos règles de construction sont simples, claires et bien organisées. Sinon, le pont ne tiendra pas.

C'est une histoire de structure, de clarté et de connexion, racontée avec les outils les plus puissants de la logique moderne.

1. Problématique et Contexte

L'article aborde la question centrale de l'interpolation dans le cadre de la logique mathématique, en se concentrant sur les méthodes proof-theoretiques (basées sur la théorie de la preuve). Le problème consiste à déterminer si, pour une implication prouvable $\phi \to \psi$ dans une logique donnée, il existe une formule « intermédiaire » $\theta$ (l'interpolant) qui ne contient que les variables propositionnelles communes à $\phi$ et $\psi$ , et telle que $\phi \to \theta$ et $\theta \to \psi$ soient également prouvables.

L'article distingue deux propriétés majeures :

La propriété d'interpolation de Craig (CIP) : L'existence d'un interpolant basé sur l'ensemble des variables communes.
La propriété d'interpolation de Lyndon (LIP) : Une version renforcée où l'interpolant préserve non seulement les variables, mais aussi leur polarité (occurrences positives ou négatives).
La propriété d'interpolation uniforme (UIP) : Une version encore plus forte où l'interpolant ne dépend que de l'antécédent (ou du succédent) et fonctionne uniformément pour n'importe quel succédent (ou antécédent) compatible, interprétant ainsi la quantification propositionnelle.

Le défi principal est que l'existence de ces propriétés n'est pas garantie pour toutes les logiques (notamment les logiques modales et intermédiaires) et que les méthodes sémantiques classiques sont souvent insuffisantes pour fournir des preuves constructives ou pour établir des résultats de non-existence de systèmes de preuve bien comportés.

2. Méthodologie

L'article propose une approche systématique basée sur les calculs de séquents et leurs généralisations. La méthodologie repose sur trois piliers principaux :

A. Méthodes Fondamentales sur les Calculs de Séquents

La méthode de Maehara : Une technique constructive qui, étant donné une preuve de $\phi \to \psi$ dans un calcul de séquents sans coupure (cut-free), construit algorithmiquement un interpolant. Elle utilise des séquents divisés (split sequents) de la forme $\Gamma; \Gamma' \Rightarrow \Delta; \Delta'$ pour suivre l'origine des formules (celles venant de $\phi$ à gauche, celles de $\psi$ à droite).
La méthode de Pitts : Une méthode syntaxique pour prouver l'interpolation uniforme (UIP), notamment pour la logique intuitionniste (IPC). Elle repose sur une recherche de preuve terminante (proof search) dans un calcul fortement terminant, permettant de définir des opérateurs de quantification propositionnelle ( $\exists p \phi, \forall p \phi$ ) directement dans le langage propositionnel.

B. Théorie Universelle de la Preuve (Universal Proof Theory)

L'article intègre ces méthodes dans le cadre de la théorie universelle de la preuve, initiée par Iemhoff. Cette approche établit un lien direct entre les propriétés d'interpolation et la structure des règles d'inférence :

Introduction des règles semi-analytiques : Des règles dont les variables des prémisses sont contenues dans les variables de la conclusion.
Résultats positifs : Si une logique admet un calcul semi-analytique (et fortement terminant pour l'UIP), elle possède la CIP (et l'UIP).
Résultats négatifs : Si une logique ne possède pas la CIP/UIP, alors elle ne peut pas avoir de calcul semi-analytique bien comporté. Cela permet de prouver l'impossibilité de trouver de tels calculs pour de vastes classes de logiques.

C. Généralisations des Calculs de Séquents

Pour les logiques qui n'admettent pas de calcul de séquents standard sans coupure (comme S5 ou certaines logiques modales complexes), l'article explore des structures plus expressives :

Séquents étiquetés (Labelled Sequents) : Intégration de la sémantique de Kripke (mondes, relations d'accessibilité) directement dans la syntaxe des séquents via des étiquettes.
Hyper-séquents et Séquents imbriqués (Nested Sequents) : Structures hiérarchiques permettant de capturer des propriétés modales complexes.
Adaptation de la méthode de Maehara : L'article montre comment adapter la construction d'interpolants à ces structures. Les interpolants ne sont plus de simples formules, mais des multiformules (combinaisons booléennes de formules étiquetées) qui respectent la structure sémantique sous-jacente.

3. Contributions Clés

Unification des méthodes : Le chapitre offre une vue d'ensemble cohérente reliant les méthodes classiques (Maehara, Pitts) aux développements modernes de la théorie universelle de la preuve.
Algorithmes constructifs : Fournit des algorithmes explicites pour construire des interpolants (Craig, Lyndon, Uniformes) à partir de preuves dans divers systèmes (calculs de séquents, étiquetés, hyper-séquents).
Critères structurels pour l'interpolation : Définit des conditions syntaxiques précises (règles semi-analytiques, axiomes focalisés) qui garantissent l'existence de l'interpolation.
Résultats de non-existence : Utilise l'absence d'interpolation pour prouver l'impossibilité d'existence de calculs de séquents « bien comportés » (semi-analytiques) pour de nombreuses logiques intermédiaires, modales et substructurales (ex: extensions de S4, logiques floues comme Łukasiewicz, logiques de pertinence).
Extension aux logiques modales non-normales et conditionnelles : Démontre que la méthode s'applique également à des logiques plus exotiques, prouvant la propriété d'interpolation de Lyndon uniforme (ULIP) pour plusieurs d'entre elles.

4. Résultats Principaux

Logiques Propositionnelles et Modales Classiques : Confirmation que CPC, IPC, et les logiques modales normales (K, T, D, K4, S4, S5, GL) possèdent la CIP et souvent la LIP.
- Note importante : Bien que S5 n'ait pas de calcul de séquents standard sans coupure, l'article montre qu'il possède la LIP grâce aux calculs d'hyper-séquents ou de séquents étiquetés, contournant les limitations de la méthode de Maehara standard avec coupure analytique.
Logiques Intermédiaires : Seules sept logiques intermédiaires cohérentes (IPC, LC, KC, Bd2, Sm, GSc, CPC) possèdent la CIP/UIP. La grande majorité des extensions de IPC ne possèdent ni l'interpolation ni un calcul semi-analytique.
Logiques Substructurales et Linéaires : Identification de classes de logiques (comme MALL, IMALL) qui possèdent la CIP, et d'autres (comme les logiques floues BL, MTL, Łukasiewicz) qui ne la possèdent pas, entraînant l'absence de calculs semi-analytiques.
Logiques Modales Non-Normales : Preuve de l'ULIP pour des logiques comme E, M, K, et des logiques conditionnelles (CE, CK), démontrant la robustesse de la méthode sur des structures non-standard.
Complexité : La complexité des interpolants construits est généralement linéaire par rapport à la taille de la preuve, bien que le calcul nécessite d'abord la construction de la preuve elle-même.

5. Signification et Impact

Cet article est fondamental pour la communauté de la logique et de la théorie de la preuve pour plusieurs raisons :

Manuel de construction : Il sert de guide pratique (« manuel ») pour les chercheurs souhaitant prouver l'interpolation pour une nouvelle logique. La stratégie consiste à vérifier si les règles du calcul de la logique correspondent aux types standards (locaux, conjonctifs, disjonctifs) décrits dans le papier.
Lien Syntaxe-Sémantique : Il démontre comment des propriétés purement syntaxiques (la forme des règles d'inférence) peuvent déterminer des propriétés logiques profondes (interpolation) et des limites structurelles (existence de calculs).
Outils pour la Complexité et l'IA : Les interpolants sont cruciaux pour la vérification de modèles, la synthèse de programmes et la complexité de la preuve (problème NP vs coNP). La capacité à les calculer de manière constructive et modulaire est un atout majeur.
Démystification des calculs sans coupure : L'article corrige l'idée reçue selon laquelle l'existence d'un calcul sans coupure implique automatiquement l'interpolation. Il montre que la structure des règles est le facteur déterminant, et que des calculs plus complexes (étiquetés, imbriqués) sont parfois nécessaires pour obtenir des résultats forts comme la LIP.

En résumé, ce chapitre synthétise des décennies de recherche pour offrir un cadre unifié, constructif et puissant pour analyser et prouver les propriétés d'interpolation à travers un spectre large de logiques, reliant la théorie des preuves, la sémantique et la complexité computationnelle.