mathematics – Dan Marsden

An application of monadicity

Now we have seen the basic ideas of monadicity, and Beck’s monadicity theorem, it’s time to look at an important application. Although the result in question belongs to the area of topos theory, to avoid pulling in too much additional theory we will consider a concrete example, and then sketch how this extends to the abstract setting.

Subsets and the contravariant powerset

For our motivating example, we are going to consider the category $\mathsf{Set}$ of sets and functions. The set

$\{ \mathsf{true}, \mathsf{false} \}$

which we shall denote $2$ will play an important role. For any set $X$ , a function $\chi : X \rightarrow 2$ corresponds to a subset of $X$ :

$\{ x \mid x \in X \;\text{and}\; \chi(x) = \mathsf{true} \}$

and given any subset $U \subseteq X$ , we can define a function:

$x \mapsto \begin{cases} \mathsf{true} & \text{ if } x \in U \\ \mathsf{false} & \text{otherwise} \end{cases}$

In this way, we can go back and forth between subsets and what are known as their characteristic functions. For a fixed set $X$ , we can consider the set $2^X$ of characteristic functions of subsets of $X$ . The mapping

$X \mapsto 2^X$

extends to a functor. For $f : X \rightarrow Y$ we get a function in the opposite direction $2^f : 2^Y \rightarrow 2^X$ with action:

$\chi \mapsto \chi \circ f$

It is straightforward to check that this satisfies the functor axioms, so we have a functor:

$2^{(-)} : \mathsf{Set}^{op} \rightarrow \mathsf{Set}$ ,

sometimes referred to as the contravariant powerset functor. This functor has a left adjoint, which we shall also denote

$2^{(-)} : \mathsf{Set} \rightarrow \mathsf{Set}^{op}$ .

Notice the only difference here is whether we choose to put the “op” on the domain or codomain. Establishing that these two functors form an adjunction is straightforward, as we have natural bijections between:

Functions $2^X \rightarrow Y$ in $\mathsf{Set}^{op}$
Functions $Y \rightarrow 2^X$ in $\mathsf{Set}$
Functions $Y \times X \rightarrow 2$ in $\mathsf{Set}$
Functions $X \times Y \rightarrow 2$ in $\mathsf{Set}$
Functions $X \rightarrow 2^Y$ in $\mathsf{Set}$

We have seen a more abstract version of this proof before, as this is a special case of the adjunction that induces the continuation monad, in this case for the endofunctor:

$2^{2^{(-)}} : \mathsf{Set} \rightarrow \mathsf{Set}$

The perhaps surprising observation is that the functor

$2^{(-)} : \mathsf{Set}^{op} \rightarrow \mathsf{Set}$

is monadic, meaning the Eilenberg-Moore category of $2^{2^{(-)}}$ is equivalent to $\mathsf{Set}^{op}$ . Put another way, $\mathsf{Set}^{op}$ is monadic over $\mathsf{Set}$ . Aside from being a rather startling fact, this gives a concrete description of the Eilenberg-Moore category of this special case of the continuation monad. Some duality theory tells us that the category of complete atomic Boolean algebras is equivalent to $\mathsf{Set}^{op}$ , and this gives us an even more concrete description of the algebras of this monad.

Generalising

At first glance, the argument above looks very specific to the category of sets and functions. Fortunately, there is a very large class of categories that look sufficiently like the category of sets to carry out this argument in the abstract.

As a first step, we look at the important role of the set $2$ . It allowed us to connect subsets and characteristic functions. To generalise this, we first adopt a more categorical perspective, and consider subobjects rather than subsets. A subobject of object $X$ , is isomorphism class of monomorphisms $U \rightarrowtail X$ . Spelling this out a bit more, two monomorphisms $m : U \rightarrowtail X$ and $m' : U' \rightarrowtail X$ are isomorphic if there exists an isomorphism $i : U \rightarrow U'$ such that $m = m' \circ i$ .

A subobject classifier is a categorical abstraction of the correspondence between subsets (subobjects) and characteristic morphisms. Writing $\mathsf{Sub}(X)$ for the collection of subobjects of $X$ , a category $\mathcal{C}$ with finite limits is said to have a subject classifier if and only if there is an object $\Omega$ and natural isomorphism:

$\mathsf{Sub}(X) \cong \mathcal{C}(X,\Omega)$

There are several equivalent definitions of subobject classifiers. The typical statement involves a generic subobject and a pullback condition, but as we won’t delve into the details, the statement above emphasises the relationship between subobjects and classifying morphisms.

Example: The set $2$ is the subobject classifier in $\mathsf{Set}$ . Subobjects correspond to subsets which correspond to characteristic functions.

