💻 computer science

Uniform Realizability Interpretations

Cet article présente un cadre novateur de réalisabilité uniforme qui unifie et généralise diverses interprétations de la logique en paramétrant l'interprétation par le traitement des formules atomiques, permettant ainsi de couvrir tant les variantes classiques que modernes, y compris celles de l'arithmétique de Heyting.

Auteurs originaux : Ulrich Berger, Paulo Oliva

Publié 2026-03-05

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ulrich Berger, Paulo Oliva

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 : Comment prouver qu'une chose existe sans la montrer ?

Imaginez que vous êtes un architecte. Vous avez deux façons de prouver qu'un bâtiment existe :

La méthode classique (Kleene) : Vous devez fournir les plans exacts, les coordonnées GPS précises et les noms des ouvriers qui ont construit chaque brique. Si vous dites « Il y a une maison quelque part », vous devez pointer du doigt exactement où elle se trouve.
La méthode uniforme (Berger & Oliva) : Vous dites « Il y a une maison quelque part » et vous donnez un magicien capable de construire la maison n'importe où, instantanément, sans que vous ayez besoin de savoir où elle sera à l'avance. Le magicien est le même pour tous les emplacements possibles.

C'est l'essence de cet article. Les auteurs proposent un nouveau cadre, une « boîte à outils universelle », pour comprendre comment les mathématiques peuvent prouver des choses (comme l'existence de nombres ou de solutions) sans toujours avoir besoin de donner la réponse exacte tout de suite.

🛠️ La Boîte à Outils : La Réalisabilité Uniforme

Dans le monde de la logique mathématique, on utilise souvent des « réalisateurs ». C'est comme un témoin ou un programme informatique qui dit : « Je peux prouver que cette affirmation est vraie ».

Jusqu'à présent, il y avait deux écoles de pensée qui ne se parlaient pas bien :

L'école des « Témoins Précis » : Pour prouver « Il existe un nombre $x$ tel que... », le témoin doit donner le nombre exact $x$ . (Exemple : Kleene).
L'école des « Témoins Uniques » : Pour prouver « Pour tout nombre $x$ ... », le témoin est une seule règle qui fonctionne pour tous les $x$ en même temps, sans changer. (Exemple : Réalisabilité de Herbrand).

L'idée géniale de Berger et Oliva :
Ils disent : « Pourquoi choisir ? Créons une boîte à outils unique qui peut faire les deux ! »
Ils appellent cela la réalisabilité uniforme.

Imaginez que la logique est un jeu de construction.

Les formules atomiques (les briques de base comme « 2+2=4 » ou « 5 est un nombre ») sont définies par vous, le joueur. Vous décidez comment on les valide.
Les connecteurs logiques (et, ou, si... alors, il existe, pour tout) sont gérés par la boîte à outils de manière uniforme.

C'est comme si vous aviez un robot cuisinier.

Vous lui donnez la recette de base (les briques).
Le robot sait automatiquement comment mélanger les ingrédients pour faire un gâteau (ET), une salade (OU), ou comment cuisiner pour n'importe quel nombre de convives (POUR TOUT), sans que vous ayez à lui réapprendre la logique à chaque fois.

🌟 Les 5 Exemples Concrets (Les Variations du Jeu)

L'article montre que cette boîte à outils peut reproduire 5 jeux de logique célèbres, comme si on changeait simplement les règles de base (les briques) :

Le Compteur (Kleene) :
- Analogie : Un compteur qui doit compter chaque brique individuellement.
- Règle : Pour dire « Il existe un nombre », le témoin doit être ce nombre précis. C'est très concret, mais parfois lourd.
Le Constructeur de Modèles (Kreisel) :
- Analogie : Au lieu de donner un nombre, on donne un plan de construction parfait.
- Règle : Tout est total (rien ne plante). C'est comme si le robot cuisinier ne faisait jamais d'erreur de calcul.
Le Magicien de l'Infini (Herbrand) :
- Analogie : Le magicien ne donne pas un nombre, mais un panier contenant plusieurs nombres possibles.
- Règle : Pour dire « Il existe un nombre », le témoin est un panier fini. L'un des nombres dans le panier est la bonne réponse, mais on ne sait pas lequel tout de suite. C'est très puissant pour les mathématiques non-standard.
Le Détective (Réalisation Classique) :
- Analogie : Le détective travaille avec des hypothèses. « Si je trouve un indice, alors la maison existe ».
- Règle : On utilise la logique classique (où on peut dire « soit c'est vrai, soit c'est faux ») mais on essaie quand même d'extraire un peu de sens pratique (un témoin) de ces affirmations.
L'Apprenti (Learning Realizability) :
- Analogie : C'est un élève qui apprend en cours de route. Au début, il ne sait rien. S'il se trompe, il met à jour ses connaissances (son « état »).
- Règle : Le témoin est un programme qui change d'état. Si on lui demande « Existe-t-il un nombre ? », il peut dire « Je ne sais pas encore, mais si vous me donnez plus d'info, je trouverai ». C'est comme un logiciel qui apprend de ses erreurs.

💡 Pourquoi est-ce important ?

Cet article est une fête pour Stefano Berardi (c'est un cadeau d'anniversaire !), mais il apporte une vraie clarté :

Unification : Il montre que ces 5 méthodes, qui semblaient très différentes, sont en fait la même chose avec des réglages différents sur les briques de base.
Flexibilité : Vous pouvez choisir vos propres règles pour les nombres ou l'égalité, et la logique s'adaptera automatiquement.
Puissance : Cela permet de prouver des théorèmes complexes en utilisant des outils simples, comme si on avait un passe-partout pour toutes les portes de la logique.

🎯 En résumé

Imaginez que la logique est un orchestre.
Avant, chaque musicien (Kleene, Kreisel, Herbrand) jouait sa propre partition avec ses propres instruments, et personne ne comprenait comment ils s'accordaient.
Berger et Oliva ont écrit une seule partition maîtresse. Ils ont dit : « Voici le chef d'orchestre (la réalisabilité uniforme). Vous, musiciens, choisissez juste votre instrument (la définition des briques de base), et le chef s'assurera que tout le monde joue juste ensemble. »

C'est une belle façon de montrer que derrière la complexité des mathématiques, il y a souvent une simplicité élégante et unifiée.

1. Problématique et Contexte

L'article s'inscrit dans le domaine de la logique intuitionniste et de la théorie des types, plus spécifiquement dans l'étude des interprétations de réalisabilité (realizability). Depuis la réalisation de Kleene en 1945, de nombreuses variantes ont été proposées (réalisabilité modifiée de Kreisel, réalisabilité « classique », réalisabilité de Herbrand, réalisabilité par apprentissage d'Aschieri-Berardi, etc.).

