A taxonomy of categories for relations

Résumé technique : Une taxonomie des catégories de relations

Énoncé du problème
L'étude des catégories abstrayant les propriétés structurelles des relations a produit, au cours des dernières décennies, un corpus de travaux diversifié et riche. Cependant, la prolifération de concepts similaires issus de contextes différents (par exemple, les présentations algébriques des graphes de termes, la probabilité catégorielle, les fonctions partielles et la logique) a conduit à une littérature fragmentée. Ces structures partagent souvent une nature fondamentale mais utilisent des notations et des terminologies différentes (par exemple, les catégories de restriction, les catégories de Markov, les $p$-catégories et les catégories de copie/suppression). Cette fragmentation rend difficile la navigation dans ce domaine et l'établissement d'un cadre clair reliant ces diverses notions catégorielles. De plus, bien qu'il soit établi que la catégorie de Kleisli d'une monade symétrique monoidale sur une catégorie cartésienne est symétrique monoidale, une investigation systématique de la manière dont ces propriétés s'étendent aux contextes enrichis et à des sous-classes spécifiques de monades (affines, pertinentes et $gs$-monoidales) a fait défaut.

Méthodologie
Les auteurs adoptent une approche modulaire fondée sur le langage des diagrammes de cordes pour unifier et classifier ces structures. La méthodologie centrale comprend :

1. Décomposition en axiomes fondamentaux : La taxonomie repose sur deux concepts fondamentaux : les catégories de partage (équipées d'un duplicateur $\nabla_X: X \to X \otimes X$) et les catégories avec poubelle (équipées d'un déchargeur $!_X: X \to I$).
2. Variation axiomatique : En variant les exigences concernant l'existence et la naturalité de ces flèches, les auteurs déduisent une hiérarchie de catégories. Par exemple, exiger la naturalité pour les deux flèches donne des catégories monoidales cartésiennes, tandis que n'exiger que l'existence donne des catégories $gs$-monoidales.
3. Dualisation et enrichissement : Le cadre est étendu aux structures duales (catégories $cogs$-monoidales) et aux contextes enrichis en préordres (remplaçant les catégories standards par des 2-catégories où les 2-cellules représentent un ordre, tel que l'inclusion ensembliste).
4. Analyse de Kleisli : L'article examine les catégories de Kleisli des monades symétriques monoidales (spécifiquement les monades affines, pertinentes et $gs$-monoidales) sur ces catégories de base. Il analyse comment les propriétés structurelles de la catégorie de base (par exemple, l'existence de diagonales ou de projections) sont préservées ou transformées dans la catégorie de Kleisli résultante.

Contributions clés

• Taxonomie unifiée : L'article fournit une taxonomie diagrammatique complète qui organise les « catégories de relations » (incluant les catégories de Markov, de restriction, $gs$-monoidales et cartésiennes) en fonction de la présence et de la naturalité des duplicateurs et des déchargeurs.
• Caractérisation des structures connues : Il établit des correspondances précises entre la taxonomie proposée et les cadres existants. Plus précisément :
  • Les catégories $gs$-monoidales avec projections correspondent exactement aux catégories de Markov.
  • Les catégories $gs$-monoidales avec diagonales correspondent exactement aux catégories de restriction cartésiennes.
• Résultats sur les catégories de Kleisli : Les auteurs prouvent que la catégorie de Kleisli d'une monade pertinente (resp. affine) sur une catégorie avec diagonales (resp. projections) conserve ces structures spécifiques. Par conséquent, la catégorie de Kleisli d'une monade $gs$-monoidale sur une catégorie monoidale cartésienne est elle-même cartésienne monoidale.
• Contexte enrichi : L'article étend ces résultats aux catégories enrichies en préordres. Il introduit les catégories oplax cartésiennes (où les flèches sont oplax copiables et déchargeables) et démontre que les catégories oplax cartésiennes posétales satisfaisant des inégalités spécifiques sont équivalentes aux catégories de restriction.
• Structures duales et bialgébriques : L'ouvrage définit et analyse les structures duales ($cogs$-monoidales, $bigs$-monoidales) et explore l'interaction entre les structures de monoïde et de comonoïde, identifiant les conditions pour les catégories bialgébriques et de Frobenius.

Résultats

• Préservation structurelle : L'article démontre que la propriété d'être une catégorie $gs$-monoidale est préservée lors de la formation de catégories de Kleisli pour les monades symétriques monoidales.
• Préservation spécifique :
  • Si une catégorie de base $C$ possède des projections (est une catégorie de Markov) et que $T$ est une monade affine, la catégorie de Kleisli $C_T$ possède des projections.
  • Si $C$ possède des diagonales (est une catégorie de restriction cartésienne) et que $T$ est une monade pertinente, $C_T$ possède des diagonales.
  • Si $C$ est cartésienne monoidale et que $T$ est une monade $gs$-monoidale, $C_T$ est cartésienne monoidale.
• Catégories de Kleisli enrichies : Pour les catégories $gs$-monoidales enrichies en préordres, si $C$ est oplax cartésienne et que $T$ est une monade $gs$-monoidale colax, alors la catégorie de Kleisli $C_T$ est également oplax cartésienne.
• Bicatégories cartésiennes : L'article montre que les bicatégories cartésiennes correspondent exactement aux bicatégories oplax cartésiennes posétales qui sont lax spéciales et lax connectées et satisfont une inégalité spécifique. De plus, la catégorie de Kleisli d'une monade $gs$-monoidale colax sur une bicatégorie cartésienne est elle-même une bicatégorie cartésienne.
• Exemples : La taxonomie est validée par divers exemples, notamment les catégories de spans, les relations pondérées (via des monades d'anneau) et les catégories d'ensembles et de relations partielles/totales.

Portée et affirmations
Les auteurs affirment que leur contribution principale est d'apporter clarté et organisation à un domaine fragmenté en fournissant un point de référence unique et modulaire pour ces concepts apparentés. En utilisant des diagrammes de cordes et un ensemble minimal d'axiomes, ils offrent un langage intuitif mais rigoureux pour comparer les notions relationnelles.

Concernant l'analyse des catégories de Kleisli, l'article indique que l'extension de ces résultats au contexte enrichi (catégories enrichies en préordres) est, à leur connaissance, originale. L'ouvrage vise à servir à la fois les chercheurs expérimentés en rassemblant le matériel pertinent en un seul endroit et les nouveaux arrivants en offrant une introduction autonome. Les auteurs notent explicitement que, bien qu'ils mentionnent brièvement la factorisation epi-mono, une comparaison systématique avec les techniques de décomposition telles que les lois de distribution est hors du champ de cet article, positionnant leur approche $gs$-monoidale comme une alternative distincte et axiomatiquement simple aux taxonomies basées sur les doubles catégories.

L'article conclut en esquissant des orientations futures, notamment la présentation combinatoire des catégories $gs$-monoidales libres, l'extension aux catégories tracées pour les systèmes de rétroaction, et de nouvelles investigations sur les notions alternatives de catégories de Markov et de monades affines dans le contexte de la théorie des probabilités.