The class of categories that look sufficiently like the category of sets for our purposes are known as toposes. A topos is a finitely complete, Cartesian closed category with a subobject classifier. (There are almost as many equivalent definitions of a topos as there are books on the subject, depending on the perspective the author wishes to emphasize. We choose this one as it is reasonably straightforward.). There are many examples of toposes that crop up in mathematical practice.

Example: The category $\mathsf{Set}$ is a topos, and in many ways the motivating example for the abstraction. The full subcategory of finite sets is also a topos.

Example: For any small category $\mathcal{C}$ , the category of presheaves over $\mathcal{C}$ is a topos. This is simply the category with objects functors $\mathcal{C}^{op} \rightarrow \mathsf{Set}$ and morphisms natural transformations between them. This construction can be generalised greatly to various notions of categories of sheaves, but we avoid entering into what would be a sizeable technical detour.

For a topos $\mathcal{C}$ , by analogy with the set theoretic situation, as we have exponentials and a subobject classifier, it is natural to consider the functor:

$\Omega^{(-)} : \mathcal{C}^{op} \rightarrow \mathcal{C}$

It is a non-trivial observation that this functor is monadic. As a concrete argument is no longer possible, this is typically established using a monadicity theorem. Interested readers that are prepared for a bit of topos theory can find the details in any good book on topos theory. Slightly confusingly, topos theorists also refer to this result as the (topos theoretic) monadicity theorem.

This result has an immediate pay-off. As a topos is finitely complete, $\mathcal{C}^{op}$ is also finitely complete. In other words, $\mathcal{C}$ is finitely cocomplete. Finite cocompleteness was actually included in the original definition of a topos, until it was shown that it followed from the other axioms. Monadicity is a particularly elegant way of establishing this fact.

Conclusion

Our discussion of topos theory has been deliberately somewhat sketchy, to avoid pulling in too many technical details. Topos theory is a vast subject, with connections to many parts of mathematics, and would probably warrant a blog of its own.

Further reading: Readers interested in filling in some of the topos theoretic technical details could look at one of the standard sources, such as volume 1 of Johnstone’s “Sketches of an Elephant”, Moerdijk and MacLane’s “Sheaves in Geometry and Logic” or volume 3 of Borceux’s “Handbook of Categorical Algebra”.

A monad is just a one object enriched category

We have seen that the notion of monad can be interpreted in any bicategory. The aim of todays post is to explain that for a bicategory $\mathcal{W}$ , a monad in $\mathcal{W}$ is the same thing as a one-object $\mathcal{W}$ -enriched category. Or more tersely:

A monad is the same thing as a one-object $\mathcal{W}$ -category.

Mostly, this is just a case of understanding the definitions, with no complicated translation between the two structures required.

Monads and enrichment

Recall that for a monoidal category $(\mathcal{V}, \otimes, I)$ , a $\mathcal{V}$ –enriched category, or $\mathcal{V}$ -category $\mathcal{A}$ is a generalisation of ordinary categories with:

A collection of objects $X,Y,\ldots$ .
For every pair of object $X,Y$ , a hom object $\mathcal{A}(X,Y)$ .
For each object $X$ , an identity $\mathcal{V}$ -morphism $j_X : I \rightarrow \mathcal{A}(X,X)$ .
For each triple of objects $X,Y,Z$ , a composition $\mathcal{V}$ -morphism $m_{X,Y,Z} : \mathcal{A}(Y,Z) \otimes \mathcal{A}(X,Y) \rightarrow \mathcal{A}(X,Z)$ .

These are subject to some natural axioms such that composition is associative, and unital with respect to the chosen identities. The motivating special case is that a $\mathsf{Set}$ -enriched category is the same thing as an ordinary category.

It is a well-known fact of enriched category theory that a monoid in the monoidal category $\mathcal{V}$ is the same thing as a one object $\mathcal{V}$ -category. The even better known special case, which crops up in most introductions to category theory, is that a one object ordinary category is the same thing as a monoid.

Of course, the special case that we should be interested in as monad theorists is the monoidal category of endofunctors $([\mathcal{C}, \mathcal{C}], \circ, \mathsf{Id}_{\mathcal{C}})$ . Using the fundamental meme of monad theory, that a monad is just a monoid in the category of endofunctors, we can deduce that monads on $\mathcal{C}$ are the same thing as one object $[\mathcal{C},\mathcal{C}]$ -enriched categories. This claim works equally well if we consider monads in an arbitrary bicategory.

