nLab
colimits in categories of algebras

Introduction

Let $T$ be a monad on a category $C$, and let $C^T$ denote the Eilenberg-Moore category of $T$. Let

$$U:C^T\to C$$U: C^T \to C

be the usual underlying or forgetful functor, with left adjoint $F:C\to C^T$, unit $\eta :1_C\to UF$, and counit $\epsilon :FU\to 1_{C^T}$. It is well-known that $U$ reflects limits, so that if $C$ is complete, then $C^T$ is also complete and $U$ is continuous.

The situation with regard to colimits is more complicated. It is not generally true that if $C$ is cocomplete, then $C^T$ is also. In this article we collect some partial results which address these issues.

Reflexive coequalizers and cocompleteness

A simple but basic fact is the following. Suppose $J$ is a small category, and suppose that the monad $T$ preserves colimits over $J$, that is, suppose that for every $F:J\to C$ the canonical map

$${\mathrm{colim}}_{J}T\circ F\to T({\mathrm{colim}}_{J}F)$$colim_J T \circ F \to T(colim_J F)

is an isomorphism.

Proposition

Under these hypotheses, $U:C^T\to C$ reflects colimits over $J$.

Here are some sample applications of this proposition which arise frequently in practice. Let $J$ be the generic reflexive fork, having exactly two objects $0,1$, generated by three non-identity arrows

$$0\to 1\overrightarrow{\to }0,$$0 \to 1 \stackrel{\to}{\to} 0,

and subject to the condition that the two composites from $0$ to $0$ are the identity. A colimit over $J$ is called a reflexive coequalizer. It frequently happens that a monad $T:C\to C$ preserves reflexive coequalizers; in this case, if $C$ has reflexive coequalizers, then so does $C^T$.

Theorem

If $C$ is cocomplete and $C^T$ has reflexive coequalizers, then $C^T$ is cocomplete.

Proof

First observe that if $(c,\xi :Tc\to c)$ is a $T$-algebra, then $\xi$ is the coequalizer of the reflexive fork

$$FUc\stackrel{F\eta Uc}{\to }FUFUc\stackrel{\stackrel{\epsilon FUc}{\to }}{\underset{FU\epsilon c}{\to }}FUc$$F U c \stackrel{F \eta U c}{\to} F U F U c \stackrel{\overset{\varepsilon F U c}{\to}}{\underset{F U \varepsilon c}{\to}} F U c

To show $C^T$ has coproducts, let $(c_i,{\xi }_i)$ be a collection of algebras. Then $F({\sum }_{i}U{c}_i)$ is the coproduct ${\sum }_{i}FU{c}_i$ in $C^T$ (since $F$ preserves coproducts and $C$ has them). We have a reflexive fork

$$\sum _{i}FU{c}_i\stackrel{\sum _{i}F\eta U{c}_i}{\to }\sum _{i}FUFU{c}_i\stackrel{\stackrel{\sum _i\epsilon FU{c}_i}{\to }}{\underset{\sum _{i}FU\epsilon c}{\to }}\sum _{i}FU{c}_i$$\sum_i F U c_i \stackrel{\sum_i F \eta U c_i}{\to} \sum_i F U F U c_i \stackrel{\overset{\sum_i \varepsilon F U c_i}{\to}}{\underset{\sum_i F U \varepsilon c}{\to}} \sum_i F U c_i

and it is not difficult to show that the coequalizer in $C^T$ of this diagram is the coproduct ${\sum }_i{c}_i$.

Finally, general coequalizers in $C^T$ are constructed from coproducts and reflexive coequalizers: given a parallel pair $f,g:c\overrightarrow{\to }d$ in $C^T$, the coequalizer of $f$ and $g$ is the colimit of the reflexive fork

$$d\to c+d\stackrel{\stackrel{(f,1_d)}{\to }}{\underset{(g,1_d)}{\to }}d$$d \to c + d \stackrel{\overset{(f, 1_d)}{\to}}{\underset{(g, 1_d)}{\to}} d

where the first arrow is the coproduct coprojection.

Corollary

If $T$ is a monad on $\mathrm{Set}$, then ${\mathrm{Set}}^T$ is cocomplete.

Proof

It is enough to show that ${\mathrm{Set}}^T$ has coequalizers. Suppose given a pair of algebra maps $f,g:A\overrightarrow{\to }B$ whose coequalizer we wish to construct. Let $R$ be the $T$-algebra relation

$$R=⟨f,g⟩:A\to B\times B$$R = \langle f, g \rangle: A \to B \times B

