Profunctor

From Quire, the open reference·Generalization in mathematics·2 min read

In category theory, a branch of mathematics, profunctors are a generalization of relations and also of bimodules.

Definition#edit

A profunctor (also named distributor by the French school and module by the Sydney school) ${\displaystyle \,\phi }$ from a category ${\displaystyle C}$ to a category ${\displaystyle D}$ , written

${\displaystyle \phi :C\nrightarrow D}$ ,

is defined to be a functor

${\displaystyle \phi :D^{\mathrm {op} }\times C\to \mathbf {Set} }$

where ${\displaystyle D^{\mathrm {op}$ denotes the opposite category of ${\displaystyle D}$ and ${\displaystyle \mathbf {Set} }$ denotes the category of sets. Given morphisms ${\displaystyle f:d\to d',g:c\to c'}$ respectively in ${\displaystyle D,C}$ and an element ${\displaystyle x\in \phi (d',c)}$ , we write ${\displaystyle xf\in \phi (d,c),gx\in \phi (d',c')}$ to denote the actions.

Using that the category of small categories ${\displaystyle \mathbf {Cat} }$ is cartesian closed, the profunctor ${\displaystyle \phi }$ can be seen as a functor

${\displaystyle {\hat {\phi :C\to {\hat {D$

where ${\displaystyle {\hat {D$ denotes the category ${\displaystyle \mathrm {Set} ^{D^{\mathrm {op}$ of presheaves over ${\displaystyle D}$ .

A correspondence from ${\displaystyle C}$ to ${\displaystyle D}$ is a profunctor ${\displaystyle D\nrightarrow C}$ .

Profunctors as categories#edit

An equivalent definition of a profunctor ${\displaystyle \phi :C\nrightarrow D}$ is a category whose objects are the disjoint union of the objects of ${\displaystyle C}$ and the objects of ${\displaystyle D}$ , and whose morphisms are the morphisms of ${\displaystyle C}$ and the morphisms of ${\displaystyle D}$ , plus zero or more additional morphisms from objects of ${\displaystyle D}$ to objects of ${\displaystyle C}$ . The sets in the formal definition above are the hom-sets between objects of ${\displaystyle D}$ and objects of ${\displaystyle C}$ . (These are also known as het-sets, since the corresponding morphisms can be called heteromorphisms.) The previous definition can be recovered by the restriction of the hom-functor ${\displaystyle \phi ^{\text{op\times \phi \to \mathbf {Set} }$ to ${\displaystyle D^{\text{op\times C}$ .

This also makes it clear that a profunctor can be thought of as a relation between the objects of ${\displaystyle C}$ and the objects of ${\displaystyle D}$ , where each member of the relation is associated with a set of morphisms. A functor is a special case of a profunctor in the same way that a function is a special case of a relation.

Composition of profunctors#edit

The composite ${\displaystyle \psi \phi }$ of two profunctors

${\displaystyle \phi :C\nrightarrow D}$ and ${\displaystyle \psi :D\nrightarrow E}$

is given by

${\displaystyle \psi \phi =\mathrm {Lan} _{Y_{D({\hat {\psi )\circ {\hat {\phi$

where ${\displaystyle \mathrm {Lan} _{Y_{D({\hat {\psi )}$ is the left Kan extension of the functor ${\displaystyle {\hat {\psi$ along the Yoneda functor ${\displaystyle Y_{D}:D\to {\hat {D$ of ${\displaystyle D}$ (which to every object ${\displaystyle d}$ of ${\displaystyle D}$ associates the functor ${\displaystyle D(-,d):D^{\mathrm {op} }\to \mathrm {Set} }$ ).

It can be shown that

${\displaystyle (\psi \phi )(e,c)=\left(\coprod _{d\in D}\psi (e,d)\times \phi (d,c)\right){\Bigg /}\sim }$

where ${\displaystyle \sim }$ is the least equivalence relation such that ${\displaystyle (y',x')\sim (y,x)}$ whenever there exists a morphism ${\displaystyle v}$ in ${\displaystyle D}$ such that

${\displaystyle y'=vy\in \psi (e,d')}$ and ${\displaystyle x'v=x\in \phi (d,c)}$ .

Equivalently, profunctor composition can be written using a coend

${\displaystyle (\psi \phi )(e,c)=\int ^{d\colon D}\psi (e,d)\times \phi (d,c)}$

Bicategory of profunctors#edit

Composition of profunctors is associative only up to isomorphism (because the product is not strictly associative in Set). The best one can hope is therefore to build a bicategory Prof whose

0-cells are small categories,
1-cells between two small categories are the profunctors between those categories,
2-cells between two profunctors are the natural transformations between those profunctors.

Properties#edit

Lifting functors to profunctors#edit

A functor ${\displaystyle F:C\to D}$ can be seen as a profunctor ${\displaystyle \phi _{F}:C\nrightarrow D}$ by postcomposing with the Yoneda functor:

${\displaystyle \phi _{F}=Y_{D}\circ F}$ .

It can be shown that such a profunctor ${\displaystyle \phi _{F$ has a right adjoint. Moreover, this is a characterization: a profunctor ${\displaystyle \phi :C\nrightarrow D}$ has a right adjoint if and only if ${\displaystyle {\hat {\phi :C\to {\hat {D$ factors through the Cauchy completion of ${\displaystyle D}$ , i.e. there exists a functor ${\displaystyle F:C\to D}$ such that ${\displaystyle {\hat {\phi =Y_{D}\circ F}$ .

References#edit

Bénabou, Jean (2000), Distributors at Work (PDF)
Borceux, Francis (1994). Handbook of Categorical Algebra. CUP.
Lurie, Jacob (2009). Higher Topos Theory. Princeton University Press.
Profunctor at the nLab
Heteromorphism at the nLab

Categories Functors

This article is mirrored from “Profunctor” on English Wikipedia, revision 1344169020, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1344169020 · just now