Chapter 5. Monads and Algebras
FC03 — Riehl, Category Theory in Context.
This chapter contains 14 definitions, 4 theorems, 6 propositions, 7 lemmas, 10 corollaries, 9 examples, 1 construction, 2 remarks and 2 other statements.
Nobody has checked this chapter against Lean yet, so the statements below say nothing about whether they are formalized.
Definition 5.1.1
A monad on a category C consists of an endofunctor \(T \colon { \mathsf { C } } \to { \mathsf { C } } ,\) a unit natural transformation η : \(1 \mathsf { c } \Rightarrow T\) , and a multiplication natural transformation µ : \(T ^ { 2 } \Rightarrow T\) 4 so that the following diagrams commute in \({ \sf C } ^ { \complement }\) :
Remark 5.1.2
A monad on \(\mathsf{C}\) is precisely a monoid in the monoidal category \(\mathsf{C}^{\mathsf{C}}\) of endofunctors of \(\mathsf{C}\), where the binary functor \(\mathsf{C}^{\mathsf{C}} \times \mathsf{C}^{\mathsf{C}} \to \mathsf{C}^{\mathsf{C}}\) is composition and the unit object is the identity endofunctor \(1_{\mathsf{C}} \in \mathsf{C}^{\mathsf{C}}\). The category of endofunctors is a strict monoidal category, in which the coherence isomorphisms can be taken to be identities.
Lemma 5.1.3
Any adjunction \(F \dashv U \colon \mathsf{C} \rightleftarrows \mathsf{D}\), with \(\eta \colon 1_{\mathsf{C}} \Rightarrow UF\) and \(\epsilon \colon FU \Rightarrow 1_{\mathsf{D}}\), gives rise to a monad on the category \(\mathsf{C}\) serving as the domain of the left adjoint: the endofunctor is \(T := UF\), the unit \(\eta \colon 1_{\mathsf{C}} \Rightarrow T\) is the unit of the adjunction, and the whiskered counit \(U\epsilon F \colon UFUF \Rightarrow UF\) serves as the multiplication \(\mu \colon T^{2} \Rightarrow T\).
Example 5.1.4
The following monads come from familiar adjunctions. (i) The free-forgetful adjunction between pointed sets and sets of Example 4.1.10(i) induces a monad on \(\mathsf{Set}\) whose endofunctor \((-)_{+} \colon \mathsf{Set} \to \mathsf{Set}\) adds a new disjoint point. The components of the unit are the inclusions \(\eta_{A} \colon A \to A_{+}\); the components of the multiplication \(\mu_{A} \colon (A_{+})_{+} \to A_{+}\) are the identity on the subset \(A\) and send both new points of \((A_{+})_{+}\) to the new point of \(A_{+}\). By Lemma 5.1.3, or by direct verification, the associativity and unit diagrams \[ \mu_{A} \cdot \mu_{A_{+}} = \mu_{A} \cdot (\mu_{A})_{+}, \qquad \mu_{A} \cdot \eta_{A_{+}} = 1_{A_{+}} = \mu_{A} \cdot (\eta_{A})_{+} \] commute. This monad is called the maybe monad, for the reasons explained in Example 5.2.10(i). There is a similar monad on \(\mathsf{Top}\), or on any category with coproducts, adjoining a copy of a fixed object.
Named example
The monad on Set obtained by adjoining a disjoint basepoint is the maybe monad; the analogous construction exists in categories with coproducts.
Named example
Double power-set constructions generalize to continuation monads, replacing the two-element classifier by an arbitrary set.
Example 5.1.5
Monads also arise in nature: (i) The covariant power set functor \(P :\) Set Set is also a monad. The unit \(\eta _ { A } \colon A \to P A\) sends an element to the singleton subset. The multiplication \(\mu _ { A } \colon P ^ { 2 } A \to P A\) takes the union of a set of subsets. Naturality of the unit with respect to a function \(f \colon A \to B\) makes use of the fact that \(f _ { * } \colon P A \to P B\) is the direct image (rather than inverse image) function. Naturality of the multiplication maps makes use of Corollary 4.5.4; the direct image function, as a left adjoint, preserves unions. \[ \begin{array}{c c} A \xrightarrow {\eta_ {A}} P A \ f \Biggl \downarrow & \Biggl \downarrow f _ {*} \ B \xrightarrow {\eta_ {B}} P B \end{array} \qquad \qquad \begin{array}{c c} P ^ {2} A \xrightarrow {\mu_ {A}} P A \ (f _ {*}) _ {*} \Biggl \downarrow & \Biggl \downarrow f _ {*} \ P ^ {2} B \xrightarrow {\mu_ {B}} P B \end{array} \] (ii) A modifica tion of the free monoid monad yields the free commutative monoid monad \[ TA := \bigsqcup_{n \geq 0} (A^{\times n})_{/\Sigma_{n}}, \] whose elements are finite unordered lists of elements of \(A\).
Definition 5.1.6
A comonad on C is a monad on \(\mathsf { C } ^ { \mathrm { o p . } }\) : explicitly, a comonad consists of an endofunctor \(K \colon \mathsf { C } \to \mathsf { C }\) together with natural transformations \(\epsilon \colon K \Rightarrow 1 _ { \mathsf { C } }\) and δ: \(K \Rightarrow K ^ { 2 }\) so that the diagrams dual to Definition 5.1.1 commute in \({ \sf C } ^ { \complement }\)
Example 5.1.7
A monad on a preorder \(( \mathsf { P } , \leq )\) is given by an order-preserving function \(T \colon \mathsf { P } \mathsf { P }\) that is so that \(p \leq T p\) and \(T ^ { 2 } p \leq T p\) . If P is a poset, so that isomorphic objects are equal, these two conditions imply that \(T ^ { 2 } p = T p\) . An order-preserving function T so that \(p \leq T p\) and \(T ^ { 2 } p = T p\) is called a closure operator. Dually, a comonad on a poset category \(( \mathsf { P } , \leq )\) defines a kernel operator: an order-preserving function K so that \(K p \le p\) and \(K p = K ^ { 2 } p\)
Definition 5.2.1
Given a vector space \(V\) over a field \(k\), an affine space is a non-empty set \(A\) together with a translation function \(+ \colon V \times A \to A\) such that \(\vec{0} + \mathbf{a} = \mathbf{a}\) for all \(\mathbf{a} \in A\); \((\vec{v} + \vec{w}) + \mathbf{a} = \vec{v} + (\vec{w} + \mathbf{a})\) for all \(\vec{v}, \vec{w} \in V\) and \(\mathbf{a} \in A\); and, for each \(\mathbf{a} \in A\), the function \(- + \mathbf{a} \colon V \to A\) is a bijection.
Definition 5.2.2
An afine space is a non-empty set A in which afine linear combinations can be evaluated.
Definition 5.2.3
An afine space is an algebra for the afine linear combination monad \(\mathsf { A f f } _ { \mathbb { k } } ( - ) \colon \mathsf { S e t } \to \mathsf { S e t }\)
Definition 5.2.4
Let \(\mathsf{C}\) be a category with a monad \((T,\eta,\mu)\). The Eilenberg–Moore category for \(T\), or category of \(T\)-algebras, is the category \(\mathsf{C}^{T}\) whose objects are pairs \((A \in \mathsf{C},\ a \colon TA \to A)\) for which the diagrams (5.2.5) commute in \(\mathsf{C}\), that is \[ a \cdot \eta_{A} = 1_{A} \qquad\text{and}\qquad a \cdot Ta = a \cdot \mu_{A}, \] and whose morphisms \(f \colon (A,a) \to (B,b)\) are the \(T\)-algebra homomorphisms: maps \(f \colon A \to B\) in \(\mathsf{C}\) for which \(f \cdot a = b \cdot Tf\), with composition and identities as in \(\mathsf{C}\).
Example 5.2.6
For instance: (i) Consider the free pointed set monad of Example 5.1.4(i). An algebra is a set A with a map a : \(A _ { + } \to A\) so that the diagrams (5.2.5) commute. The square imposes no additional conditions, but the triangle asserts that the map a : \(A _ { + } \to A\) restricts to the identity on the A component of the disjoint union \(A _ { + } = A \sqcup { * }\) . Thus, the data of an algebra is a set with a specified basepoint \(a \in A\) , the image of the extra point under the map a : \(A _ { + } \to A\) . A morphism \(f \colon ( A , a ) ( B , b )\) is a map f : A B so that \[ \begin{array}{c} A _ {+} \xrightarrow {f _ {+}} B _ {+} \ \Biggl \downarrow a \ A \xrightarrow {f} B \end{array} \] commutes. The map \(f _ { + }\) carries the extra point in \(A .\) + to the extra point in \(B _ { + }\) , so this condition demands that \(f ( a ) = b\) . In conclusion, the Eilenberg–Moore category is isomorphic to \(\mathtt { S e t } _ { * }\) , the ca tegory of pointed sets.
Construction/comparison
For the monad induced by the free/forgetful R-module adjunction, an algebra structure R⊗_Z A→A is equivalently scalar multiplication satisfying the module axioms.
Lemma 5.2.8
For any monad \(( T , \eta , \mu )\) acting on a category C, there is an adjunction \[ F^{T} \dashv U^{T} \colon \mathsf{C} \rightleftarrows \mathsf{C}^{T} \] between \(\mathsf{C}\) and the Eilenberg–Moore category, whose induced monad is \((T,\eta,\mu)\).
Definition 5.2.9
Let \(\mathsf{C}\) be a category with a monad \((T,\eta,\mu)\). The Kleisli category \(\mathsf{C}_{T}\) has the objects of \(\mathsf{C}\), and a morphism from \(A\) to \(B\) in \(\mathsf{C}_{T}\) is a morphism \(A \to TB\) in \(\mathsf{C}\). The unit \(\eta_{A} \colon A \to TA\) is the identity at \(A\), and the composite of \(f \colon A \to TB\) with \(g \colon B \to TC\) is \[ A \xrightarrow{\ f\ } TB \xrightarrow{\ Tg\ } T^{2}C \xrightarrow{\ \mu_{C}\ } TC. \]
Example 5.2.10
For instance: (i) Objects in the Kleisli category for the maybe monad on Set are sets. A map \(A B\) in the Kleisli category is a function \(A B _ { + }\) , which may be thought of as a partiallydefined function from A to B: the elements of A that are sent to the free basepoint have “undefined” output. The composite of two partial functions is the maximal partially-defined function. Thus, the Kleisli category is the category \({ \mathsf { S e t } } ^ { \partial }\) of sets and partially-defined functions. (ii) Objects in the Kleisli category for the free monoid monad on Set are sets and a map from A to B is a function \(\begin{array} { r } { A \to \coprod _ { n \geq 0 } B ^ { n } } \end{array}\) . For each input element \(a \in A\) , the output is an element \(\begin{array} { r } { ( b _ { 1 } , \dotsc , b _ { k } ) \in \prod _ { n > 0 } B ^ { n } , \mathrm { i . e . } } \end{array}\) , a list of elements of B. (iii) For a fixed set S of “states,”
Lemma 5.2.11
For any monad \(( T , \eta , \mu )\) acting on a category C, there is an adjunction \[ F_{T} \dashv U_{T} \colon \mathsf{C} \rightleftarrows \mathsf{C}_{T} \] between \(\mathsf{C}\) and the Kleisli category, whose induced monad is \((T,\eta,\mu)\).
Proposition 5.2.12
The Kleisli category \(\mathsf { C } _ { T }\) is initial in \(\mathsf { A d j } _ { T }\) and the Eilenberg–Moore category \({ \mathsf { C } } ^ { T }\) is terminal. That is, for any adjunction \(F \to U\) inducing the monad \(( T , \eta , \mu )\) on \(\complement ,\) there exist unique functors \(J \colon \mathsf{C}_{T} \to \mathsf{D}\) and \(K \colon \mathsf{D} \to \mathsf{C}^{T}\) commuting with the left and right adjoints; since they define adjunction morphisms, they are unique.
Lemma 5.2.13
Let \(( T , \eta , \mu )\) be a monad on C. The canonical functor K : \(\mathsf { C } _ { T } \to \mathsf { C } ^ { T }\) from the Kleisli category to the Eilenberg–Moore category is full and faithful and its image consists of the free T -algebras.
Definition 5.2.14
A free T -algebra is an object \[ F ^ {T} c := (T c, \mu_ {c} \colon T ^ {2} c \to T c) \] in the category of algebras that is in the image of the free functor \(F ^ { T } \colon { \mathsf { C } } \to { \mathsf { C } } ^ { T }\)
Definition 5.3.1
An adjunction \(\mathsf { C } _ { } ^ { \frac { F } { \bot } } \mathsf { D }\) is monadic if the canonical comparison functor of Proposition 5.2.12 from D to the category of algebras for the induced monad on C defines an equivalence of categories. A functor \(U \colon \mathsf { D } \mathsf { C }\) is monadic if it admits a left adjoint that defines a monadic adjunction.
Example 5.3.2
The Kleisli adjunction for the maybe monad is identified in Example 5.2.10(i) as the adjunction between the category of sets and the category of sets and partially-defined functions: \[ \text { Set } \xrightarrow {\perp} \text { Set } ^ {\partial}. \] This adjunction is monadic. The associated category of algebras is Set+ and the canonical comparison functor \(\mathsf { S e t } ^ { \partial } \to \mathsf { S e t } _ { + }\) is part of the equivalence of categories described in Example 1.5.6. Many of the monadic functors that one meets in practice, such as the example \(U \colon { \mathsf { A b } } \to\) Set considered above, are in fact strictly monadic, meaning that the canonical comparison functor defines an isomorphism of categories. Whether this comparison functor is an equivalence or an isomorphism will not make a substantial diference to the theory.
Definition: A monad whose multiplication μ:T²⇒T is invertible is an idempotent monad
A monad whose multiplication μ:T²⇒T is invertible is an idempotent monad; reflective subcategories induce such monads.
Proposition 5.3.3
The inclusion \(\mathsf { D } \hookrightarrow \mathsf { C }\) of a reflective subcategory is monadic: that \(i s ,\) the functor \(\mathsf{D} \to \mathsf{C}^{L}\) to the category of algebras for the induced idempotent monad \(L\) is an equivalence of categories.
Proposition 5.4.3
Let \(( T , \eta , \mu )\) be a monad on C and let \(( A , T A \ { \stackrel { \alpha } { \to } } \ A )\) be a T -algebra. Then \[ (T ^ {2} A, \mu_ {T A}) \xrightarrow [ \mu_ {A} ]{T \alpha} (T A, \mu_ {A}) \xrightarrow {\alpha} (A, \alpha)\tag{5.4.4} \] is a coequalizer diagram in \({ \mathsf { C } } ^ { T }\)
Definition 5.4.5
A split coequalizer diagram consists of maps \[ x \xrightarrow [ t ]{f} y \xrightarrow [ s ]{h} z \] so that \(h f = h g , h s = 1 _ { z } , g t = 1 _ { y }\) , and \(f t = s h\) The condition \(h f = h g\) says that this triple of maps defines a fork, i.e., h is a cone under the parallel pair \(f , g \colon x \preceq y\)
Lemma 5.4.6
The underlying fork of a split coequalizer diagram is a coequalizer. Moreover, it is an absolute colimit: any functor preserves this coequalizer.
Example 5.4.7
For any algebra \(( A , \alpha \colon T A \to A )\) for a monad \(( T , \eta , \mu )\) on C, the diagram \[ T^{2}A \ \substack{\xrightarrow{\ T\alpha\ } \\ \xrightarrow{\ \mu_{A}\ }} \ TA \xrightarrow{\ \alpha\ } A \] defines a split coequalizer diagram in \(\mathsf{C}\), with splitting given by \(\eta_{TA}\) and \(\eta_{A}\).
Definition 5.4.8
Given a functor \(U \colon \mathsf { D } \to \mathsf { C }\) A U-split coequalizer is a parallel pair \(f , g \colon x \preceq y\) in D together with an extension of the pair \(U f , U g \colon U x U y\) to a split coequalizer diagram \[ U x \xrightarrow [ t ]{U f} U y \xrightarrow [ s ]{h} z \] in \({ \mathsf { C } } .\)
Proposition 5.4.9
For any monad \(( T , \eta , \mu )\) acting on a category C, the monadic forgetful functor \(U ^ { T } \colon { \mathsf { C } } ^ { T } \to { \mathsf { C } }\) strictly creates coequalizers of UT -split pairs.
Corollary 5.4.10
If \(F \dashv U \colon \mathsf{C} \rightleftarrows \mathsf{D}\) is a monadic adjunction, then (i) \(U \colon \mathsf{D} \to \mathsf{C}\) creates coequalizers of \(U\)-split pairs, and (ii) for any \(D \in \mathsf{D}\) there is a coequalizer diagram \[ FUFUD \ \substack{\xrightarrow{\ FU\epsilon_{D}\ } \\ \xrightarrow{\ \epsilon_{FUD}\ }} \ FUD \xrightarrow{\ \epsilon_{D}\ } D \tag{5.4.11} \] involving the counit \(\epsilon \colon FU \Rightarrow 1_{\mathsf{D}}\) of the adjunction.
Theorem 5.5.1
A right adjoint functor \(U \colon \mathsf { D } \mathsf { C }\) is monadic if and only if it creates coequalizers of U-split pairs.
Corollary 5.5.3
The following categories are monadic over Set via the free forgetful adjunctions described in Example 4.1.10.
Definition 5.5.4
A functor is finitary if it preserves filtered colimits. In particular, a monad \(T \colon { \mathsf { C } } \to { \mathsf { C } }\) is finitary if it preserves filtered colimits in C. If a right adjoint is finitary, then so is its monad because its left adjoint preserves all colimits.
Definition 5.5.5
A category A is a category of models for an algebraic theory if there is a finitary monadic functor \(U \colon \mathsf { A } \to \mathsf { S e t } .\)
Corollary 5.5.6
The underlying set functor U : cHaus Set from the category of compact Hausdorf spaces is monadic.
Example 5.5.7
Other examples of monadic functors include: (i) the forgetful functor \(U \colon \mathsf{Mod}_{R} \to \mathsf{Ab}\) is monadic, by Example 5.2.6(ii), the induced monad on \(\mathsf{Ab}\) being \(R \otimes_{\mathbb{Z}} - \colon \mathsf{Ab} \to \mathsf{Ab}\); (ii) the proof of Corollary 5.5.3 adapts to show that the forgetful functor \(U \colon \mathsf{Ring} \to \mathsf{Ab}\) is monadic, the induced monad on \(\mathsf{Ab}\) being the free ring monad \(TA := \bigoplus_{n \geq 0} A^{\otimes n}\); (iii) if \(\mathsf{C}\) has coproducts (copowers suffice) and \(\mathsf{J}\) is small, then by Exercise 5.5.v the restriction functor \(\mathsf{C}^{\mathsf{J}} \to \mathsf{C}^{\mathrm{ob}\,\mathsf{J}}\), carrying a \(\mathsf{J}\)-indexed diagram to the family of objects in its image, is monadic — for instance the functor \(\mathsf{Vect}_{k}^{\mathsf{B}G} \to \mathsf{Vect}_{k}\) carrying a \(G\)-representation to its underlying vector space, or the analogous functors for \(G\)-objects in any category; (iv) the forgetful functor \(U \colon \mathsf{Cat} \to \mathsf{DirGraph}\) is monadic, its monad forming the underlying graph of the free category on a directed graph, and it factors through the monadic functor \(U \colon \mathsf{Cat} \to \mathsf{rDirGraph}\) onto reflexive directed graphs.
Proposition 5.5.8
\(I f U \colon \mathsf { D } \to \mathsf { C }\) has a left adjoint and if (i) D has coequalizers of reflexive14 pairs, (ii) U preserves coequalizers of reflexive pairs, and (iii) U reflects isomorphisms, then U is monadic.
Theorem 5.5.9
The contravariant power set functor \(P \colon { \mathsf { S e t } } ^ { \mathrm { o p } } \to { \mathsf { S e } }\) t is monadic.
Lemma 5.5.10
For any pullback diagram of monomorphisms, as displayed on the left, the right hand square commutes.
Lemma 5.6.1
\(I f U \colon { \mathsf { A } } \to { \mathsf { C } }\) is monadic, then U reflects isomorphisms: for any morphism \(f \colon a a ^ { \prime }\) in A, if U f is an isomorphism in C, then f is an isomorphism in A.
Corollary 5.6.2
Any bijective continuous function between compact Hausdorf spaces is a homeomorphism.17
Remark 5.6.3
Unlike the other corollaries listed in the introduction, this is not the most eficient proof that bijective continuous functions between compact Hausdorf spaces are homeomorphisms,18 but we submit that this roundabout proof of Corollary 5.6.2 is nonetheless interesting. By monadicity of the functor U : cHaus Set and Proposition 5.4.3, any compact Hausdorf space is canonically a quotient of the Stone–Čech compactification of its underlying set. A continuous bijection induces a natural isomorphism between the Stone–Čech compactifications, and thus a homeomorphism between the canonical quotients.
Corollary 5.6.4
Any bijective homomorphism in a category of models for an algebraic theory is an isomorphism.
Theorem 5.6.5
A monadic functor \(U \colon \mathsf { A } \to \mathsf { C }\) creates (i) any limits that C has, and (ii) any colimits that C has and the monad and its square preserve.
Corollary 5.6.6
The inclusion of a reflective subcategory creates all limits. In particular, a reflective subcategory of a complete category is complete.
Corollary 5.6.7
Any category that is monadic over Set is complete, with limits created by the monadic forgetful functor.
Example 5.6.8
For instance, the p-adic integers are defined to be the limit of an \(\psi ^ { \mathrm { o p } } .\) indexed diagram of rings \[ \mathbb{Z}_{p} := \lim_{n} \left( \cdots \to \mathbb{Z}/p^{3} \to \mathbb{Z}/p^{2} \to \mathbb{Z}/p \right). \]
Corollary 5.6.9
Set is cocomplete.
Corollary 5.6.10
Mo \(| _ { R } \to \mathsf { A b }\) creates all colimits that Ab admits.
Proposition 5.6.11
Suppose C is cocomplete and \(U \colon \mathsf { A } \to \mathsf { C }\) is monadic. Then the following are equivalent: (i) A is cocomplete. (ii) A has coequalizers.
Theorem 5.6.12
\(I f T \colon { \mathsf { C } } \to { \mathsf { C } }\) is a finitary monad on a complete and cocomplete, locally small category C, then the category \({ \mathsf { C } } ^ { T }\) of T -algebras is also complete and cocomplete.
Corollary 5.6.14
Any category of models for an algebraic theory is cocomplete. While the monad \(\beta\) for compact Hausdorf spaces is not finitary, the category cHaus is nonetheless cocomplete. Example 4.5.14(i) observes that compact Hausdorf spaces form a reflective subcategory of Top. The claim follows from Propositions 3.5.2 and 4.5.15.