Example: We have seen previously that for a monoidal category $\mathcal{V}$ with coproducts, a $\mathcal{V}$ -enriched category is the same thing as a monad in the bicategory of $\mathcal{V}$ -matrices, $\mathbf{Mat}(\mathcal{V})$ . Applying the observation above, the following all describe the same data:

A $\mathcal{V}$ -enriched category with set of objects $O$ .
A monad on $O$ in $\mathbf{Mat}(\mathcal{V})$ .
A one-object $\mathbf{Mat}(\mathcal{V})(O,O)$ -enriched category.

Which is a bit of a funny conclusion, every multi-object enriched category is the same thing as a single-object enriched category over a different base. In particular, every ordinary (small) category with set of objects $O$ is a one-object $\mathbf{Mat}(\mathsf{Set})(O,O)$ -enriched category.

In the example above, it feels a bit clumsy to have to keep saying “…with set of objects $O$ …”. To clean this up, and take this story a bit further, we are going to have to generalise our notion of enriched category, to categories enriched over a bicategory $\mathcal{W}$ . Although this may sound a bit intimidating, it is actually only a small step beyond enrichment in a monoidal category.

A $\mathcal{W}$ -enriched category $\mathcal{A}$ consists of:

A collection of objects $X,Y,Z$ , each with an associated extent, given by a 0-cell $\mathsf{ext}(X)$ in $\mathcal{W}$ .
For every pair of objects $X,Y$ , a hom 1-cell $\mathcal{A}(X,Y) : \mathsf{ext}(X) \rightarrow \mathsf{ext}(Y)$ .
For every object $X$ , an identity 2-cell $j_A : \mathsf{Id}_{\mathsf{ext}(X)} \Rightarrow \mathcal{A}(X,X)$ .
For every triple of objects $X,Y,Z$ , a composition 2-cell $m_{X,Y,Z} : \mathcal{A}(Y,Z) \circ \mathcal{A}(X,Y) \Rightarrow \mathcal{A}(X,Z)$ .

As before, this data is subject to natural unitality and associativity axioms.

With this definition in place, naming things suggestively, a one object $\mathcal{W}$ -category consists of:

An object, with extent a 0-cell $\mathcal{C}$ in $\mathcal{W}$ .
A single hom 1-cell $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ .
An identity 2-cell $\eta : \mathsf{Id} \Rightarrow \mathbb{T}$ .
A single composition 2-cell $\mu : \mathbb{T} \circ \mathbb{T} \Rightarrow \mathbb{T}$ .

This data satisfies exactly the axioms such that $(\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}, \eta, \mu)$ is a monad. That is:

A monad in $\mathcal{W}$ is the same thing as a one-object $\mathcal{W}$ -category.

We rephrase the previous example in this more flexible setting.

Example: For a monoidal category $\mathcal{V}$ , a $\mathcal{V}$ -category is a one object $\mathbf{Mat}(\mathcal{V})$ -enriched category.

A possibly more interesting example is as follows.

Example: We have seen previously that for a category $\mathcal{C}$ with pullbacks, an internal category in $\mathcal{C}$ is the same thing as a monad in the bicategory of spans $\mathbf{Span}(\mathcal{C})$ . Now applying our previous observation, the following all describe the same data:

An internal category in $\mathcal{C}$ .
A monad in $\mathbf{Span}(\mathcal{C})$ .
A one-object $\mathbf{Span}(\mathcal{C})$ -enriched category.

This establishes a slightly surprising connection between internal and enriched category theory.

Conclusion

To an extent, this post is about almost trivial relationships between definitions that happen to coincide. This is not just an exercise in categorical showing-off or pointless abstraction. The relationship between monads and one-object enriched categories is really a matter of perspective. This may allow us to relate monads to other concepts, for example finitary monads and Lawvere theories can be connected in this way. Once monads are viewed as categories, we can consider categorical notions such as completion under certain limits or colimits, which again occur in connection with Lawvere theories. These ideas are used to startling effect in the work of Richard Garner and co-authors, which I highly recommend as further reading.

Algebras are regular quotients of free algebras

The aim of this post is to show that for a monad

$(\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}, \eta : \mathsf{Id}_{\mathcal{C}} \Rightarrow \mathbb{T}, \mu : \mathbb{T}^2 \Rightarrow \mathbb{T})$ ,

every Eilenberg-Moore algebra $(A,\alpha : \mathbb{T}(A) \rightarrow A)$ is given as the coequalizer of a parallel pair of morphisms between free algebras in $\mathcal{C}^{\mathbb{T}}$ . In this case, we say that $(A,\alpha)$ is a regular quotient of free algebras. Notice we are not making any any assumptions about the base category $\mathcal{C}$ such as (co)completeness, so we don’t have a lot to work with. Really the only available structure is:

