Profunctor

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

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

ϕ : C ↛ D {\displaystyle \phi :C\nrightarrow D} ,

is defined to be a functor

ϕ : D o p × C → S e t {\displaystyle \phi :D^{\mathrm {op} }\times C\to \mathbf {Set} }

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

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

ϕ ^ : C → D ^ {\displaystyle {\hat {\phi }}:C\to {\hat {D}}}

where D ^ {\displaystyle {\hat {D}}} denotes the category S e t D o p {\displaystyle \mathrm {Set} ^{D^{\mathrm {op} }}} of presheaves over D {\displaystyle D} .

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

An equivalent definition of a profunctor ϕ : C ↛ D {\displaystyle \phi :C\nrightarrow D} is a category whose objects are the disjoint union of the objects of C {\displaystyle C} and the objects of D {\displaystyle D} , and whose morphisms are the morphisms of C {\displaystyle C} and the morphisms of D {\displaystyle D} , plus zero or more additional morphisms from objects of D {\displaystyle D} to objects of C {\displaystyle C} . The sets in the formal definition above are the hom-sets between objects of D {\displaystyle D} and objects of C {\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 ϕ op × ϕ → S e t {\displaystyle \phi ^{\text{op}}\times \phi \to \mathbf {Set} } to D op × C {\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 C {\displaystyle C} and the objects of D {\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.

The composite ψ ϕ {\displaystyle \psi \phi } of two profunctors

ϕ : C ↛ D {\displaystyle \phi :C\nrightarrow D} and ψ : D ↛ E {\displaystyle \psi :D\nrightarrow E}

is given by

ψ ϕ = L a n Y D ( ψ ^ ) ∘ ϕ ^ {\displaystyle \psi \phi =\mathrm {Lan} _{Y_{D}}({\hat {\psi }})\circ {\hat {\phi }}}

where L a n Y D ( ψ ^ ) {\displaystyle \mathrm {Lan} _{Y_{D}}({\hat {\psi }})} is the left Kan extension of the functor ψ ^ {\displaystyle {\hat {\psi }}} along the Yoneda functor Y D : D → D ^ {\displaystyle Y_{D}:D\to {\hat {D}}} of D {\displaystyle D} (which to every object d {\displaystyle d} of D {\displaystyle D} associates the functor D ( − , d ) : D o p → S e t {\displaystyle D(-,d):D^{\mathrm {op} }\to \mathrm {Set} } ).

It can be shown that

( ψ ϕ ) ( e , c ) = ( ∐ d ∈ D ψ ( e , d ) × ϕ ( d , c ) ) / ∼ {\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 ( y ′ , x ′ ) ∼ ( y , x ) {\displaystyle (y',x')\sim (y,x)} whenever there exists a morphism v {\displaystyle v} in D {\displaystyle D} such that

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

Equivalently, profunctor composition can be written using a coend

( ψ ϕ ) ( e , c ) = ∫ d : D ψ ( e , d ) × ϕ ( d , c ) {\displaystyle (\psi \phi )(e,c)=\int ^{d\colon D}\psi (e,d)\times \phi (d,c)}

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.

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

ϕ F = Y D ∘ F {\displaystyle \phi _{F}=Y_{D}\circ F} .

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

• Anafunctor