🔢 mathematics

Functional completeness and primitive positive decomposition of relations on finite domains

Cet article présente une construction nouvelle, élémentaire et efficace sur le plan computationnel qui décompose les relations d'arité supérieure sur des domaines finis en relations binaires en exploitant la complétude fonctionnelle et en convertissant des disjonctions spécifiques en quantifications existentielles, fournissant ainsi une preuve uniforme de la thèse de réduction de Peirce et démontrant que le graphe de toute fonction de Sheffer peut composer toutes ces relations.

Auteurs originaux : Sergiy Koshkin

Publié 2026-06-19

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Sergiy Koshkin

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

Imaginez que vous avez un manuel d'instructions géant et compliqué pour une machine. Ce manuel décrit comment effectuer des tâches qui nécessitent de nombreuses mains travaillant ensemble à la fois (comme un pas de danse à 5 personnes). Le papier pose une question simple : Pouvons-nous décomposer cette instruction complexe à plusieurs personnes en une série d'instructions simples à deux personnes ?

L'auteur, Sergiy Koshkin, dit « Oui, nous le pouvons », mais avec quelques nuances intéressantes selon la taille de la pièce (le « domaine ») où la machine opère.

Voici la décomposition du document en utilisant des analogies de la vie quotidienne :

1. L'idée principale : Décomposer la complexité

Considérez une relation complexe (comme « A est le frère de B, qui est le parent de C ») comme un gros nœud emmêlé. Le document traite de la manière de dénouer ce nœud en boucles plus petites et plus simples.

En mathématiques et en informatique, nous traitons souvent des « relations » (des règles reliant des choses).

Unaire : Une chose (ex. : « Est rouge »).
Binaire : Deux choses (ex. : « Est plus grand que »).
Ternaire : Trois choses (ex. : « Est entre »).
N-aire : De nombreuses choses.

Le but est de prendre une règle qui nécessite 5 personnes pour être comprise et de montrer qu'elle peut en fait être construite en enchaînant des règles qui n'en nécessitent que 2 ou 3.

2. Le monde infini vs Le monde fini

Le document distingue deux types de mondes :

Le Monde Infini : Imaginez une pièce avec un nombre infini de personnes. Ici, vous pouvez réaliser un tour de magie appelé « Abstraction Hypostatique ». C'est comme prendre une danse complexe à 5 personnes et dire : « Prétendons que tout ce groupe n'est qu'une seule nouvelle personne. » Vous pouvez instantanément transformer n'importe quelle règle complexe en une règle binaire simple. C'est facile, mais cela nécessite une réserve infinie de « nouvelles personnes » pour servir de substituts.
Le Monde Fini : C'est notre monde réel, où le nombre de personnes est limité. Vous ne pouvez pas simplement inventer de nouvelles personnes pour vous aider. C'est là que le document fait tout son travail de fond. L'auteur montre que même dans une petite pièce bondée, vous pouvez toujours décomposer des règles complexes, mais vous avez besoin d'une construction spécifique et ingénieuse.

3. L'astuce principale : Transformer les règles en « Fonctions »

L'arme secrète de l'auteur est un concept appelé « Relatifs ».
Habituellement, une « fonction » est comme un distributeur automatique : vous insérez une pièce (entrée) et vous obtenez un snack (sortie). C'est une rue à sens unique.
Une « relation » est plutôt comme un groupe de discussion (chat) : tout le monde est connecté, mais personne n'est strictement le « patron » ou la « sortie ».

L'analogie :
Imaginez que vous avez un groupe de discussion où tout le monde discute. Pour simplifier cela, l'auteur dit : « Prétendons qu'une personne dans le chat est le "patron" (la sortie), et que tous les autres ne font qu'envoyer des messages. »
En prétendant que la relation est une « fonction partielle » (un patron qui ne répond parfois pas), l'auteur peut utiliser les astuces mathématiques bien connues pour décomposer les fonctions.

Le processus :