and then let $E$ be the smallest $T$-congruence (equivalence relation that is a $T$-subalgebra map $E\hookrightarrow B\times B$) through which $R$ factors. (This is the intersection of all $T$-congruences through which $R$ factors, and may be calculated in $\mathrm{Set}$, where it is reflected in $T$-$\mathrm{Alg}$.) The coequalizer as calculated in $\mathrm{Set}$,

$$E\stackrel{\stackrel{{\pi }_1}{\to }}{\underset{{\pi }_2}{\to }}B\stackrel{p}{\to }Q$$E \stackrel{\overset{\pi_1}{\to}}{\underset{\pi_2}{\to}} B \stackrel{p}{\to} Q

is a split coequalizer, because every quotient of an equivalence relation in $\mathrm{Set}$ is a split coequalizer. (This requires the axiom of choice. A splitting is given by any splitting $i:Q\to B$ of $p$, which picks a representative in each equivalence class, together with $⟨ip,1⟩:B\to E$.) It is therefore an absolute colimit, which the monad $T$ preserves. Hence the top row in

$$\begin{array}{ccccc}TE& \stackrel{\stackrel{T{\pi }_1}{\to }}{\underset{T{\pi }_2}{\to }}& TB& \stackrel{Tp}{\to }& TQ\\ \downarrow & & \downarrow & & \downarrow \\ E& \stackrel{\stackrel{{\pi }_1}{\to }}{\underset{{\pi }_2}{\to }}& B& \to & Q\end{array}$$\array{ T E & \stackrel{\overset{T\pi_1}{\to}}{\underset{T\pi_2}{\to}} & T B & \stackrel{T p}{\to} & T Q \\ \downarrow & & \downarrow & & \downarrow \\ E & \stackrel{\overset{\pi_1}{\to}}{\underset{\pi_2}{\to}} & B & \to & Q}

(the first two vertical arrows being algebra structure maps) is a coequalizer in ${\mathrm{Set}}^T$. The last vertical arrow making the diagram commute gives $Q$ a $T$-algebra structure, and the split coequalizer in the bottom row is reflected in ${\mathrm{Set}}^T$.

Corollary

If $T$ is a monad on a complete and cocomplete category $C$ that preserves reflexive coequalizers, then $C^T$ is complete and cocomplete.

The hypotheses of the preceding corollary hold when $T$ is a monad on a complete, cocomplete, cartesian closed category that is induced from a finitary algebraic theory. (The key observation being that the finitary power functors $x\mapsto x^n$ preserve reflexive coequalizers.)

Here is a more difficult result given in Toposes, Theories, and Triples (theorem 3.9, p. 267):

Proposition

If $C$ has coequalizers and equalizers of arbitrary sets of parallel morphisms, and if a monad $T:C\to C$ preserves colimits of countable chains $\omega \to C$, then $C^T$ has coequalizers.

Corollary

If $C$ is complete and cocomplete and $T:C\to C$ preserves filtered colimits, then $C^T$ is complete and cocomplete.

Relatively free functors

Theorem

Suppose that $\theta :S\to T$ is a morphism of monads on $C$, and suppose that $C^T$ has coequalizers. Then the forgetful functor

$$C^{\theta }:C^T\to C^S$$C^\theta: C^T \to C^S

has a left adjoint.

Proof

Since the following diagram is commutative:

$$\begin{array}{ccc}{C}^T& \stackrel{C^{\theta }}{\to }& C^S\\ {}^{U^T}\downarrow & & {\downarrow }^{U^S}\\ C& =& C\end{array}$$\begin{array}{cccc}C^T & \overset{C^{\theta}}{\to} & C^S \\ ^{U^T}\downarrow & & \downarrow^{U^S} \\ C & = & C \end{array}

(using an obvious notation), it follows immediately from a corollary to the adjoint lifting theorem that if $C^T$ has coequalizers of reflexive pairs, then $C^{\theta }$ has a left adjoint and is, in fact, monadic.

This completes the proof, but it is interesting to observe that there is a concrete description of the left adjoint in this case: The left adjoint sends an $S$-algebra $(c,\xi :Sc\to c)$ to the (reflexive) coequalizer of the pair

$$TSc\stackrel{T\xi }{\to }TcTSc\stackrel{T\theta c}{\to }TTc\stackrel{\mu c}{\to }Tc$$T S c \stackrel{T \xi}{\to} T c \qquad T S c \stackrel{T \theta c}{\to} T T c \stackrel{\mu c}{\to} T c