The unit and multiplication of the monad, and the axioms they satisfy.
The two axioms that every Eilenberg-Moore algebra satisfies relating its structure map to the unit and multiplication.

So we have a handful of morphisms, and some equations that they satisfy, and that’s it. Let’s have a look at how this magic trick is performed.

A parallel pair of algebra morphisms

As a first step, we note that for an Eilenberg-Moore algebra $(A,\alpha)$ , we have a parallel pair of $\mathcal{C}^{\mathbb{T}}$ morphisms:

$\mu_A, \mathbb{T}(\alpha) : F^{\mathbb{T}}(\mathbb{T}(A)) \rightarrow F^{\mathbb{T}}(A)$

Expanding the action of the free algebra functor, this is a pair of morphisms:

$\mu_A, \mathbb{T}(\alpha) : (\mathbb{T}^2(A), \mu_{\mathbb{T}^2(A)}) \rightarrow (\mathbb{T}(A), \mu_A)$

That $\mu_A$ is an algebra morphism is equivalent to the Eilenberg-Moore algebra multiplication axiom. That $\mathbb{T}(\alpha)$ is an algebra morphism is simply naturality of the monad multiplication.

By naturality of $\mu$ , we note that there is an algebra morphism in the opposite direction:

$\mathbb{T}(\eta_A) : (\mathbb{T}(A), \mu_A) \rightarrow (\mathbb{T}^2(A), \mu_{\mathbb{T}^2(A)})$

Furthermore, by the monad right unitality axiom

$\mu_A \cdot \mathbb{T}(\eta_A) = \mathsf{id}_{\mathbb{T}(A)}$

and by the algebra unit axiom:

$\mathbb{T}(\alpha) \cdot \mathbb{T}(\eta_A) = \mathsf{id}_{\mathbb{T}(A)}$

Therefore these three morphisms form a reflexive pair.

A coequalizer in the base category

We now apply the forgetful functor $U^{\mathbb{T}} : \mathcal{C}^{\mathbb{T}} \rightarrow \mathcal{C}$ , yielding a parallel pair.

$U^{\mathbb{T}}(\mu_A), U^{\mathbb{T}}(\mathbb{T}(\alpha)) : U^{\mathbb{T}} \circ F^{\mathbb{T}}(\mathbb{T}(A)) \rightarrow U^{\mathbb{T}}(\alpha) : U^{\mathbb{T}} \circ F^{\mathbb{T}}(A)$

which if we unpack the definitions is simply a parallel pair of $\mathcal{C}$ -morphisms:

$\mu_A, \mathbb{T}(\alpha) : \mathbb{T}^2(A) \rightarrow \mathbb{T}(A)$

Our current aim is to find a coequalizer of this pair, knowing it must have codomain $A$ . The obvious choice is to consider

$\alpha : \mathbb{T}(A) \rightarrow A$

as our candidate universal coequalizer morphism. By the algebra multiplication axiom, we have

$\alpha \cdot \mu_A = \alpha \cdot \mathbb{T}(\alpha)$

which is an encouraging first step to establishing this forms a coequalizer diagram. To establish the universal property, we are going to need a bit more. Using components of the monad unit, we get two other useful $\mathcal{C}$ -morphisms:

$\eta_A : A \rightarrow \mathbb{T}(A)$ .
$\eta_{\mathbb{T}(A)} : \mathbb{T}(A) \rightarrow \mathbb{T}^2(A)$ .

By the algebra unit axiom

$\alpha \cdot \eta_A = \mathsf{id}_A$

and by the monad left unitality axiom

$\mu_A \cdot \eta_{\mathbb{T}(A)} = \mathsf{id}_{\mathbb{T}(A)}$

Finally, by naturality:

$\mathbb{T}(\alpha) \cdot \eta_{\mathbb{T}(A)} = \eta_A \cdot \alpha$ .

We have shown the our parallel pair form a contractible coequalizer in the base category, and further that the parallel pair of algebra morphism:

$\mu_A, \alpha : F^{\mathbb{T}}(\mathbb{T}(A)) \rightarrow F^{\mathbb{T}}(A)$

form a reflexive $U^{\mathbb{T}}$ -contractible pair.

An algebra coequalizer

We would now like to conclude we have a coequalizer in the Eilenberg-Moore category. Recall that the forgetful functor $U^{\mathbb{T}} : \mathcal{C}^{\mathbb{T}} \rightarrow \mathcal{C}$ creates colimits that are preserved by $\mathbb{T}$ and $\mathbb{T}^2$ . As contractible coequalizers are absolute colimits, we can apply this result to lift the coequalizer to the Eilenberg-Moore category.

