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) $\varphi$ from a category $C$ to a category $D$, written

$\varphi :C\nrightarrow D$,

is defined to be a functor

$\varphi :D^{\mathrm{o}\mathrm{p}}\times C\to \mathbf{S}\mathbf{e}\mathbf{t}$

where $D^{\mathrm{o}\mathrm{p}}$ denotes the opposite category of $D$ and $\mathbf{S}\mathbf{e}\mathbf{t}$ denotes the category of sets. Given morphisms $f:d\to d^{\prime },g:c\to c^{\prime }$ respectively in $D,C$ and an element $x\in \varphi (d^{\prime },c)$, we write $xf\in \varphi (d,c),gx\in \varphi (d^{\prime },c^{\prime })$ to denote the actions. Using the cartesian closure of $\mathbf{C}\mathbf{a}\mathbf{t}$, the category of small categories, the profunctor $\varphi$ can be seen as a functor

$\hat{\varphi }:C\to \hat{D}$

where $\hat{D}$ denotes the category ${\mathrm{S}\mathrm{e}\mathrm{t}}^{D^{\mathrm{o}\mathrm{p}}}$ of presheaves over $D$. A correspondence from $C$ to $D$ is a profunctor $D\nrightarrow C$.

Profunctors as categories

An equivalent definition of a profunctor $\varphi :C\nrightarrow D$ is a category whose objects are the disjoint union of the objects of $C$ and the objects of $D$, and whose morphisms are the morphisms of $C$ and the morphisms of $D$, plus zero or more additional morphisms from objects of $D$ to objects of $C$. The sets in the formal definition above are the hom-sets between objects of $D$ and objects of $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 ${\varphi }^{\text{op}}\times \varphi \to \mathbf{S}\mathbf{e}\mathbf{t}$ to $D^{\text{op}}\times C$. This also makes it clear that a profunctor can be thought of as a relation between the objects of $C$ and the objects of $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 $\psi \varphi$ of two profunctors

$\varphi :C\nrightarrow D$ and $\psi :D\nrightarrow E$

is given by

$\psi \varphi ={\mathrm{L}\mathrm{a}\mathrm{n}}_{Y_D}(\hat{\psi })\circ \hat{\varphi }$

where ${\mathrm{L}\mathrm{a}\mathrm{n}}_{Y_D}(\hat{\psi })$ is the left Kan extension of the functor $\hat{\psi }$ along the Yoneda functor $Y_D:D\to \hat{D}$ of $D$ (which to every object $d$ of $D$ associates the functor $D(-,d):D^{\mathrm{o}\mathrm{p}}\to \mathrm{S}\mathrm{e}\mathrm{t}$). It can be shown that

$(\psi \varphi )(e,c)=(\coprod _{d\in D}\psi (e,d)\times \varphi (d,c))/\sim$

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

$y^{\prime }=vy\in \psi (e,d^{\prime })$ and $x^{\prime }v=x\in \varphi (d,c)$.

Equivalently, profunctor composition can be written using a coend

$(\psi \varphi )(e,c)={\int }^{d:D}\psi (e,d)\times \varphi (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 $F:C\to D$ can be seen as a profunctor ${\varphi }_F:C\nrightarrow D$ by postcomposing with the Yoneda functor:

${\varphi }_F=Y_D\circ F$.

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

See also

• Anafunctor

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