Identifier le Patron : Choisissez une variable dans votre règle complexe pour qu'elle soit la « sortie ».
Le Sélecteur : Si la règle permet plusieurs sorties possibles (comme un patron qui pourrait envoyer soit un SMS, soit un e-mail), l'auteur utilise un « sélecteur » pour choisir un chemin spécifique.
La Chaîne : Une fois que vous avez une fonction, vous pouvez la décomposer. Tout comme vous pouvez construire une machine complexe à partir d'engrenages simples, vous pouvez construire n'importe quelle fonction complexe à partir de simples engrenages à 2 entrées (des fonctions qui prennent deux choses et produisent une seule).
Le Résultat : Cela prouve que toute règle complexe peut être décomposée en relations ternaires (des règles impliquant 3 choses). Voyez cela comme une règle de « intermédiaire » : Si A fait X à B, et que B fait Y à C, alors A est connecté à C.

4. L'étape finale : Passer de 3 personnes à 2 personnes

Le document va encore plus loin. Pouvons-nous décomposer ces règles à 3 personnes en règles à 2 personnes ?

Sur de grands domaines finis (3 personnes et plus) : Oui ! L'auteur utilise une astuce ingénieuse appelée « Existentialisation des disjonctions ».
- La métaphore : Imaginez que vous avez une règle qui dit : « Vous pouvez entrer si vous portez un Chapeau OU une Écharpe OU des Gants. »
- Dans une petite pièce, vous ne pouvez pas facilement transformer le « OU » en une chaîne simple. Mais l'auteur montre que si vous avez assez de personnes (au moins 3), vous pouvez transformer cette liste « OU » en une question de type « Qui tient le ticket ? ». Vous introduisez une variable temporaire (le « détenteur du ticket ») et demandez : « Existe-t-il une personne tenant un ticket qui rend la règle vraie ? »
- Cela convertit la logique complexe du « OU » en une logique simple du « Existe » (Existence), permettant de construire la règle ternaire entièrement à partir de règles binaires.
Sur de petits domaines finis (Booléens / 2 personnes) : Non.
- Si vous n'avez que deux personnes (comme Vrai/Faux ou 0/1), vous vous heurtez à un mur. Il existe certaines règles à 3 personnes qui ne peuvent tout simplement pas être décomposées en règles à 2 personnes.
- La métaphore : C'est comme essayer de construire une forme 3D spécifique en utilisant uniquement des pièces plates en 2D. Certaines formes ne s'emboîteront tout simplement pas. Le document prouve que sur un monde à 2 personnes, certaines relations complexes sont « irréductibles » — elles sont les blocs de construction atomiques qui ne peuvent être davantage simplifiés.

5. La surprise de « Sheffer »

Le document découvre également quelque chose de fascinant : tout comme il existe un seul « interrupteur magique » (le crochet de Sheffer) en logique qui peut construire n'importe quelle porte logique, il existe une seule « Relation de Sheffer » (une règle spécifique à 3 personnes) qui peut construire n'importe quelle autre relation sur un domaine fini.

C'est comme trouver une brique Lego spécifique qui, si vous en avez assez, peut construire n'importe quel château, voiture ou vaisseau spatial.

Résumé de la « Conclusion à retenir »

La complexité est gérable : Vous pouvez prendre presque n'importe quelle règle compliquée impliquant de nombreuses variables et la décomposer en règles simples impliquant seulement 2 ou 3 variables.
L'intermédiaire est Ternaire : La façon la plus efficace de décomposer les choses s'arrête généralement à 3 variables (Ternaire).
La taille compte : Si votre monde est assez grand (3 éléments ou plus), vous pouvez tout décomposer en 2 variables. Si votre monde est minuscule (seulement 2 éléments), certaines règles à 3 variables sont bloquées et ne peuvent pas être simplifiées.
Les fonctions aident les relations : En prétendant que les relations sont des fonctions (avec un patron et des travailleurs), nous pouvons utiliser les outils mathématiques existants pour résoudre les problèmes de relations.