Finally, we note that $\alpha$ is in fact an algebra morphism of type:

$F^{\mathbb{T}}(A) \rightarrow (A,\alpha)$

by the Eilenberg-Moore algebra multiplication axiom. Therefore

$F^{\mathbb{T}}(\mathbb{T}(A)) \xrightarrow{ \mu_A, \alpha} F^{\mathbb{T}}(A) \xrightarrow{\alpha} (A,\alpha)$

is a coequalizer diagram in the Eilenberg-Moore category, and $(A,\alpha)$ is a regular quotient of free algebras as claimed.

Conclusion

We encountered reflexive $U$ -contractible coequalizers in the statement of Beck’s monadicity theorem. In this post, we have seen one example of why these particular absolute colimits are important in the theory of monads, as they can be used to construct every Eilenberg-Moore algebra as a quotient of a free algebra.

Proving this result from very few assumptions, beyond some morphisms satisfying certain equations, leads us to the construction of coequalizers which are defined by by equations between morphisms. Such constructions are necessary absolute, and this at least partially explains the significance of absolute colimits in this context.

Beck’s Monadicity Theorem

Now we have introduced the idea of monadicity, we move onto the most important theorem in this area. Beck’s monadicity theorem tells us that a functor $U: \mathcal{B} \rightarrow \mathcal{C}$ is monadic if and only if the following three conditions hold:

U has a left adjoint.
U reflects isomorphisms.
$\mathcal{B}$ has coequalizers of reflexive $U$ -contractible pairs, and $U$ preserves them.

The aim of this post is to unpack these three conditions, and to justify why they are at least necessary for a monadic functor. That they are also sufficient is a rather amazing fact that we may delve into in another post. The first two conditions are relatively trivial, but the third will require more consideration.

Left adjoints

The first condition, that $U$ has a left adjoint is the most trivial. By definition, we require a monadic functor to be a right adjoint so we can consider the comparison functor to the Eilenberg-Moore category.

Isomorphism reflection

A functor $U$ is said to reflect isomorphisms, or to be conservative, if for every $f$ , $U(f)$ is an isomorphism implies $f$ is.

Remark: Isomorphism reflection is a statement about morphisms not objects. It does not say that if $U(A)$ is isomorphic to $U(B)$ then $A$ is isomorphic to $B$ .

For a monad $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ , if we have an Eilenberg-Moore algebra morphism $h : (A,\alpha) \rightarrow (B,\beta)$ , then in $\mathcal{C}$

$h \cdot \alpha = \beta \cdot \mathbb{T}(h)$ .

Now assume there exists $\mathcal{C}$ -morphism $g : B \rightarrow A$ such that

$g \cdot h = \mathsf{id}_{A}$ and $h \cdot g = \mathsf{id}_{B}$

then we would like to show $g$ is an algebra morphism of type $(B,\beta) \rightarrow (A,\alpha)$ . This is a straightforward calculation:

$g \cdot \beta = g \cdot \beta \cdot \mathbb{T}(h \cdot g) = g \cdot h \cdot \alpha \cdot \mathbb{T}(g) = \alpha \cdot \mathbb{T}(g)$ .

Therefore $U^{\mathbb{T}}$ reflects isomorphisms. It is easy to verify that equivalences are also conservative, and conservative functors are closed under composition. As

$U = U^{\mathbb{T}} \circ K$

where $K$ is the comparison functor, if $U$ is monadic, it must be conservative. This condition is already sufficient to weed out various putative monadic functors.

Example: Let $\mathsf{Pos}$ be the category of posets and monotone maps, and $U : \mathsf{Pos} \rightarrow \mathsf{Set}$ the obvious forgetful functor. This functor has a left adjoint, and so satisfies the first condition of the monadicity theorem. Now consider the two element posets:

The poset $X$ , with underlying set $\{ x_1, x_2 \}$ with the discrete partial order.
The poset $Y$ , with underlying set $\{ y_1, y_2 \}$ with the least partial order such that $y_1 \leq y_2$ .

There is a bijective monotone map $h : X \rightarrow Y$ with $h(x_1) = y_1$ and $h(x_2) = y_2$ . This morphism has no inverse monotone map. On the other hand, the underlying function $U(h)$ has an obvious inverse in $\mathsf{Set}$ . Therefore $U$ is not conservative, and therefore cannot be monadic.

This argument is easily adapted to show the forgetful functor $\mathsf{Cat} \rightarrow \mathsf{Set}$ taking a small category to its set of objects is not monadic.

The coequalizer condition

