Monads - Category Theory - Cambridge III notes

5 Monads

Suppose we have $C ⇄_{G}^{F} D$ , $(F ⊣ G)$ . How much of the adjunction can we describe in terms of $C$ (supposing we can’t know anything about $D$ , or know very little about it)?

We have:

The functor $T = G F : C \to C$ .
The unit $η : 1_{C} \to T$ .
The natural transformation $μ = G 𝜀_{F} : T T \to T$ .

From the triangular identities of Theorem 3.7, we obtain the commutative triangles:

and from naturality of

𝜀

we obtain

Definition 5.1 (Monad). A monad on a category $C$ is a triple $(T, η, μ) = 𝕋$ where $T : C \to C$ , and $η : 1_{C} \to T$ and $μ : T T \to T$ satisfy the commutative diagrams

Example 5.2.

(a) Let $M$ be a monoid. The functor $M \times (∙) : S e t \to S e t$ has a monad structure: $η_{A} : A \to M \times A$ is $a \mapsto (1, a)$ and $μ_{A} : M \times M \times A \to M \times A$ sends $(m, m^{'}, a)$ to $(m m^{'}, a)$ . The three diagrams ‘are’ the unit and associative laws in $M$ .
(b) The functor $P : S e t \to S e t$ has a monad structure: the unit $η_{A} : A \to P A$ is the mapping $a \mapsto {a}$ (Example 1.7(c)) and the multiplication $μ_{A} : P P A \to P A$ sends a set of subsets of $A$ to their union.

Does every monad come from an adjunction?

Answered by Eilenberg-Moore and by Kleisli (1965).

Note that the monad of Example 5.2(a) is induced by $S e t ⇄_{U}^{M \times (∙)} [M, S e t]$ and that of Example 5.2(b) is induced by $S e t ⇄_{U}^{P} C S L a t t$ , where $C S L a t t$ is the category of complete semilattices (posets, with arbitrary joins). The free complete semilattice on $A$ is $P (A)$ : every $f : A \to U S$ extends uniquely to $\bar{f} : P (A) \to S$ where $\bar{f} (A^{'}) = \lor {f (a) | a \in A^{'}}$ .

An $M$ -set (respectively a complete semilattice) is a set $A$ equipped with a suitable mapping $M \times A \to A$ (respectively $P (A) \overset{\lor}{\to} A$ ).

Definition 5.3 (Eilenberg-Moore algebra). Let $𝕋 = (T, η, μ)$ be a monad on $C$ . By an Eilenberg-Moore algebra for $𝕋$ we mean a pair $(A, α)$ where $A \in ob C$ and $α : T A \to A$ satisfies

A TA TTA T A

(4) : ηA1Aα A(5) : TμαααA TA A

A homomorphism

f : (A, α) \to (B, β)

is a morphism

f : A \to B

satisfying

We write

C^{𝕋}

for the category of

𝕋

-algebras and homomorphisms.

Proposition 5.4. Assuming that:

$C$ a category
$𝕋$ a monad

Then the forgetful functor

C^{𝕋} \overset{G^{𝕋}}{\to} C

has a left adjoint

F^{𝕋}

, and the adjunction induces the monad

𝕋

Proof. We define $F^{𝕋} A = (T A, μ_{A})$ (an algebra by (2) and (3)) and $F^{𝕋} (A \overset{f}{\to} B) = T f$ (a homomorphism by naturality of $μ$ ). Clearly, $F^{𝕋}$ is functorial and $G^{𝕋} F^{𝕋} = T$ .

We establish the adjunction using Theorem 3.7: its unit is $η$ , and the counit $𝜀_{(A, α)}$ is just $α$ (a homomorphism $F^{𝕋} A \to (A, α)$ , by (5), and natural by (6)).

The triangular identity

is just (1), and

is (4).

Finally, $G 𝜀_{F^{𝕋} A} = μ$ by definition of $F^{𝕋} A$ . So the adjunction induces $(T, η, μ)$ . □

Note: $C ⇄_{G}^{F} D$ induces $𝕋$ , we can replace $D$ by its full subcategory on objects $F A$ .

