algebra for a profunctor


Category theory




The notion of algebra over an endo-profunctor (CC-CC-bimodule) is a joint generalization of the notions algebra for an endofunctor and coalgebra for an endofunctor.


For a category CC and a CC-CC bimodule H:C op×CSetH : C^{op} \times C \to Set, an algebra for HH is given by a functor X:DCX \colon D \to C and an extranatural transformation *H(X,X)\ast \to H(X,X), where *:1Set\ast \colon \mathbf{1} \to Set is constant at the point. XX is called the carrier of the algebra. A morphism (X,α)(Y,β)(X, \alpha) \to (Y, \beta) of HH-algebras is given by a natural transformation ϕ:XY\phi \colon X \Rightarrow Y such that H(X,ϕ)α=H(ϕ,Y)βH(X,\phi) \circ \alpha = H(\phi,Y) \circ \beta.

If DD is the one-object category, an algebra (X,α)(X,\alpha) is given by an object XX in CC and an element αH(X,X)\alpha \in H(X, X). A morphism between two algebras (X,α)(X, \alpha) and (Y,β)(Y, \beta) is then a morphism m:XYm : X \to Y in CC such that H(X,m)(α)=H(m,Y)(β)H(X, m) (\alpha) = H(m, Y) (\beta), these both being elements of H(X,Y)H(X, Y).

There is an an obvious forgetful functor into CC from the category of algebras for HH, which sends each algebra to its carrier and each algebra morphism to its underlying morphism in CC; among other properties, this functor is always faithful and conservative.

In fact, the category Alg(H)Alg(H), together with its forgetful functor U:Alg(H)CU\colon Alg(H)\to C, has the universal property of an Eilenberg-Moore object, namely that of being the universal HH-algebra. Specifically, it is a terminal object in the category whose objects are functors G:DCG\colon D\to C equipped with an extranatural transformation *H(G,G?)\ast \to H(G-,G?). For such an extranatural transformation consists of, for every dDd\in D, an element ξ dH(Gd,Gd)\xi_d \in H(G d,G d), such that for every morphism v:dev\colon d\to e in DD, we have H(id d,v)(ξ d)=H(v,id e)(ξ e)H(id_d,v)(\xi_d) = H(v,id_e)(\xi_e). This is precisely the data of a functor DAlg(H)D\to Alg(H) lying over CC.

Coalgebras in Prof

One version of Yoneda's lemma says that for a profunctor K:CCK \colon C ⇸ C there is a bijection between extranatural transformations *K\ast \to K and natural transformations hom CK\hom_C \to K. So there are bijections

*¨H(X,X) hom DH(X,X) C(1,X)HC(1,X) \array{ \ast \: {\ddot\to} \: H(X,X) \\ \hom_D \Rightarrow H(X,X) \\ C(1,X) \Rightarrow H \circ C(1,X) }

where the last holds by the usual properties of representable profunctors (see e.g. proarrow equipment). This exhibits each HH-algebra on XX in the above sense as a HH-coalgebra in ProfProf with carrier C(1,X)C(1,X).


  • Algebras and coalgebras for endofunctors are special cases of algebras for bimodules; specifically, an algebra for an endofunctor FF is an algebra for the bimodule Hom(F(),?)Hom(F(-), ?), while a coalgebra for FF is an algebra for the bimodule Hom(,F(?))Hom(-, F(?)).

  • A natural transformation between functors FF and GG from CC to DD is a section of the forgetful functor into CC from the category of algebras for the CCC-C bimodule Hom D(F(),G(?))Hom_D(F(-), G(?)). That is, it gives every object of CC the structure of an algebra for Hom D(F(),G(?))Hom_D(F(-), G(?)) in such a way as that every morphism of CC has the property of being an algebra morphism between the algebras on its domain and codomain.

  • A natural numbers object (in the weak, unparametrized sense) in a category CC with terminal object 11 is an initial object in the category of algebras for the bimodule Hom C(1,?)×Hom C(,?)Hom_C(1, ?) \times Hom_C(-, ?). If CC has binary coproducts, then this is of course the same as an initial algebra for the endofunctor 1+()1+(-).

Last revised on April 26, 2011 at 05:12:16. See the history of this page for a list of all contributions to it.