We now need to untangle the final condition, and this will be a little bit more technical. We need to introduce two related notions.

Firstly, a parallel pair:

$d^0, d^1 : A \rightarrow B$

is said to be contractible (or split) if there exists $t : B \rightarrow A$ such that

$d^0 \cdot t = \mathsf{id}_B$ and $d^1 \cdot t \cdot d^0 = d^1 \cdot t \cdot d^1$ .

Notice that these conditions are asymmetrical in $d^0$ and $d^1$ .

Secondly, a contractible (or split) coequalizer consists of the following data:

A parallel pair $d^0, d^1 : A \rightarrow B$ .
A morphism $t : B \rightarrow A$ .
A morphism $d : B \rightarrow C$ .
A morphism $s : C \rightarrow B$ .

such that:

$d$ coequalizes the parallel pair, that is $d \cdot d^0 = d \cdot d^1$ .
$d^0$ has section $t$ , that is $d^0 \cdot t = \mathsf{id}_B$ .
$d$ has section $s$ , that is $d \cdot s = \mathsf{id}_C$ .
$d^1 \cdot t = s \cdot d$ .

Again, notice the asymmetry of the conditions. As suggested by the terminology, a contractible coequalizer is a coequalizer in the ordinary sense.

Furthermore, a contractible coequalizer is simply a collection of morphisms satisfying four equations. If we apply a functor to the morphisms, the resulting data will also satisfy the same equations, as functors preserve them, and will therefore also form a contractible coequalizer. Therefore contractible coequalizers are preserved by every functor. That is, they are an example of an absolute colimit.

A second useful fact, connecting these two notions, is that if a contractible pair $d^0, d^1 : A \rightarrow B$ has a coequalizer $d : B \rightarrow C$ , then there automatically exists an $s : C \rightarrow B$ such that it forms a contractible coequalizer.

A $U$ -contractible pair, is a pair $d^0, d^1 : A \rightarrow B$ such that $U(d^0), U(d^1) : U(A) \rightarrow U(B)$ has a contractible coequalizer. Notice this terminology is slightly misleading, we are requiring a contractible coequalizer, not just a contractible pair.

With that mass of terminology in place, we recall that for any monad $\mathbb{T}$ , the forgetful functor $U^{\mathbb{T}} : \mathcal{C}^{\mathbb{T}} \rightarrow \mathcal{C}$ creates colimits which exist in the base category and are preserved by $\mathbb{T}$ and $\mathbb{T}^2$ . $U$ -contractible pairs induce absolute coequalizers in the base category, which are therefore created by $U^{\mathbb{T}}$ . Secondly, although equivalences don’t necessarily create colimits that exist, they do preserve them. Therefore, if $U : \mathcal{B} \rightarrow \mathcal{C}$ is monadic, as

$U = U^{\mathbb{T}} \circ K$

$\mathcal{B}$ has coequalizers of $U$ -contractible pairs, and $U$ preserves them.

In fact, this is stronger than the proof of the monadicity theorem needs, and we can restrict our attention to a small class of coequalizers. A parallel pair $d^0, d^1 : A \rightarrow B$ is said to be reflexive if they have common section. That is, there exists an $r : B \rightarrow A$ such that

$d^0 \cdot r = \mathsf{id}_B = d^1 \cdot r$ .

Conclusion

Two out of the three conditions of the monadicity theorem are pretty routine. The third took a bit of unravelling, but enduring the technicalities is a worthwhile investment, as these special colimits arise again and again in the theory of monads. We will look in detail at the most important source of these special coequalizers in a later post.

Further reading: Our account owes a lot to that of Barr and Well’s in Toposes Triples and Theories. We have deliberately used similar notational choices to them in case readers want to consult their work for further details, which is highly recommended. Johnstone remarks in the Elephant that the restriction to reflexive pairs in condition three is omitted in many accounts, but is all that is needed. Toposes, Triples and Theories is also careful in this regard.

The Idea of Monadicity

Naively, for a given category $\mathcal{B}$ , we might wonder if it is equivalent to the Eilenberg-Moore category of a monad. This would help us deduce properties of $\mathcal{B}$ , such as (co)completeness, using facts we know about the Eilenberg-Moore construction.

Giving this a moments thought, it doesn’t sound quite right, as to deduce properties of an Eilenberg-Moore category, we need more information, for example about the base category. In order to reach a mathematically useful notion, we need to pin down exactly what we intend with regard to this equivalence.

We would like to know what the base category we’re interested in is, and how it relates to $\mathcal{B}$ , so it is natural to consider functors of the form.

$U : \mathcal{B} \rightarrow \mathcal{C}$

