Distributeur (théorie des catégories)

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

La notion est introduite et développée par Jean Bénabou en 1967^[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 (mathématique) (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

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 , les relations correspondent aux applications monotones de A dans l'ensemble partiellement ordonné 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 ensemble partiellement ordonné discret, et en ce sens généralise véritablement la notion de relation telle que définie dans le cas des ensembles.

La catégorie des ensembles partiellement ordonnés, 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}

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

Puisque les ensembles partiellement ordonnés 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

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

Pour les ensembles et pour les ensembles partiellement ordonnés, 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 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

↑ Jean Bénabou, « Introduction to bicategories », dans Reports of the Midwest Category Seminar, vol. 47, Springer Berlin Heidelberg, 1967 (ISBN 978-3-540-03918-1, DOI 10.1007/bfb0074299, lire en ligne), p. 1–77
↑ Ross Street, Fibrations in bicategories, Cahiers Topologie Géom. Différentielle 21.2 (1980) pages 111-160.
↑ Ross Street, Enriched categories and cohomology, Quaestiones Mathematicae 6, no. 1-3 (1983) pages 265-283.
↑ Max G. Kelly, Ross Street, Review of the elements of 2-categories, Category seminar. Springer Berlin Heidelberg (1974)
↑ Richard J. Wood, Abstract pro arrows I, Cahiers de topologie et géometrie différentielle categoriques 23.3 (1982) pages 279-290.
↑ Richard J. Wood, Pro arrows II, Cahiers de topologie et géometrie différentielle categoriques 26(2):135-168 (1985)
↑ Gian Luca Cattani, Glynn Winskel : Profunctors, open maps and bisimulation, Mathematical Structures in Computer Science 15.3 (2005) pages 553-614.
↑ Mikkel Nygaard, Glynn Winskel: Domain theory for concurrency. Theoretical Computer Science, 316(1):153–190 (2004).
↑ 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

Jean Bénabou, Distributors at work, juin 2000
Francis Borceux, Handbook of Categorical Algebra 1, Cambridge University Press, 2004
nLab, Profunctor

Portail des mathématiques

[:8-1] Jean Bénabou, « Introduction to bicategories », dans Reports of the Midwest Category Seminar, vol. 47, Springer Berlin Heidelberg, 1967 (ISBN 978-3-540-03918-1, DOI 10.1007/bfb0074299, lire en ligne), p. 1–77

[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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]