Le problème central identifié par les auteurs réside dans la diversité des traitements des quantiﬁeurs et des formules atomiques :

Dans les approches traditionnelles (ex: réalisabilité de Kleene), un réalisateur pour une formule existentielle $\exists n A(n)$ doit fournir explicitement un témoin $n$ et un réalisateur pour $A(n)$ .
Dans des approches plus récentes (ex: réalisabilité de Herbrand ou de l'arithmétique uniforme), les quantiﬁeurs sont traités de manière uniforme : un réalisateur pour $\exists n A(n)$ ne fournit pas nécessairement $n$ explicitement, et un réalisateur pour $\forall n A(n)$ doit fonctionner uniformément pour tout $n$ sans dépendre d'un $n$ spécifique en entrée.

Cette hétérogénéité rend difficile la comparaison formelle entre ces interprétations et la preuve de leurs propriétés de manière unifiée. L'objectif est de dégager un cadre commun qui unifie ces variantes tout en isolant leurs différences fondamentales.

2. Méthodologie : Le Cadre de Réalisabilité Uniforme

Les auteurs proposent un cadre général paramétré appelé réalisabilité uniforme. L'idée maîtresse est de séparer la complexité de l'interprétation des prédicats atomiques de la structure logique des formules composées.

A. Distinction des Quantiﬁeurs

L'article introduit une distinction cruciale entre :

Quantiﬁeurs non qualifiés (uniformes) : $\exists x A(x)$ et $\forall x A(x)$ .
Quantiﬁeurs qualifiés (typés) : $\exists^B x A(x)$ et $\forall^B x A(x)$ , où $B$ est un prédicat.

Les auteurs postulent que les quantiﬁeurs non qualifiés doivent toujours recevoir une interprétation uniforme, tandis que les quantiﬁeurs qualifiés sont traités comme des abréviations :

$\exists^B x A(x) \equiv \exists x (B(x) \land A(x))$
$\forall^B x A(x) \equiv \forall x (B(x) \to A(x))$

Ainsi, la complexité de l'interprétation est reportée sur la définition du prédicat $B(x)$ et des formules atomiques.

B. Définition Formelle

Le cadre est défini par rapport à une théorie source $S$ (ex: l'arithmétique de Heyting, HA) et une théorie cible $T$ (généralement une extension de HA ou un système de types).

Interprétation de base : À chaque symbole de prédicat $P$ de $S$ (d'arité $n$ ), on associe une relation $(n+m)$ -aire $x \triangleleft_P a$ dans $T$ . Ici, $x$ est le tuple d'arguments du prédicat et $a$ est le tuple des réalisateurs (témoins).
Interprétation des formules composées : L'interprétation $a \text{ ur } A$ $a ur A$ (a réalise uniformément A) est définie par récurrence :
- Atomique : $a \text{ ur } P(x) \iff x \triangleleft_P a$ .
- Conjonction : $(a, b) \text{ ur } A \land B \iff (a \text{ ur } A) \land (b \text{ ur } B)$ .
- Implication : $f \text{ ur } A \to B \iff \forall a ((a \text{ ur } A) \to (f(a)\downarrow \land f(a) \text{ ur } B))$ .
- Existentiel (Uniforme) : $a \text{ ur } \exists x A(x) \iff \exists x (a \text{ ur } A(x))$ . Note : Le réalisateur $a$ ne change pas, il ne doit pas extraire $x$ .
- Universel (Uniforme) : $a \text{ ur } \forall x A(x) \iff \forall x (a \text{ ur } A(x))$ . Note : Le même $a$ doit réaliser $A(x)$ pour tout $x$ .

Cette définition abstraite permet de capturer à la fois les interprétations où les réalisateurs sont des nombres (Kleene) et celles où ils sont des fonctions ou des états, en modifiant uniquement la relation de base $\triangleleft_P$ .

3. Résultats Principaux et Contributions

A. Théorème de Correction (Soundness)

Le Théorème 2.7 établit que si tous les axiomes non-logiques de la théorie source $S$ sont réalisables selon l'interprétation de base choisie, alors tous les théorèmes de $S$ sont réalisables.

Avantage : La preuve de correction se réduit à vérifier la réalisabilité des axiomes non-logiques (comme les axiomes de Peano ou l'induction) pour le prédicat spécifique choisi, sans avoir à réinventer la roue pour chaque variante de réalisabilité.

B. Instantiations Concrètes

Les auteurs montrent que cinq interprétations majeures sont des cas particuliers de leur cadre :

Réalisabilité de Kleene :
- Base : $n \triangleleft_N m \iff n=m$ (interprétation précise).
- Résultat : On retrouve la définition classique où un nombre code un couple $\langle n, \text{témoin} \rangle$ .
Réalisabilité Modifiée de Kreisel :
- Base : Identique à Kleene, mais dans un système de types finis (Système T) avec des réalisateurs totaux.
- Résultat : Permet de réaliser le schéma d'indépendance de la prémisse.
Réalisabilité de Herbrand (Arithmétique non-standard) :
- Base : $n \triangleleft_N \langle \rangle \iff \text{vrai}$ (interprétation uniforme) et $n \triangleleft_{st} S \iff n \in S$ (interprétation approximative par ensembles finis).
- Résultat : Les quantiﬁeurs internes ( $\exists n, \forall n$ ) sont traités uniformément, tandis que les quantiﬁeurs externes (sur les nombres standards) utilisent des ensembles finis comme témoins.
Réalisabilité Classique (Friedman-Dragalin) :
- Base : Le faux ( $\bot$ ) est interprété par un prédicat unaire $P(a)$ . L'égalité est interprétée comme $(n=m) \lor P(a)$ .
- Résultat : Permet d'extraire du contenu computationnel de formules négatives et de traiter la logique classique via une traduction.
Réalisabilité par Apprentissage (Aschieri-Berardi) :
- Base : Introduit un type d'état $S$ . Le faux est réalisé si l'état change ( $\gamma(s) \neq s$ ). L'égalité dépend de l'état fixe.
- Résultat : Modélise des preuves qui mettent à jour un état de connaissance, permettant d'interpréter la loi du tiers exclu pour les formules $\Sigma^0_1$ .

C. Gestion de l'Induction

L'article analyse comment l'interprétation de la relation $N(n)$ (être un nombre naturel) affecte la réalisation du schéma d'induction.

Pour une interprétation approchée (ex: $n \leq a$ ), le réalisateur de l'induction doit construire un majorant uniforme, nécessitant une opération de "jointure" ( $\cup$ ) sur les réalisateurs.
Pour une interprétation précise ( $n=a$ ), l'induction correspond à une récursion primitive standard.

4. Signification et Implications

L'apport de cet article est triple :

Unification Conceptuelle : Il démontre que des interprétations apparemment disparates (Kleene, Herbrand, Classique) partagent une structure logique identique pour les connecteurs et les quantiﬁeurs. La différence réside uniquement dans la sémantique des atomes.
Simplification des Preuves de Correction : En isolant la difficulté dans la définition de la relation de base $\triangleleft_P$ , la preuve de correction pour une nouvelle variante de réalisabilité devient triviale dès lors que les axiomes de base sont vérifiés.
Flexibilité pour la Logique Classique : Le cadre permet d'intégrer des formules valides classiquement (comme la double négation pour les formules uniformes) en tant qu'axiomes supplémentaires, à condition que les prédicats concernés soient interprétés uniformément.

Conclusion

Berger et Oliva proposent une méta-théorie puissante qui abstrait les mécanismes de réalisabilité. En traitant les quantiﬁeurs de manière uniforme et en paramétrant l'interprétation des atomes, ils offrent un outil robuste pour analyser, comparer et étendre les interprétations de réalisabilité, facilitant ainsi l'extraction de programmes à partir de preuves dans des contextes variés (intuitionniste, classique, non-standard). L'article ouvre également des perspectives sur la question de la conservativité de ces extensions de langage par rapport à la théorie de base.