Intuitively this is a candidate forgetful functor from an Eilenberg-Moore category to its base category. If there is any hope of $\mathcal{B}$ being equivalent to an Eilenberg-Moore category, $U$ should have a left adjoint

$F : \mathcal{C} \rightarrow \mathcal{B}$ .

This gives us a bit more to work with, as adjunction will give us a monad

$\mathbb{T} = U \circ F$

We are now interested in when there is an equivalence:

$\mathcal{B} \simeq \mathcal{C}^{\mathbb{T}}$

To specify this equivalence more precisely, recall we have already seen the Eilenberg-Moore comparison functor, which relates resolutions of the same monad. Recall this is the unique functor

$K : \mathcal{B} \rightarrow \mathcal{C}^{\mathbb{T}}$

that commutes with the free and forgetful functors, in that:

$U^{\mathbb{T}} \circ K = U$ and $K \circ F = F^{\mathbb{T}}$ .

We have now arrived at the right notion. A right adjoint functor $U : \mathcal{B} \rightarrow \mathcal{C}$ is monadic if the comparison functor is an equivalence of categories. If there exist such a $U$ , we say that $\mathcal{B}$ is monadic over $\mathcal{C}$ .

Monadicity Theorems

Unsurprisingly, a monadicity theorem gives conditions under which a functor is monadic. The key result is known as Beck’s monadicity theorem, which gives precise conditions for monadicity. There are many variations, often with sufficient assumptions that are more convenient to establish in practice. There are also a family of related results, which don’t specifically establish monadicity, but rather other nice properties of the comparison functor.

In fact, if you have a specific functor with a left adjoint, it is often easier to establish monadicity by directly proving the required equivalence. So what’s the point of monadicity theorems? Their main application is when you are working more abstractly, aiming to show that under suitable assumptions that all functors of a certain type are monadic. This situation is similar to the use of adjoint functor theorems. Again, these are rarely applied to establish that a particular functor has an adjoint, but rather that in an abstract setting every functor satisfying certain axioms always has an adjoint.

In our discussions, we will focus on when the comparison functor is an equivalence. MacLane considers the stronger situation where the comparison functor is an isomorphism. We will pay this perhaps less categorically natural formulation less attention. It is however important to be aware that there are monadicity theorems of this type as well when looking at the wider literature.

If instead of the Eilenberg-Moore construction, we consider the Kleisli construction, we can ask similar questions. The situation is much simpler in this case, as was previously discussed.

Conclusion

The notions of monadicity and monadicity theorems are fundamental tools. Despite this, as they are used in more abstract work, they tend to be perceived as a more advanced topic. This is probably reinforced by the fact that the details of monadicity theorems are a little bit technical looking, with certain special classes of colimits having a prominent role. In reality, the details only involve elementary ideas, and are not particularly challenging. We will discuss the specifics of monadicity theorems, related results about comparison functors, and their applications in future posts.

Eilenberg-Moore limits and colimits

For every monad $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ , we have seen that the Eilenberg-Moore construction yields a new category $\mathcal{C}^{\mathbb{T}}$ . So far, we don’t have a lot of general facts about Eilenberg-Moore categories we can exploit. In fact, these categories are typically very nice, with lots of good properties that a category theorist might hope for being inherited from their base categories. In this post, we will consider (co)completeness of Eilenberg-Moore categories.

Creation of limits and colimits

A functor

$U : \mathcal{A} \rightarrow \mathcal{B}$

is said to create limits of shape $\mathcal{D}$ if for every diagram

$D : \mathcal{D} \rightarrow \mathcal{A}$

the limit $\lim_{U \circ D}$ exists, with limit cone:

$\lim_{U \circ D} \xrightarrow{\lambda_I} UD(I)$

and there exists a unique $D$ -cone

