nLab
algebra for a profunctor

Idea

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

Definition

For a category $C$ and a $C$-$C$ bimodule $H:C^{\mathrm{op}}\times C\to \mathrm{Set}$, an algebra for $H$ is given by a functor $X:D\to C$ and an extranatural transformation $*\to H(X,X)$, where $*:1\to \mathrm{Set}$ is constant at the point. $X$ is called the carrier of the algebra. A morphism $(X,\alpha )\to (Y,\beta )$ of $H$-algebras is given by a natural transformation $\varphi :X\Rightarrow Y$ such that $H(X,\varphi )\circ \alpha =H(\varphi ,Y)\circ \beta$.

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

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

In fact, the category $\mathrm{Alg}(H)$, together with its forgetful functor $U:\mathrm{Alg}(H)\to C$, has the universal property of an Eilenberg-Moore object, namely that of being the universal $H$-algebra. Specifically, it is a terminal object in the category whose objects are functors $G:D\to C$ equipped with an extranatural transformation $*\to H(G-,G?)$. For such an extranatural transformation consists of, for every $d\in D$, an element ${\xi }_d\in H(Gd,Gd)$, such that for every morphism $v:d\to e$ in $D$, we have $H({\mathrm{id}}_d,v)({\xi }_d)=H(v,{\mathrm{id}}_e)({\xi }_e)$. This is precisely the data of a functor $D\to \mathrm{Alg}(H)$ lying over $C$.

Coalgebras in Prof

One version of Yoneda's lemma says that for a profunctor $K:C⇸C$ there is a bijection between extranatural transformations $*\to K$ and natural transformations ${\mathrm{hom}}_C\to K$. So there are bijections

$$\begin{array}{c}*\ddot{\to }H(X,X)\\ {\mathrm{hom}}_D\Rightarrow H(X,X)\\ C(1,X)\Rightarrow H\circ C(1,X)\end{array}$$\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 $H$-algebra on $X$ in the above sense as a $H$-coalgebra in $\mathrm{Prof}$ with carrier $C(1,X)$.

Examples

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

• A natural transformation between functors $F$ and $G$ from $C$ to $D$ is a section of the forgetful functor into $C$ from the category of algebras for the $C-C$ bimodule ${\mathrm{Hom}}_D(F(-),G(?))$. That is, it gives every object of $C$ the structure of an algebra for ${\mathrm{Hom}}_D(F(-),G(?))$ in such a way as that every morphism of $C$ 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 $C$ with terminal object $1$ is an initial object in the category of algebras for the bimodule ${\mathrm{Hom}}_C(1,?)\times {\mathrm{Hom}}_C(-,?)$. If $C$ has binary coproducts, then this is of course the same as an initial algebra for the endofunctor $1+(-)$.

Related concepts

• algebra over a monad, algebra over an endofunctor, coalgebra over an endofunctor