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$, i.e., the category of $T$-algebras. Let

$$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 U F$, and counit $\varepsilon: F U \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. (See Adámek & Koubek, III.10, for an example when $C =$ Pos.) In this article we collect various results that guarantee existence of colimits of algebras.

Reflexive coequalizers and cocompleteness

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

$$colim_J T \circ F \to T(colim_J F)$$

is an isomorphism.

Proposition

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

For a proof, see Proposition 4.3.2 of Handbook of Categorical Algebra (Volume 2). In fact, what is shown there is a tighter result: if $D:J\to C^T$ is any diagram such that $U \circ D$ has a colimit preserved by both $T$ and $T \circ T$, then $D$ has a colimit preserved by $U$.

Here preservation by just $T$ is not sufficient. A counterexample is given by the algebraic theory generated by a 1-ary operation $f$ and a 3-ary operation $g$ with the following laws:

• $f(f(x)) = x$.
• $g(x,x,y) = g(x,y,x) = g(y,x,x) = x$.
• $g(x,f(x),y) = g(x,y,f(x)) = g(y,x,f(x)) = y$.

The corresponding monad on $\mathrm{Set}$ preserves the coproduct $1 + 1$. However, in the category of algebras we have $1 + 1 = 1$.

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 \stackrel{\longrightarrow}{\longrightarrow} 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$.

The following very useful observation was first made by Linton.

Theorem

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

Proof

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

$$\array{ F U c & \stackrel{F \eta U c}{\longrightarrow} & F U F U c & \stackrel{\overset{\varepsilon F U c}{\longrightarrow}}{\underset{F \xi}{\longrightarrow}} & 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 F U c_i$ in $C^T$ (since $F$ preserves coproducts and $C$ has them). We have a reflexive fork

$$\array{ \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}{\longrightarrow}}{\underset{\sum_i F \xi_i}{\longrightarrow}} & \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 \stackrel{\longrightarrow}{\longrightarrow} d$ in $C^T$, the coequalizer of $f$ and $g$ is the colimit of the reflexive fork

$$\array{ 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 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 $C$ is a complete, cocomplete, cartesian closed category and $T$ is the monad corresponding to a finitary algebraic theory. (The key observation being that the finitary power functors $x \mapsto x^n$ preserve reflexive coequalizers if $C$ is cartesian closed.)

Corollary

Assuming the axiom of choice, if $T$ is a monad on Set, then $Set^T$ is cocomplete. Similarly upon replacing $Set$ by a slice $Set/X \simeq Set^X$, or by Vect.

Proof

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

$$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 $Set$, where it is reflected in $T$-$Alg$ since $U: Set^T \to Set$ reflects arbitrary intersections.) The coequalizer as calculated in $Set$,

$$\array{ U E & \stackrel{\overset{U \pi_1}{\longrightarrow}}{\underset{U \pi_2}{\longrightarrow}} & U B & \stackrel{p}{\longrightarrow} & Q }$$

is a split coequalizer, because every quotient of an equivalence relation in $Set$ is a split coequalizer. (This requires the axiom of choice. A splitting is given by any splitting $i: Q \to U B$ of $p$, which picks a representative in each equivalence class, together with $\langle i p, 1 \rangle: U B \to U E$.) The proof is completed by the following lemma.

Lemma

In a category $\mathbf{C}$, given a pair $\pi_1, \pi_2: E \rightrightarrows B$ in $\mathbf{C}^T$ such that $U\pi_1, U\pi_2: U E \rightrightarrows U B$ has a split coequalizer $U B \to Q$ in $\mathbf{C}$, the pair $\pi_1, \pi_2$ has a coequalizer in $\mathbf{C}^T$ (reflected by the split coequalizer).

Proof

(Cf. monadicity theorem.) A split coequalizer is an absolute colimit, which the functor $T$ preserves. Hence the top row in

