Distributeur (théorie des catégories)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Distributeur.

Un distributeur (aussi appelé profoncteur, module ou bimodule) est une généralisation catégorique de la notion de relations entre ensembles, et de la notion de bisimulation en informatique théorique.

Histoire[modifier | modifier le code]

La notion est introduite et développée par Jean Bénabou en 1973[1], sous le nom de profoncteurs, auquel très vite il préfère le terme de distributeurs : par analogie avec l'analyse, où les distributions donnent naissance aux fonctions, les « distributeurs » font apparaître les foncteurs.

Ross Street[2],[3] a développé dans les années 1980 la théorie dans le cadre enrichi avec Max Kelly (en)[4]. L'école de Sydney introduit également le nom de module ou bimodule pour les distributeurs, une appellation motivée par le fait que dans le cadre V-enrichi, avec V une catégorie ne contenant qu'un seul objet, les distributeurs correspondent aux bimodules entre monoïdes, dans le sens habituel.

Richard Wood (en) introduit les proflèches[5],[6] ainsi que la notion d'équipement en distributeurs. Plus récemment, il a été compris que l'étude des distributeurs était particulièrement adaptée à la modélisation en informatique théorique de problèmes tels que la bisimulation[7]et les problèmes de concurrence[8], ainsi que pour fournir des modèles catégoriques de la logique (en) tensorielle[9] et linéaire classique.

Motivation[modifier | modifier le code]

Si on considère deux ensembles A et B, alors une relation entre ces ensembles est une application A \to \wp(B), où \wp(B) est l'ensemble des sous-ensembles de B.

Dans le cas où A et B sont des ensembles partiellement ordonnés (posets), les relations correspondent aux applications monotones de A dans le poset formé des sous-parties de B fermées vers le bas, ordonnées par l'inclusion, noté \downarrow B -- qui correspond à \wp(B) si B est un poset discret, et en ce sens généralise véritablement la notionde relation telle que définie dans le cas des ensembles.

La catégorie des posets, dont les morphismes sont les applications monotones, est cartésienne fermée si bien qu'une relation entre A et B peut se voir comme une application monotone

B^{\mathrm{op}} \times A \to \mathbf{2}

2 désigne le treillis à deux éléments.

Puisque les posets sont des catégories enrichies sur 2, et que les catégories ordinaires peuvent se voir comme des catégories enrichies sur la catégorie Set des ensembles, on peut concevoir, de manière analogue, une relation entre ensembles comme la donnée d'un foncteur

B^{\mathrm{op}} \times A \to \mathsf{Set}

Définition[modifier | modifier le code]

Un distributeur de A vers B, noté \phi :  A\nrightarrow B, est un foncteur

\phi : B^{\mathrm{op}}\times A\to\mathsf{Set}

De manière équivalente, en utilisant le fait que la catégorie Cat des petites catégories est cartésienne fermée, si on note

\hat B = \mathsf{Set}^{B^{\mathrm{op}}}

la catégorie des préfaisceaux sur B, alors on peut définir un distributeur de A vers B comme un foncteur

\phi : A \to \hat B

En particulier, le foncteur Hom d'une catégorie C définit un distributeur « identité » \mathrm{id} : C^{\mathrm{op}} \times C \to \mathsf{Set}.

Si on travaille dans le cadre V-enrichi, avec V une catégorie monoidale complète, cocomplète et telle que les V-foncteurs issus de l'opération \otimes_V préservent les colimites, on peut définir une notion de distributeur enrichi ou V-distributeur : un tel distributeur \phi :  A\nrightarrow B est un V-foncteur

\phi : B^{\mathrm{op}}\otimes A\to V

On dit parfois que l'existence d'un distributeur \phi :  A\nrightarrow B établit une correspondance de B vers A.

Bicatégorie des distributeurs[modifier | modifier le code]

Pour les ensembles et pour les posets, la catégorie des relations est une catégorie de Kleisli sur les monades engendrées par \wp et \downarrow respectivement. Dans ces cas, la composition est évidente et donnée par la composition dans la catégorie de Kleisli. Mais ce n'est pas vrai en général et la composition de distributeurs ne jouit pas de « bonnes » propriétés, en particulier l'associativité stricte. On peut donc espérer, au mieux, considérer une bicatégorie (en) (i.e. une 2-catégorie (en) faible) des distributeurs, notée Dist :

  • Les 0-cellules sont les petites catégories ;
  • Les 1-cellules entre deux telles catégories sont les distributeurs entre ces catégories ;
  • Les 2-cellules sont les transformations naturelles entre distributeurs.

On définit la composition de deux distributeurs

\phi: A\nrightarrow B
\psi: B\nrightarrow C

par

\psi\phi = \mathrm{L}_B \psi \circ \phi

avec \mathrm{L}_B \psi : \hat B \to \hat C l'extension de Kan à gauche de \psi le long du morphisme de Yoneda \mathrm{Y}_B : B \to \hat B . Dans une catégorie de préfaisceaux, on peut exprimer cette composition point par point, c'est-à-dire en termes de cofin :

\psi\phi(c, a) = \int^{b: B} \psi(c,b)\times\phi(b,a)

ce qui se transporte aisément au cas enrichi, avec \otimes_V au lieu de \times, et permet de définir la catégorie V-Dist des distributeurs V-enrichis.

Cette composition est définie de manière universelle, et donc n'est associative qu'à isomorphisme près, en général.

Références[modifier | modifier le code]

  1. Jean Bénabou, Les distributeurs. Rapport n°33 du Séminaire de Mathématiques Pures, Université Catholique de Louvain, 1973.
  2. Ross Street, Fibrations in bicategories, Cahiers Topologie Géom. Différentielle 21.2 (1980) pages 111-160.
  3. Ross Street, Enriched categories and cohomology, Quaestiones Mathematicae 6, no. 1-3 (1983) pages 265-283.
  4. Max G. Kelly, Ross Street, Review of the elements of 2-categories, Category seminar. Springer Berlin Heidelberg (1974)
  5. Richard J. Wood, Abstract pro arrows I, Cahiers de topologie et géometrie différentielle categoriques 23.3 (1982) pages 279-290.
  6. Richard J. Wood, Pro arrows II, Cahiers de topologie et géometrie différentielle categoriques 26(2):135-168 (1985)
  7. Gian Luca Cattani, Glynn Winskel : Profunctors, open maps and bisimulation, Mathematical Structures in Computer Science 15.3 (2005) pages 553-614.
  8. Mikkel Nygaard, Glynn Winskel: Domain theory for concurrency. Theoretical Computer Science, 316(1):153–190 (2004).
  9. Nicolas Tabareau, Modalités de ressource et contrôle en logique tensorielle, Thèse de doctorat à l'Université Paris-Diderot-Paris VII, 2008.

Bibliographie[modifier | modifier le code]