In category theory, a branch of mathematics, profunctors are a generalization of relations and also of bimodules. They are related to the notion of correspondences.
A profunctor (also named distributor by the French school and module by the Sydney school) ϕ from a category C to a category D , written
ϕ : C ↛ D ,
is defined to be a functor
ϕ : D o p × C → S e t where D o p denotes the opposite category of D and S e t denotes the category of sets. Given morphisms f : d → d ′ , g : c → c ′ respectively in D , C and an element x ∈ ϕ ( d ′ , c ) , we write x f ∈ ϕ ( d , c ) , g x ∈ ϕ ( d ′ , c ′ ) to denote the actions.
Using the cartesian closure of C a t , the category of small categories, the profunctor ϕ can be seen as a functor
ϕ ^ : C → D ^ where D ^ denotes the category S e t D o p of presheaves over D .
A correspondence from C to D is a profunctor D ↛ C .
The composite ψ ϕ of two profunctors
ϕ : C ↛ D and
ψ : D ↛ E is given by
ψ ϕ = L a n Y D ( ψ ^ ) ∘ ϕ ^ where L a n Y D ( ψ ^ ) is the left Kan extension of the functor ψ ^ along the Yoneda functor Y D : D → D ^ of D (which to every object d of D associates the functor D ( − , d ) : D o p → S e t ).
It can be shown that
( ψ ϕ ) ( e , c ) = ( ∐ d ∈ D ψ ( e , d ) × ϕ ( d , c ) ) / ∼ where ∼ is the least equivalence relation such that ( y ′ , x ′ ) ∼ ( y , x ) whenever there exists a morphism v in D such that
y ′ = v y ∈ ψ ( e , d ′ ) and
x ′ v = x ∈ ϕ ( 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 can be seen as a profunctor ϕ F : C ↛ D by postcomposing with the Yoneda functor:
ϕ F = Y D ∘ F .
It can be shown that such a profunctor ϕ F has a right adjoint. Moreover, this is a characterization: a profunctor ϕ : C ↛ D has a right adjoint if and only if ϕ ^ : C → D ^ factors through the Cauchy completion of D , i.e. there exists a functor F : C → D such that ϕ ^ = Y D ∘ F .