Le document fournit essentiellement un nouvel « manuel d'instructions » plus simple pour déconstruire les relations de données complexes, prouvant que même dans un monde limité, nous pouvons tout construire à partir d'interactions simples à deux personnes, à condition d'avoir quelques règles d'aide spécifiques.

Résumé technique : Complétude fonctionnelle et décomposition primitivement positive des relations sur des domaines finis

Énoncé du problème
L'article traite du problème de la décomposition de relations d'arité supérieure en relations d'arité inférieure, spécifiquement en relations binaires, en utilisant des formules primitivement positives (fpp). Une formule primitivement positive est une conjonction de prédicats avec des quantificateurs existentiels. Ce problème, connu sous le nom de Thèse de Réduction Relationnelle (TRR), postule que les relations d'ordre $n$ ( $n \ge 2$ ) peuvent être réduites à des relations binaires, bien que toutes les relations binaires ne se réduisent pas à des relations unaires.

Alors que l'analogue fonctionnel (Thèse de Réduction Fonctionnelle, TRF) — selon lequel les fonctions à $n$ entrées se réduisent à des fonctions à 2 entrées — est bien établi (via les travaux de Post sur la logique polyvalente et les fonctions de Sheffer), le cas relationnel sur des domaines finis était moins clair. Les résultats précédents étaient dispersés, souvent non constructifs, ou reposaient sur l'extension du domaine (abstraction hypostatique), ce qui n'est pas réalisable sur des domaines finis sans ajouter des éléments. De plus, il est connu que la TRR échoue sur les domaines booléens (où existent des relations ternaires irréductibles), mais les raisons structurelles de cet échec et les conditions de succès sur des domaines finis généraux nécessitaient une explication unifiée et élémentaire.

Méthodologie
L'auteur emploie une approche constructive qui jette un pont entre la complétude fonctionnelle et la décomposition relationnelle en interprétant les relations comme des « relatives » (fonctions partiellement définies multivalentes). La méthodologie procède en trois étapes :

Réduction relative (Relations vers Ternaire) :
L'article traite une relation $n$ -aire $R$ comme une relative possédant un argument de sortie distingué. Il décompose $R$ en une multifunction et une relation de domaine. En utilisant des sélecteurs de valeurs (fonctions qui choisissent une valeur dans l'image de la multifunction), l'auteur réduit la multifunction en une fonction ordinaire $f(t, x_1, \dots, x_{n-1})$ . En s'appuyant sur la réduction fonctionnelle connue des fonctions à $n$ entrées vers des fonctions à 2 entrées (via les formes normales disjonctives canoniques de Post dans les logiques polyvalentes), l'article démontre que toute relation peut être décomposée en relations ternaires (graphes de fonctions à 2 entrées) et en relations d'arité inférieure.
Existentialisation des disjonctions (Ternaire vers Binaire) :
Pour réduire les relations ternaires aux relations binaires, l'article introduit une construction pour les relations cofinies (relations dont les compléments sont finis). Cette méthode est duelle à l'abstraction hypostatique. Au lieu d'encoder des tuples dans de nouveaux éléments, elle convertit les disjonctions inhérentes à la Forme Normale Conjonctive Complémentaire (FNCC) d'une relation cofini en quantifications existentielles. Ceci est réalisé en introduisant une variable d'indexation et en définissant des prédicats binaires spécifiques qui émulent la disjonction de « colitéraux » unaires. Cette étape n'est valide que lorsque l'arité $n$ n'excède pas la taille du domaine $|D|$ , permettant une injection des indices dans le domaine.
Réduction de liaison et Thèse de Peirce :
L'article analyse la relation entre la composition primitivement positive et la « liaison » originale de Peirce (composition restreinte impliquant des produits relatifs et l'identification de variables). Il prouve que pour les arités $n \ge 4$ , la réductibilité pp et la réductibilité par liaison sont équivalentes, à condition que des « teridentités » ( $I_3$ ) soient autorisées. Cependant, pour les relations ternaires, la réductibilité par liaison est strictement plus faible que la réductibilité pp.