So in trying to construct $D$ , we may assume $F$ is surjective (indeed, bijective) on objects. The morphisms $F A \to F B$ in $D$ must correspond to morphisms $A \to G F B = T B$ in $C$ .

Definition 5.5 (Kleisli category). Let $𝕋$ be a monad on $C$ . The Kleisli category $C_{𝕋}$ is defined by $ob C_{𝕋} = ob C$ , morphsims $A \overset{f}{\to} B$ in $C_{𝕋}$ are morphisms $A \overset{f}{\to} T B$ in $C$ . The identity $A \overset{}{\to} A$ is $A \overset{η_{A}}{\to} T A$ , and the composite of $A \overset{f}{\to} B \overset{g}{\to} C$ is $A \overset{f}{\to} T B \overset{T g}{\to} T T C \overset{μ_{C}}{\to} T C$ .

For the unit and associative laws, consider the diagrams

A TB TTC TT TD T TD

fTTμTμμTμgTCμTDhDhDD TC TT D T D

Proposition 5.6. Assuming that:

$C$ a category
$𝕋$ a monad

Then there is an adjunction

C ⇄_{G_{𝕋}}^{F_{𝕋}} C_{𝕋}

inducing the monad

𝕋

Proof. We define $F_{𝕋} A = A$ and $F_{𝕋} (A \overset{f}{\to} B) = A \overset{f}{\to} B \overset{η_{B}}{\to} T B$ . $F_{𝕋}$ preserves identities by definintion, and preserves composition by

A B TB

C TC T TC

fg1gTηT1μfBgC1TCCC T C

We define

G_{𝕋} A = T A

, and

G_{𝕋} (A \overset{f}{\to} B) = T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B

G_{𝕋}

preserves identities by (1), and preserves composites by

T A TT B T TTC T TC

TTμTμμTμfTBμTCgCgCC TB T TC T C

We verify the adjunction using Theorem 3.7:

G_{𝕋} F_{𝕋} (f) = T f

by (1) so

G_{𝕋} F_{𝕋} = T

and we take

η

as unit of the adjunction.

We define $T A \overset{𝜀_{A}}{\to} A$ to be $T A \overset{1_{T A}}{\to} T A$ . To verify the naturality square

the lower composite is

T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B

and the upper one is

T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B \overset{η_{T B}}{\to} T T B \overset{μ_{B}}{\to} T B

, which agree since (2) tells us that

μ_{B} η_{T B} = 1_{B}

The triangular identities become

F𝜀𝕋FηAFA 𝕋A F= GF A FA ηTηT1TηTATTATAAA TTA TTT A TT A

and

Finally,

G_{𝕋} 𝜀_{F_{𝕋} A} = μ_{A}

, so

(F_{𝕋} ⊣ G_{𝕋})

induces the monad

𝕋

. □