$$\array{ T U E & \stackrel{\overset{T U\pi_1}{\to}}{\underset{T U\pi_2}{\to}} & T U B & \stackrel{T p}{\longrightarrow} & T Q \\ \downarrow & & \downarrow & & \downarrow \\ U E & \stackrel{\overset{U\pi_1}{\longrightarrow}}{\underset{U\pi_2}{\longrightarrow}} & U B & \stackrel{p}{\longrightarrow} & Q }$$

(the first two vertical arrows being algebra structure maps) is a coequalizer in $\mathbf{C}^T$. The last vertical arrow making the diagram commute gives $Q$ a $T$-algebra structure, and the split coequalizer in the bottom row is thereby reflected in $\mathbf{C}^T$ (i.e., lifts to a coequalizer in $\mathbf{C}^T$, albeit not necessarily to one that is itself split).

Categories of algebras are Barr exact

Theorem

If $\mathbf{C}$ is a regular category or exact category in which regular epimorphisms split, and $T$ is any monad on $\mathbf{C}$, then $\mathbf{C}^T$ is a regular category (or exact category, respectively).

Proof

For regularity, we first construct coequalizers of kernel pairs in $\mathbf{C}^T$. So suppose $\pi_1, \pi_2: E \rightrightarrows B$ is the kernel pair of some $f: B \to C$ in $\mathbf{C}^T$. The kernel pair $U\pi_1, U\pi_2: U E \to U B$ of $U f$ in $\mathbf{C}$ has a coequalizer $q: U B \to Q$ in $\mathbf{C}$, and of course $U\pi_1, U\pi_2$ is the kernel pair of $q$ as well. It follows from the splitting hypothesis that the fork

$$\array{ U E & \stackrel{\overset{U\pi_1}{\longrightarrow}}{\underset{U\pi_2}{\longrightarrow}} & U B & \stackrel{q}{\longrightarrow} & Q}$$

splits in $\mathbf{C}$, hence by Lemma this diagram lifts to a coequalizer for $\pi_1, \pi_2: E \rightrightarrows B$ in $\mathbf{C}^T$. Thus kernel pairs in $\mathbf{C}^T$ have coequalizers.

That regular epis in $\mathbf{C}^T$ are stable under pullback follows a similar line of reasoning: let $p: B \to P$ be a regular epi in $\mathbf{C}^T$. It is the coequalizer of its kernel pair $\pi_1, \pi_2: E \rightrightarrows B$. We just calculated that the coequalizer $q: U B \to Q$ of $U\pi_1, U\pi_2$ in $\mathbf{C}$ lifts to $\mathbf{C}^T$, so that $Q$ is identified with $U P$ and $q$ with $U p$. Thus $U p$ is a regular epi in $\mathbf{C}$. Now if $f: A \to P$ is a map in $\mathbf{C}^T$, and $b = f^\ast p$ is the pullback of $p$ along $f$ (with kernel pair $\ker(b)$), then $U b$ is the pullback of $U p$ along $U f$ since $U$ preserves pullbacks, and so $U b$ is a regular epi since $\mathbf{C}$ is regular. This $U b$ is the coequalizer of its kernel pair, and splits, so by Lemma , its lift $b$ is the coequalizer of $\ker(b)$. Thus regular epis in $\mathbf{C}^T$ are stable under pullback.

For Barr-exactness, suppose $\pi_1, \pi_2: E \rightrightarrows B$ is an equivalence relation (or congruence) in $\mathbf{C}^T$. Then $U\pi_1, U\pi_2: U E \rightrightarrows U B$ is an equivalence relation in $\mathbf{C}$, and hence a kernel pair since $\mathbf{C}$ is exact. It is the kernel pair of its coequalizer $q$ in $\mathbf{C}$. By Lemma , the split coequalizer

$$\array{ U E & \stackrel{\overset{U\pi_1}{\longrightarrow}}{\underset{U\pi_2}{\longrightarrow}} & U B & \stackrel{q}{\to} & Q }$$

