Profunctor

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

Definition

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 the cartesian closure of ${\displaystyle \mathbf {Cat} }$, the category of small categories, 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

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

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

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

Lifting functors to profunctors

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

• 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