Given a monad $𝕋$ on $C$ , we write $Adj (𝕋)$ for the category whose objects are adjunctions $(C ⇄_{G}^{F} D)$ inducing $𝕋$ , and morphisms $(C ⇄_{G}^{F} D) \to (C ⇄_{G^{'}}^{F^{'}} D^{'})$ are functors $D \overset{K}{\to} D^{'}$ satisfying $K F = F^{'}$ and $G^{'} K = G$ .

Theorem 5.7. The Kleisli adjunction $(C ⇄_{}^{} C_{𝕋})$ is an initial object of $Adj (𝕋)$ , and the Eilenberg-Moore adjunction $(C ⇄_{}^{} C^{𝕋}$ is terminal.

Proof. Suppose given $(C ⇄_{G}^{F} D)$ in $Adj (𝕋)$ . We define $K : D \to C^{𝕋}$ by $K B = (G B, G 𝜀_{B})$ (an algebra by one of the triangular identities for $η$ and $𝜀$ , and naturality of $𝜀$ ), $K (B \overset{g}{\to} B^{'}) = G g$ (a homomorphism by naturality of $𝜀$ ). $K$ is functorial since $G$ is, $G^{𝕋} K = G$ is obvious, and $K F A = (G F A, G 𝜀_{F A}) = (T A, μ_{A}) = F^{𝕋} A$ .

So $K$ is a morphism of $Adj (𝕋)$ .

Suppose $K^{'} : D \to C^{𝕋}$ is another such: then we must have $K^{'} B = (G B, β_{B})$ where $β : G F G \to G$ is a natural transformation since $K^{'} g = G g$ is a homomorphism $K^{'} B \to K^{'} B^{'}$ for all $g : B \to B^{'}$ . Also, since $K^{'} F = F^{𝕋}$ , we have $β_{F A} = μ_{A} = G 𝜀_{F A}$ for all $A$ .

For any $B$ , we have naturality squares

GF GF GB GF GB

GGβGβGF𝜀F𝜀B𝜀GFGBB𝜀GBBBGF GB GB

whose left edges are equal, and whose top edge is split epic, so we obtain

G 𝜀_{B} = β_{B}

for all

B

. So

K^{'} = K

We define $H : C_{𝕋} \to D$ by $H A = F A$ and $H (A \overset{f}{\to} B) = F A \overset{F f}{\to} F G F B \overset{𝜀_{F B}}{\to} F B$ . $H$ preserves identities and satisfies $H F_{𝕋} = F$ , by the first triangular identity for $η$ and $𝜀$ .

$H$ preserves the composite $A \overset{f}{\to} B \overset{g}{\to} C$ by

F A FGF B FGF GF C F GF C

FF𝜀F𝜀𝜀F𝜀fGFGFFgFFB𝜀GCCFFgCC FB FGF C F C

Also

G H A = G F A = T A = G_{𝕋} A

and

G H (A \overset{f}{\to} B) = (T A \overset{T f}{\to} T T B \overset{μ_{B}}{\to} T B) = G_{𝕋} (A \overset{f}{\to} B) .

So $H$ is a morphism of $Adj (𝕋)$ . Note that $H$ is full and faithful, since it sends $A \overset{f}{\to} G F B$ to its traspose across $(F ⊣ G)$ .

If $H^{'} : C_{𝕋} \to D$ is any morphism of $Adj (𝕋)$ , we must have $H^{'} A = F A = H A$ for all $A$ , and since $G H^{'} = G_{𝕋}$ and the adjunctions have the same unit, $H^{'}$ must send the transpose $A \overset{f}{\to} B$ of $A \overset{f}{\to} G F B$ to its transpose across $(F ⊣ G)$ . So $H^{'} = H$ . □

$C_{𝕋}$ has coproducts if $C$ does, but has few other limits or colimits. In contrast, we have:

Proposition 5.8. Assuming that:

$𝕋$ a monad on $C$

Then

(i) The forgetful functor $G^{𝕋} : C^{𝕋} \to C$ creates all limits which exist in $C$ .
(ii) If $C$ has colimits of shape $J$ , then $G^{𝕋}$ creates colimits of shape $J$ if and only if $T$ preserves them.

Proof.

(i) Suppose given $D : J \to C^{𝕋}$ ; write $D (j) = (G D (j), δ_{j})$ , and let $(L, (λ_{j} : L \to G D (j) | j \in ob J))$ be a limit for $G D$ . The composites $T L \overset{T λ_{j}}{\to} T G D (j) \overset{δ_{j}}{\to} G D (j)$ form a cone over $G B$ . So they induce a unique $λ : T L \to L$ . And $λ$ is a $𝕋$ -algebra structure on $L$ , since the identities $λ η_{L} = 1_{L}$ and $λ (T λ) = λ μ_{L}$ follow from uniqueness of factorisations through limits and it’s the unique lifting of the limit cone in $C$ to a cone in $C^{𝕋}$ . The fact that it’s a limit cone is straightforward.
(ii) If $G^{𝕋}$ creates colimits then it preserves them, but so does $F^{𝕋}$ since it’s a left adjoint, so $T$ preserves them too.
Conversely, given $D : J \to C^{𝕋}$ and a colimit cone $(G D (j) \overset{λ_{j}}{\to} L | j \in ob J)$ under $G D$ , we need to know that $(T G D (j) \overset{T λ_{j}}{\to} T L | j \in ob J)$ is a colimit cone to obtain $T L \overset{λ}{\to} L$ (and that $T T L$ is a colimit to verify that $λ$ is a $𝕋$ -algebra structure). Otherwise, the argument is as before. □

Given $(C ⇄_{G}^{F} D)$ , $(F ⊣ G)$ , how can we tell when $K : D \to C^{𝕋}$ is part of an equivalence?

Note: $H : C_{𝕋} \to D$ is an equivalence if and only if $F$ is essentially surjective.

We call $(F ⊣ F)$ (or the functor $G$ ) monadic if $K : D \to C^{𝕋}$ is part of an equivalence.

Lemma 5.9. Assuming that:

$C ⇄_{G}^{F} D$ is an adjunction inducing the monad $𝕋$ on $C$
for every $𝕋$ algebra $(A, α)$ , the pair $F G F A ⇉_{𝜀_{F A}}^{F α} F A$ has a coequaliser in $D$

Then

K : D \to C^{𝕋}

has a left adjoint

L

Proof. Write $F A \overset{λ_{(A, α)}}{\to} L (A, α)$ for the coequaliser. For any homomorphism $f : (A, α) \to (B, β)$ the two left hand squares in

FGF A F A L (A, α)

F𝜀FFλFLF𝜀FλαAG(AffβB(BF,,fα)β)FGF B F B L (B, β)

commute, so we get a unique

L f

making the right hand square commute. As usual, uniqueness implies functoriality of

L

For any $B \in ob D$ , morphisms $L (A, α) \to B$ correspond to morphisms $F A \overset{f}{\to} B$ satisfying $f (F α) = f 𝜀_{F A}$ . If $\bar{f} : A \to G B$ is the transpose of $f$ across $(F ⊣ G)$ , then $f (F α)$ transposes to $\bar{f} α : G F A \to G B$ , whereas $f 𝜀_{F A}$ transposes to $G f$ . But we can write $f = 𝜀_{B} (F \bar{f})$ by the proof of Theorem 3.7, so $G f = (G 𝜀_{B}) (G F \bar{f})$ . So $f (F α) = f 𝜀_{F A}$ if and only if

commutes, which happens if and only if

\bar{f} : (A, α) \to K B

C^{𝕋}

Naturality of the bijection follows from that of $f \mapsto \bar{f}$ . □

Note that since $G 𝕋 K = G$ , we have $L F^{𝕋} ≅ F$ by Corollary 3.6, and $L$ preserves coequalisers.

Definition 5.10 (Reflexive / split coequaliser diagram / $G$ -split).

(a)
We say a parallel pair $A ⇉_{g}^{f} B$ is reflexive if there exists $r : B \to A$ with $f r = g r = 1_{B}$ . Note that $F G F A ⇉_{𝜀_{F A}}^{F α} F A$ is reflexive, with common right inverse $F A \overset{F η_{A}}{\to} F G F A$ .
(b)
By a split coequaliser diagram, we mean a diagram
satisfying $h f = h g$ , $h s = 1_{C}$ , $g t = 1_{B}$ and $f t = s h$ . If these hold, then $h$ is a coequaliser of $(f, g)$ since if $B \overset{k}{\to} D$ satisfies $k f = k g$ then $k = k g t = k f t = k s h$ , so $k$ factors through $h$ , and the factorisation is unique since $h$ is (split) epic. Note that any functor preserves split coequalisers.
(c)
Given $G : D \to C$ , we say a pair $A ⇉_{g}^{f} B$ in $D$ is $G$ -split if there’s a split coequaliser diagram
in $C$ . The pair $(F α, 𝜀_{F A})$ in Lemma 5.9 is $G$ -split, since
is a split coequaliser diagram in $C$ .

Theorem 5.11 (Precise Monadicity Theorem). A functor $G : D \to C$ is monadic if and only if $G$ has a left adjoint and creates coequaliser of $G$ -split pairs in $D$ .

Theorem 5.12 (Crude Monadicity Theorem). Assuming that:

$G : D \to C$ preserves reflexive coequalisers
$G$ has a left adjoint
$G$ reflects isomorphisms
$D$ has reflexive coequalisers

Then

G

is monadic.

Proof.

(5.11, $\Rightarrow$ ) Necessity of $F ⊣ G$ is obvious. For the other condition, it’s enough to show that $G^{𝕋} : C^{𝕋} \to C$ creates coequalisers of $G^{𝕋}$ -split pairs. This is a re-run of Proposition 5.8(ii): if $(A, α) ⇉_{g}^{f} (B, β)$ are such that
is a split coequaliser diagram, the coequaliser is preserved by $T$ and by $T T$ , so $C$ acquires a unique algebra structure $T C \overset{γ}{\to} C$ making $h$ a homomorphism, and $h$ is a coequaliser in $C^{𝕋}$ .
(5.11 $\Leftarrow$ and 5.12) Either set of hypotheses implies that $D$ has the coequalisers needed for Lemma 5.9, so $K$ has a left adjoint $L$ . So we need to show that the unit and counit of $(L ⊣ K)$ are isomorphisms.
The unit $(A, α) \to K L (A, α)$ is the factorisation of $G λ_{(A, α)} : G F A \to G L (A, α)$ through the ( $G^{𝕋}$ -split) coequaliser $G F A \overset{α}{\to} A$ of $G F G F A ⇉_{G 𝜀_{F A}}^{G F α} G F A$ . But either set of hypothesis implies that $G$ preserves the equaliser of $(F α, 𝜀_{F A})$ , so this factorisation is an isomorphism.

The counit $L K B \to B$ is the factorisation of $F G B \overset{𝜀_{B}}{\to} B$ through the coequaliser of $F G F G B ⇉_{𝜀_{F G B}}^{F G 𝜀_{B}} F G B$ . The hypotheses of Theorem 5.11 imply that $𝜀_{B}$ is a coequaliser of this pair, so the counit is an isomorphism. Those of Theorem 5.12 imply that the factorisation is mapped to an isomorphism by $G$ , so it’s an isomorphism. □

Remark 5.13.

(1) Reflexive coequalisers are colimits of shape $J$ , where $J$ is the category
satisfying $f r = g r = 1_{}$ , $r f = s$ and $r g = t$ .
(2) All colimits can be constructed from coproducts and reflexive coequalisers. This was proved in Proposition 4.4: the pair $P ⇉_{g}^{f} Q$ appearing in that proof is coreflexive with common left inverse $r : Q \to P$ defined by $π_{j} r = π_{1_{j}}$ for all $j$ .
(3) If $A ⇉_{g}^{f} B$ is reflexive, then in any commutative square
we have $h = h f r = k g r = k$ . So a pushout for
is a coequaliser for $A ⇉_{g}^{f} B$ .
(4) In $S e t$ , or more generally in a cartesian closed category, if $A_{i} ⇉_{g_{i}}^{f_{i}} B_{i} \overset{h_{i}}{\to} C_{i}$ ( $i = 1, 2$ ) are reflexive coequalisers, then $A_{1} \times A_{2} ⇉_{g_{1} \times g_{2}}^{f_{1} \times f_{2}} B_{1} \times B_{2} \overset{h_{1} \times h_{2}}{\to} C_{1} \times C_{2}$ is also a coequaliser. To see this, consider
in which all rows and columns are coequalisers. Then the lower right square is a pushout; but if $B_{1} \times B_{2} \overset{k}{\to} D$ coequalises $A_{1} \times A_{2} ⇉_{g_{1} \times g_{2}}^{f_{1} \times f_{2}} B_{1} \times B_{2}$ , then is also coequalises $A_{1} \times B_{2} ⇉_{}^{} B_{1} \times B_{2}$ and $B_{1} \times A_{2} ⇉_{}^{} B_{1} \times B_{2}$ , so if factors through the top and left edges of the lower right square, and hence through $B_{1} \times B_{2} \overset{h_{1} \times h_{2}}{\to} C_{1} \times C_{2}$ .

Example 5.14.

(a) The forgetful functor $G p \to S e t$ is monadic, and satisfies the hypotheses of Theorem 5.12. If $G ⇉_{g}^{f} H$ is a reflexive pair in $G p$ , with coequaliser $H \overset{h}{\to} K$ in $S e t$ , then $G \times G ⇉_{}^{} H \times H \to K \times K$ is a coequaliser, so the multiplication $H \times H \to H$ induces a binary operation $K \times K \to K$ , which is the unique group multiplication on $K$ making $h$ a homomorphism, and it makes $h$ into a coequaliser in $G p$ .
The same argument works for $A b G p$ , $R n g$ , $L a t$ , $D L a t$ , ….

It doesn’t work for categories like $C S L a t$ or $C L a t$ , but here we can use Theorem 5.11 provided the forgetful functor has a left adjoint.
(b) Any reflection is monadic: this can be proved using Theorem 5.11. If $D \subseteq C$ is a reflective subcategory, and $A ⇉_{g}^{f} B$ is a pair in $D$ for which there exists
in $C$ satisfying the equaitions of Definition 5.10(b), then $t \in mor D$ since $D$ is full, so $f t = s h$ is in $D$ , but $D$ is closed under splittings of idempotents by Example 4.7(d), so $h$ belongs to it.
(c) Consider the composite adjunction
where $(L ⊣ I)$ is the adjunction of Example 3.11(b). The two factors are monadic, but the composite isn’t since free abelian groups are torsion free, so $G I L F ≃ G F$ and its category of algebras is $≅ A b G p$ .
(d) The contravariant power-set functor $P^{*} : {S e t}^{o p} \to S e t$ is monadic, and satisfies the hypotheses of Theorem 5.12. Its left adjoint is $P^{*} : S e t \to {S e t}^{o p}$ by Example 3.2(i), and it reflects isomorphisms by Example 2.9(a).
Let $E \overset{e}{\to} A ⇉_{g}^{f} B$ be a coreflexive equaliser diagram in $S e t$ . Then
is a pullback by Remark 5.13(c), so
commutes. But we also have $(P^{*} e) (P e) = 1_{P E}$ and $(P^{*} f) (P f) = 1_{P B}$ since $e$ and $f$ are injective, so
is a split coequaliser diagram.
(e) The fogetful functor $T o p \overset{U}{\to} S e t$ is not monadic; the monad on $S e t$ induced by $(D ⊣ U)$ is $(1_{S e t}, 1_{1_{S e t}}, 1_{1_{S e t}})$ so its category of algebras is $≅ S e t$ .
(f) The composite adjunction
is monadic. We’ll prove this using Theorem 5.11: suppose given $X ⇉_{g}^{f} Y$ in $K H a u s$ and a split coequaliser
in $S e t$ . The quotient topology on $Z$ is the unique topology making $h$ into a coequaliser in $T o p$ , and it’s compact, so $h$ will be a coequaliser in $K H a u s$ provided $Z$ is Hausdorff. It is also the unique topology that could make $h$ into a morphism of $K H a u s$ .
But, given an equivalence relation $S$ on a compact Hausdorff space $Y$ , $Y ∕ S$ is Hausdorff if and only if $S$ is closed in $Y \times Y$ .

In our case, if $(y_{1}, y_{2}) \in S$ (i.e. $h (y_{1}) = h (y_{2})$ ) then $x_{1} = t (y_{1})$ and $x = t (y_{2})$ satisfy $g (t_{1}) = y_{1}$ , $g (x_{2}) = y_{2}$ and $f (x_{1}) = f (x_{2})$ .

Conversely, if we have $x_{1}$ and $x_{2}$ as above, then $h (y_{1}) = h (y_{2})$ , so $S = g \times g (R)$ where $R \subseteq X \times X$ is ${(x_{1}, x_{2}) | f (x_{1}) = f (x_{2})}$ . But $R$ is closed in $X \times X$ since it’s the equaliser of $X \times X ⇉_{f π_{2}}^{f π_{1}} Y$ . So $R$ is compact, so $S$ is compact, so $S$ is closed in $Y \times Y$ .

Definition 5.15 (Monadic tower). Let $C ⇄_{G}^{F} D$ be an adjunction where $D$ has reflexive coequalisers. The monadic tower of $(F ⊣ G)$ is the diagram

where

𝕋

is the monad induced by

(F ⊣ G)

, and

K

and

L

are as in Theorem 5.7 and Lemma 5.9, and

𝕊

is the monad induced by

(L ⊣ K)

and so on.

We say $(F ⊣ G)$ has monadic length $n$ if we reach an equivalence after $n$ steps.