lifts to a coequalizer diagram in $\mathbf{C}^T$, and since kernel pairs are preserved and reflected by $U: \mathbf{C}^T \to \mathbf{C}$, we conclude that $\pi_1, \pi_2$ is the kernel pair of the lifted regular epi over $q$.

Corollary

If $T$ is a monad on a slice category $Set/X$, then the category of $T$-algebras is (Barr-)exact. If $T$ is a monad on $Vect$, then $Vect^T$ is exact.

For functors preserving filtered colimits

Returning now to existence of general coequalizers, here is a more difficult and arcane result given in Toposes, Triples, and Theories (theorem 3.9, p. 267):

Proposition

Let $C$ be a category with finite colimits, colimits of chains $\kappa \to C$ (for $\kappa$ an infinite cardinal), and equalizers of arbitrary sets of endomorphisms. If a monad $T : C \to C$ preserves colimits of $\kappa$-chains, then $C^T$ admits coequalizers.

Corollary

If $C$ is complete and cocomplete and $T: C \to C$ preserves filtered colimits, or even just colimits of $\omega$-chains, then $C^T$ is complete and cocomplete.

For locally presentable categories

If $C$ is a locally presentable category and $T$ is an accessible monad (aka a bounded monad, aka a monad with rank) on $C$, then $C^T$ is also locally presentable and in particular cocomplete. Details may be found in Locally presentable and accessible categories.

Algebraic functors have left adjoints

Theorem

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

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

(pulling back a $T$-algebra $(c, \xi: T c \to c)$ to the $S$-algebra $(c, S c \stackrel{\theta c}{\longrightarrow} T c \stackrel{\xi}{\longrightarrow} c)$, thus remembering only underlying $S$-algebra structure) has a left adjoint.

Proof

Since the following diagram is commutative:

