nLab colimits in categories of algebras

Redirected from "cocompleteness of categories of algebras".
Contents

Context

Limits and colimits

Higher algebra

Contents

Introduction

Let TT be a monad on a category CC, and let C TC^T denote the Eilenberg-Moore category of TT, i.e., the category of TT-algebras. Let

U:C TCU: C^T \to C

be the usual underlying or forgetful functor, with left adjoint F:CC TF: C \to C^T, unit η:1 CUF\eta: 1_C \to U F, and counit ε:FU1 C T\varepsilon: F U \to 1_{C^T}. It is well-known that UU reflects limits, so that if CC is complete, then C TC^T is also complete and UU is continuous.

The situation with regard to colimits is more complicated. It is not generally true that if CC is cocomplete, then C TC^T is also. (See Adámek & Koubek, III.10, for an example when C=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 JJ is a small category, and suppose that the functors TT and TTT \circ T preserve colimits over JJ, that is, suppose that for every F:JCF: J \to C the canonical map

colim JTFT(colim JF)colim_J T \circ F \to T(colim_J F)

is an isomorphism, and similarly for TTT \circ T.

Proposition

Under these hypotheses, U:C TCU: C^T \to C creates colimits over JJ.

For a proof, see Proposition 4.3.2 of Handbook of Categorical Algebra (Volume 2).

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

010,0 \to 1 \stackrel{\longrightarrow}{\longrightarrow} 0,

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

The following very useful observation was first made by Linton.

Theorem

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

Proof

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

FUc FηUc FUFUc FξεFUc FUc\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 TC^T has coproducts, let (c i,ξ i)(c_i, \xi_i) be a collection of algebras. Then F( iUc i)F(\sum_i U c_i) is the coproduct iFUc i\sum_i F U c_i in C TC^T (since FF preserves coproducts and CC has them). We have a reflexive fork

iFUc i iFηUc i iFUFUc i iFξ i iεFUc i iFUc i\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 TC^T of this diagram is the coproduct ic i\sum_i c_i.

Finally, general coequalizers in C TC^T are constructed from coproducts and reflexive coequalizers: given a parallel pair f,g:cdf, g: c \stackrel{\longrightarrow}{\longrightarrow} d in C TC^T, the coequalizer of ff and gg is the colimit of the reflexive fork

d c+d (g,1 d)(f,1 d) d\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 TT is a monad on a complete and cocomplete category CC that preserves reflexive coequalizers, then C TC^T is complete and cocomplete.

The hypotheses of the preceding corollary hold when CC is a complete, cocomplete, cartesian closed category and TT is the monad corresponding to a finitary algebraic theory. (The key observation being that the finitary power functors xx nx \mapsto x^n preserve reflexive coequalizers if CC is cartesian closed.)

Corollary

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

Proof

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

R=f,g:AB×BR = \langle f, g \rangle: A \to B \times B

and then let EE be the smallest TT-congruence (equivalence relation that is a TT-subalgebra map EB×BE \hookrightarrow B \times B) through which RR factors. (This is the intersection of all TT-congruences through which RR factors, and may be calculated in SetSet, where it is reflected in TT-AlgAlg since U:Set TSetU: Set^T \to Set reflects arbitrary intersections.) The coequalizer as calculated in SetSet,

UE Uπ 2Uπ 1 UB p Q\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 SetSet is a split coequalizer. (This requires the axiom of choice. A splitting is given by any splitting i:QUBi: Q \to U B of pp, which picks a representative in each equivalence class, together with ip,1:UBUE\langle i p, 1 \rangle: U B \to U E.) The proof is completed by the following lemma.

Lemma

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

Proof

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

TUE TUπ 2TUπ 1 TUB Tp TQ UE Uπ 2Uπ 1 UB p Q\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 C T\mathbf{C}^T. The last vertical arrow making the diagram commute gives QQ a TT-algebra structure, and the split coequalizer in the bottom row is thereby reflected in C T\mathbf{C}^T (i.e., lifts to a coequalizer in C T\mathbf{C}^T, albeit not necessarily to one that is itself split).

Categories of algebras are Barr exact

Theorem

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

Proof

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

UE Uπ 2Uπ 1 UB q Q\array{ U E & \stackrel{\overset{U\pi_1}{\longrightarrow}}{\underset{U\pi_2}{\longrightarrow}} & U B & \stackrel{q}{\longrightarrow} & Q}

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

That regular epis in C T\mathbf{C}^T are stable under pullback follows a similar line of reasoning: let p:BPp: B \to P be a regular epi in C T\mathbf{C}^T. It is the coequalizer of its kernel pair π 1,π 2:EB\pi_1, \pi_2: E \rightrightarrows B. We just calculated that the coequalizer q:UBQq: U B \to Q of Uπ 1,Uπ 2U\pi_1, U\pi_2 in C\mathbf{C} lifts to C T\mathbf{C}^T, so that QQ is identified with UPU P and qq with UpU p. Thus UpU p is a regular epi in C\mathbf{C}. Now if f:APf: A \to P is a map in C T\mathbf{C}^T, and b=f *pb = f^\ast p is the pullback of pp along ff (with kernel pair ker(b)\ker(b)), then UbU b is the pullback of UpU p along UfU f since UU preserves pullbacks, and so UbU b is a regular epi since C\mathbf{C} is regular. This UbU b is the coequalizer of its kernel pair, and splits, so by Lemma , its lift bb is the coequalizer of ker(b)\ker(b). Thus regular epis in C T\mathbf{C}^T are stable under pullback.

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

UE Uπ 2Uπ 1 UB q Q\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 C T\mathbf{C}^T, and since kernel pairs are preserved and reflected by U:C TCU: \mathbf{C}^T \to \mathbf{C}, we conclude that π 1,π 2\pi_1, \pi_2 is the kernel pair of the lifted regular epi over qq.

Corollary

If TT is a monad on a slice category Set/XSet/X, then the category of TT-algebras is (Barr-)exact. If TT is a monad on VectVect, then Vect TVect^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

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

Corollary

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

For locally presentable categories

If CC is a locally presentable category and TT is an accessible monad (aka a bounded monad, aka a monad with rank) on CC, then C TC^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 θ:ST\theta: S \to T is a morphism of monads on CC, and suppose that C TC^T has coequalizers. Then the induced algebraic functor

C θ:C TC SC^\theta: C^T \to C^S

(pulling back a TT-algebra (c,ξ:Tcc)(c, \xi: T c \to c) to the SS-algebra (c,ScθcTcξc)(c, S c \stackrel{\theta c}{\longrightarrow} T c \stackrel{\xi}{\longrightarrow} c), thus remembering only underlying SS-algebra structure) has a left adjoint.

Proof

Since the following diagram is commutative:

C T C θ C S U T U S C = C \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 TC^T has coequalizers of reflexive pairs, then C θ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 θC^\theta: it sends an SS-algebra (c,ξ:Scc)(c, \xi: S c \to c) to the (reflexive) coequalizer of the pair

(1) TTc Tθc μc TSc Tξ Tc\array{ & & T T c & & \\ & \mathllap{T \theta c} \nearrow & & \searrow \mathrlap{\mu c} \\ T S c & & \stackrel{\; \; \; \; \; \; \; \; T \xi \; \; \; \; \; \; \; \; }{\longrightarrow} & & T c }

where μ:TTT\mu: T T \to T is the monad multiplication. (If u:1 CSu: 1_C \to S is the unit of SS, then Tuc:TcTScT 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 AB \otimes_A - to the “restriction” functor Ab f:Ab BAb AAb^f: Ab^B \to Ab^A between module categories (restricting scalar multiplication on a BB-module along a ring map f:ABf: A \to B); given an AA-module (M,α M:AMM)(M, \alpha_M: A \otimes M \to M), the BB-module B AMB \otimes_A M is the coequalizer in Ab BAb^B of

BBM BfM mult BM BAM Bα M BM,\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 ScT \circ_S c to underline the analogy.

To see that T ST \circ_S - is the left adjoint, let (d,α:Tdd)(d, \alpha: T d \to d) be a TT-algebra. Any map f:cdf: c \to d in CC induces a unique TT-algebra map ϕ:Tcd\phi: T c \to d:

ϕ=(TcTfTdαd)\phi = (T c \stackrel{T f}{\to} T d \stackrel{\alpha}{\to} d)

and the claim is that f:cdf: c \to d is an SS-algebra map cC θ(d)c \to C^\theta(d) if and only if ϕ\phi coequalizes the pair in (1), i.e., if ϕ\phi factors (uniquely) through a TT-algebra map T ScdT \circ_S c \to d.

Indeed, assume ff is an SS-algebra map, so we have a commutative diagram

(2)Sc ξ c Sf f Sd αθd d.\array{ S c & \stackrel{\xi}{\to} & c \\ \mathllap{S f} \downarrow & & \downarrow \mathrlap{f} \\ S d & \underset{\alpha \circ \theta d}{\to} & d. }

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

(3)TSc Tθc TTc Tξ μc Tc Tf Td α d \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) TSd TSf (nat) Tθd TSc Tθc TTc TTf TTd Tα Td Tξ μc (nat) μd (alg) α Tc Tf Td α d\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 TfTξ:TScTdT f \circ T \xi: T S c \to T d, reducing the desired coequalizing of (3) to the tautology αTfTξ=αTfTξ\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 TT:

(5) Sd Sf ηSd θd Sc (nat) TSd (nat) Td α d ηSc TSf (nat) Tθd ηTd (nat) ηd TSc Tθc TTc TTf TTd Tα Td Tξ μc (nat) μd (alg) α Tc Tf Td α d\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 d1_d by a unit equation for a TT-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

Sc Sf Sd θd Td ηSc ξ α TSc (nat) c f d 1 d d Tξ ηc (nat) ηd (unit) 1 d Tc Tf Td α d\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

  • 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)

Last revised on December 21, 2023 at 02:37:29. See the history of this page for a list of all contributions to it.