where $\mu :TT\to T$ is the monad multiplication. (If $u:1_C\to S$ is the unit of $S$, then $Tuc:Tc\to TSc$ is a common right inverse of both arrows of the pair.) This coequalizer is analogous to the construction of the left adjoint $B{\otimes }_A-$ to the functor ${\mathrm{Ab}}^f:{\mathrm{Ab}}^B\to {\mathrm{Ab}}^A$ between module categories given by restricting scalar multiplication; the coequalizer will be denoted $T{\circ }_{S}c$ to underline the analogy.

To see that $T{\circ }_S-$ is the left adjoint, let $(d,\alpha :Td\to d)$ be a $T$-algebra. Any map $f:c\to d$ in $C$ induces a unique $T$-algebra map $\varphi :Tc\to d$:

$$\varphi =(Tc\stackrel{Tf}{\to }Td\stackrel{\alpha }{\to }d)$$\phi = (T c \stackrel{T f}{\to} T d \stackrel{\alpha}{\to} d)

and the claim is that $f:c\to d$ is an $S$-algebra map $c\to C^{\theta }(d)$ if and only if $\varphi$ coequalizes the pair of above, i.e., if $\varphi$ factors (uniquely) through a $T$-algebra map $T{\circ }_{S}c\to d$.

Indeed, the condition that $f$ is an $S$-algebra map is satisfaction of the equation

$$(Sc\stackrel{\xi }{\to }c\stackrel{f}{\to }d)=(Sc\stackrel{Sf}{\to }Sd\stackrel{\theta d}{\to }Td\stackrel{\alpha }{\to }d)$$(S c \stackrel{\xi}{\to} c \stackrel{f}{\to} d) = (S c \stackrel{S f}{\to} S d \stackrel{\theta d}{\to} T d \stackrel{\alpha}{\to} d)

and now we have a long train of equations

$$\begin{array}{ccc}\alpha \circ Tf\circ \mu c\circ T\theta c& =& \alpha \circ \mu d\circ TTf\circ T\theta c\\ & =& \alpha \circ \mu d\circ T\theta d\circ TSf\\ & =& \alpha \circ T\alpha \circ T\theta d\circ TSf\\ & =& \alpha \circ T(\alpha \circ \theta d\circ Sf)\\ & =& \alpha \circ T(f\circ \xi )\\ & =& \alpha \circ Tf\circ T\xi \end{array}$$\array{ \alpha \circ T f \circ \mu c \circ T \theta c & = & \alpha \circ \mu d \circ T T f \circ T \theta c \\ & = & \alpha \circ \mu d \circ T \theta d \circ T S f \\ & = & \alpha \circ T \alpha \circ T \theta d \circ T S f \\ & = & \alpha \circ T(\alpha \circ \theta d \circ S f)\\ & = & \alpha \circ T(f \circ \xi) \\ & = & \alpha \circ T f \circ T \xi }

which gives $\varphi \circ \mu c\circ T\theta c=\varphi \circ T\xi$. This completes one direction. In the other direction, suppose $\varphi \circ \mu c\circ T\theta c=\varphi \circ T\xi$. Then

$$\begin{array}{ccc}\alpha \circ \theta d\circ Sf& =& \alpha \circ Tf\circ \theta c\\ & =& \varphi \circ \theta c\\ & =& \varphi \circ \mu c\circ \eta Tc\circ \theta c\\ & =& \varphi \circ \mu c\circ T\theta c\circ \eta Sc\\ & =& \varphi \circ T\xi \circ \eta Sc\\ & =& \varphi \circ \eta c\circ \xi \\ & =& \alpha \circ Tf\circ \eta c\circ \xi \\ & =& \alpha \circ \eta d\circ f\circ \xi \\ & =& f\circ \xi \end{array}$$\array{ \alpha \circ \theta d \circ S f & = & \alpha \circ \T f \circ \theta c \\ & = & \phi \circ \theta c \\ & = & \phi \circ \mu c \circ \eta T c \circ \theta c \\ & = & \phi \circ \mu c \circ T \theta c \circ \eta S c \\ & = & \phi \circ T \xi \circ \eta S c \\ & = & \phi \circ \eta c \circ \xi \\ & = & \alpha \circ T f \circ \eta c \circ \xi \\ & = & \alpha \circ \eta d \circ f \circ \xi \\ & = & f \circ \xi }

as desired. This completes the proof.

References

• Michael Barr and Charles Wells, Toposes, Theories, and Triples, Reprints in Theory and Applications of Categories (2005), 1-289. (online pdf)