$$\begin{array}{cccc}C^T & \overset{C^{\theta}}{\to} & C^S \\ \mathllap{U^T} \downarrow & & \downarrow \mathrlap{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 actually completes the proof, but here is a concrete description of the left adjoint to $C^\theta$: it sends an $S$-algebra $(c, \xi: S c \to c)$ to the (reflexive) coequalizer of the pair

(1)$$\array{ & & T T c & & \\ & \mathllap{T \theta c} \nearrow & & \searrow \mathrlap{\mu c} \\ T S c & & \stackrel{\; \; \; \; \; \; \; \; T \xi \; \; \; \; \; \; \; \; }{\longrightarrow} & & T c }$$

where $\mu: T T \to T$ is the monad multiplication. (If $u: 1_C \to S$ is the unit of $S$, then $T u c: T c \to T S c$ 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 “restriction” functor $Ab^f: Ab^B \to Ab^A$ between module categories (restricting scalar multiplication on a $B$-module along a ring map $f: A \to B$); given an $A$-module $(M, \alpha_M: A \otimes M \to M)$, the $B$-module $B \otimes_A M$ is the coequalizer in $Ab^B$ of

$$\array{ & & B \otimes B \otimes M & & \\ & \mathllap{B \otimes f \otimes M} \nearrow & & \searrow \mathrlap{mult_B \otimes M} \\ B \otimes A \otimes M & & \stackrel{\; \; \; \; \; \; \; \; B \otimes \alpha_M \; \; \; \; \; \; \; \; }{\longrightarrow} & & B \otimes M, }$$

and so the coequalizer of (1) will be denoted $T \circ_S c$ to underline the analogy.

To see that $T \circ_S -$ is the left adjoint, let $(d, \alpha: T d \to d)$ be a $T$-algebra. Any map $f: c \to d$ in $C$ induces a unique $T$-algebra map $\phi: T c \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 $\phi$ coequalizes the pair in (1), i.e., if $\phi$ factors (uniquely) through a $T$-algebra map $T \circ_S c \to d$.

Indeed, assume $f$ is an $S$-algebra map, so we have a commutative diagram

(2)$$\array{ S c & \stackrel{\xi}{\to} & c \\ \mathllap{S f} \downarrow & & \downarrow \mathrlap{f} \\ S d & \underset{\alpha \circ \theta d}{\to} & d. }$$

That $\phi = \alpha \circ T f$ coequalizes the pair of (1) follows by expanding the diagram

(3)$$\array{ T S c & \stackrel{T \theta c}{\to} & T T c & & & & \\ & \mathllap{T \xi} \searrow & \downarrow \mathrlap{\mu c} & & & & \\ & & T c & \underset{T f}{\to} & T d & \underset{\alpha}{\to} & d }$$

to

(4)$$\array{ & & T S d & & & & \\ & \mathllap{T S f} \nearrow & \; \; (nat) & \searrow \mathrlap{T \theta d} & & & \\ T S c & \stackrel{T \theta c}{\to} & T T c & \stackrel{T T f}{\to} & T T d & \stackrel{T \alpha}{\to} & T d \\ & \mathllap{T \xi} \searrow & \downarrow \mathrlap{\mu c} & \; \; (nat) & \downarrow \mathrlap{\mu d} & \; \; (alg) & \downarrow \mathrlap{\alpha} \\ & & T c & \underset{T f}{\to} & T d & \underset{\alpha}{\to} & d }$$

where using (2), the path along the top may be replaced by $T f \circ T \xi: T S c \to T d$, reducing the desired coequalizing of (3) to the tautology $\alpha \circ T f \circ T \xi = \alpha \circ T f \circ T \xi$.

Conversely, assuming the coequalizing of (3), the perimeter of (4) commutes, and on top of that we stack naturality diagrams for the monad unit $\eta$ of $T$:

(5)$$\array{ & & S d & & & & \\ & _\mathllap{S f} \nearrow & _\mathllap{\eta S d} \downarrow & \searrow _\mathrlap{\theta d} & & & \\ S c & (nat) & T S d & (nat) & T d & \stackrel{\alpha}{\to} & d \\ _\mathllap{\eta S c} \downarrow & _\mathllap{T S f} \nearrow & \; \; (nat) & \searrow _\mathrlap{T \theta d} & \downarrow_\mathrlap{\eta T d} & (nat) & \downarrow _\mathrlap{\eta d}\\ T S c & \stackrel{T \theta c}{\to} & T T c & \stackrel{T T f}{\to} & T T d & \stackrel{T \alpha}{\to} & T d \\ & \mathllap{T \xi} \searrow & \downarrow \mathrlap{\mu c} & \; \; (nat) & \downarrow \mathrlap{\mu d} & \; \; (alg) & \downarrow \mathrlap{\alpha} \\ & & T c & \underset{T f}{\to} & T d & \underset{\alpha}{\to} & d }$$

The vertical composite on the right is $1_d$ by a unit equation for a $T$-algebra, and thus we may simplify the perimeter. Retaining the (simplified) perimeter of (5), and inserting some naturality squares and a unit diagram inside, we arrive at the commutative diagram

$$\array{ S c & \stackrel{S f}{\to} & S d & \stackrel{\theta d}{\to} & T d & & \\ _\mathllap{\eta S c} \downarrow & \searrow\; _\mathllap{\xi} & & & & \searrow \mathrlap{\alpha} & \\ T S c & (nat) & c & \stackrel{f}{\to} & d & \stackrel{1_d}{\to} & d \\ & \mathllap{T \xi} \searrow & \downarrow _\mathrlap{\eta c} & (nat) & \downarrow _\mathrlap{\eta d} & (unit) & \downarrow \mathrlap{1_d} \\ & & T c & \underset{T f}{\to} & T d & \underset{\alpha}{\to} & d }$$

where the commutativity of the unlabeled polygonal region is just the commutativity of (2). This completes the proof of the claim.

References

• Fred Linton, Coequalizers in categories of algebras, Seminar on Triples and Categorical Homology Theory: ETH 1966/67. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.

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

• Jiří Adámek and Václav Koubek, Are colimits of algebras simple to construct?, Journal of Algebra, Volume 66, Issue 1 (September 1980), 226-250. (link)