Contributions clés et Résultats

Théorème 2 (Réduction Relative) : Sur n'importe quel domaine, toute relation $n$ -aire se décompose en une composition d'une fonction $f: D^n \to D$ et d'une relation de domaine. Crucialement, si un ensemble de fonctions à 2 entrées est fonctionnellement complet, toute relation peut être décomposée en les graphes de fonctions de cet ensemble. Cela implique que sur tout domaine fini, toute relation $n$ -aire ( $n \ge 4$ ) est réductible à des relations ternaires.
Corollaire 1 (Relations de Sheffer) : Sur tout domaine fini, il existe des relations ternaires (graphes de fonctions de Sheffer) qui forment à elles seules un système primitivement complet. Cela établit l'existence de « relations de Sheffer » pour les domaines non-booléens.
Théorème 3 (Réduction Binaire des Relations Cofinies) : Pour des domaines avec $|D| \ge 3$ , toute relation $n$ -aire cofini (où $3 \le n \le |D|$ ) se réduit à des relations binaires. Cette construction repose sur la conversion des disjonctions de colitéraux en quantifications existentielles sur des prédicats binaires.
Théorème 4 (Irréductibilité sur les Domaines Booléens) : L'article fournit une preuve élémentaire que la relation ternaire $\neg I_3$ (le complément de l'identité ternaire) est irréductible aux relations binaires sur les domaines booléens. Cela est démontré en montrant que $\neg I_3$ n'est pas « bijonctive » (ne peut être exprimée comme une 2CNF), et puisque la composition pp préserve la bijonctivité, elle ne peut être réduite à des relations binaires (qui sont toutes bijonctives).
Théorèmes 5 & 6 (Liaison vs Réductibilité pp) : L'article précise que pour $n \ge 4$ , la réductibilité pp est équivalente à la réductibilité par liaison (utilisant des teridentités). Cependant, pour les relations ternaires, la réductibilité par liaison est strictement plus faible ; spécifiquement, $I_3$ est irréductible par liaison sur tout domaine possédant au moins deux éléments.

Signification et Revendications
L'article prétend fournir une « preuve uniforme » de la thèse de réduction de Peirce sur les domaines finis en établissant un lien direct et élémentaire entre la thèse de réduction fonctionnelle (TRF) et la thèse de réduction relationnelle (TRR).

Unification : Il résout la déconnexion entre la complétude fonctionnelle et relationnelle en montrant que les graphes des systèmes fonctionnellement complets forment des systèmes primitivement complets sur les relations.
Constructivité : Contra contrairement aux preuves non constructives précédentes reposant sur des connexions de Galois ou des extensions de domaine, cette construction est calculablement efficace et repose sur des méthodes bien développées de décomposition fonctionnelle (logiques de Post).
Explication de l'échec : La construction élucide pourquoi la TRR échoue sur les domaines booléens : l'incapacité de convertir les disjonctions d'ordre supérieur en quantifications existentielles en raison d'un nombre insuffisant d'éléments du domaine (précisément, l'absence d'une injection pour les indices quand $n > |D|$ ).
Nouveaux concepts : Il introduit le concept de « relations de Sheffer » et propose une nouvelle perspective sur l'« abstraction hypostatique » en tant que processus duel de l'« existentialisation des disjonctions ».

L'auteur note avec modestie que si la construction explique la réductibilité des relations vers le ternaire et (pour les cas cofinis) vers le binaire, elle ne fournit pas d'analogue général des critères de Post ou de Slupecki pour la complétude relationnelle sur des domaines finis arbitraires, ni ne caractérise pleinement les coclones maximales. L'article laisse ouverte la question de savoir si des relations de Sheffer binaires existent sur des domaines non-booléens.