$L \xrightarrow{\lambda'_I} D(I)$

living above the limit cone, that is for all $I$

$U(\lambda'_I) = \lambda_I$

Furthermore, $(L, \lambda')$ is the limit of the diagram $D$ .

The point of knowing that a functor creates limits is that assuming we understand those limits in the codomain category, we the know both:

Limits of the same shape exist in the domain category.
We can explicitly calculate those limits from those in the base category.

There is an obvious dual notion of a functor that creates colimits.

Limits in Eilenberg-Moore Categories

For a monad $\mathbb{T}$ , recall that there is a forgetful functor:

$U^{\mathbb{T}} : \mathcal{C}^{\mathbb{T}} \rightarrow \mathcal{C}$

We have seen that this functor has a left adjoint, and so will preserve all limits that exist in $\mathcal{C}^{\mathbb{T}}$ for standard reasons. It turns out, we can say a lot more than that. In fact $U^{\mathbb{T}}$ creates all limits that exist in $\mathcal{C}$ .

Lets look at what this means in more detail. The action of $U^{\mathbb{T}}$ on algebra morphisms is trivial:

$U^{\mathbb{T}}(h) = h$

Therefore, for diagram:

$D : \mathcal{D} \rightarrow \mathcal{C}^{\mathbb{T}}$

if $\lim_{U^{\mathbb{T}} \circ D}$ exists, with limit cone:

$\lim_{U^{\mathbb{T}} \circ D} \xrightarrow{\lambda_I} U^{\mathbb{T}}D(I)$

then there exists a unique Eilenberg-Moore algebra structure $\alpha$ on $\lim_{U^{\mathbb{T}} \circ D}$ such that each $\lambda_I$ is an algebra homomorphism:

$(lim_{U^{\mathbb{T}} \circ D}, \alpha) \rightarrow D(I)$

and this is the limit cone in $\mathcal{C}^{\mathbb{T}}$ .

This result is fairly easy to prove. The universal property of the limit of $U^{\mathbb{T}} \circ D$ completely determines what $\alpha$ can be. Verifying it is an Eilenberg-Moore algebra, and satisfies the required universal property in $\mathcal{C}^{\mathbb{T}}$ requires further applications of the universal property of the limit in the base category.

This theorem gives us a very good handle on limits in Eilenberg-Moore categories:

$\mathcal{C}^{\mathbb{T}}$ is as complete as the base category $\mathcal{C}$ .
We can calculate these limits explicitly, using our understanding of limits in the base category.

Colimits in Eilenberg-Moore Categories

The situation for colimits is not as good as that for limits, but it’s still pretty nice. There are standard theorems that address some important cases.

Firstly, $U^{\mathbb{T}}$ creates every colimit which exists in the base category and is preserved by $\mathbb{T}$ and $\mathbb{T} \circ \mathbb{T}$ . Again, we get very nice behaviour, but for a slightly strange looking restricted class of colimits. The proof is similar to that for limits, exploiting the universal property of colimits in the base category to find a unique algebra structure map such that the cocone morphisms in the base category are algebra morphisms. The additional preservation assumptions are used to get colimits of the required shape to complete the argument.

You may ask where we are going to find colimits that satisfy these assumptions. There are special colimits called absolute colimits, which are preserved by every functor. These colimits are important in the theory of monads, particularly what are known as monadicity theorems, which we have only briefly touched upon so far. Applying the result above tells us that $U^{\mathbb{T}}$ creates all absolute colimits which exist in the base category.

If you’re wondering how on earth there can be colimits which are preserved by every functor, or how we might prove such a thing, it is instructive to think about what functors preserve. As functors are homomorphisms of categories, they preserve commuting diagrams. It turns out there are certain limits which are characterised by certain diagrams commuting, and therefore are automatically preserved by every functor. We will discuss concrete examples, specifically certain special classes of coequalizers, in later posts when we look at monadicity theorems in more detail.

Another important results is that $\mathcal{C}^{\mathbb{T}}$ is cocomplete if the base category is, and $\mathcal{C}^{\mathbb{T}}$ has coequalizers. This is because in Eilenberg-Moore categories, we can then construct coproducts using these coequalizers, and that establishes cocompleteness. Using this observation, Linton established that for $\mathsf{Set}$ monads, Eilenberg-Moore categories are cocomplete. Note these results are weaker than those we saw before, as there is no suggestion that these colimits are created by $U^{\mathbb{T}}$ , and so the situation is getting wilder. There are more axiomatic versions of Linton’s result, which can then be applied in settings beyond $\mathsf{Set}$ to establish cocompleteness of Eilenberg-Moore categories.

Conclusion

As a warm up application of the results above, and the connection between monads and universal algebra, we can conclude that:

Categories of algebraic structures such as monoids, groups, rings and so on are all complete and cocomplete.
The limits in these algebraic categories are created by the forgetful functor to $\mathsf{Set}$ .
Certain well behaved colimits in these algebraic categories are also created by the forgetful functor.

We will see some more exciting applications of these results later, once we have discussed some other machinery.

This is only one aspect of the niceness of Eilenberg-Moore categories. There are further tame conditions under which the Eilenberg-Moore category is either regular or locally presentable for example. Certain special classes of monads, such as commutative monads imply further structure on the Eilenberg-Moore category. We shall return to these topics later.

Further reading: The results in this post are all very well known, and can be found in all the standard sources, such as Categories for the Working Mathematician, Toposes, Triples and Theories, or volume 2 of the Handbook of Categorical Algebra.