Eilenberg-Moore categories

Distributing over the powerset

We saw in the previous post that we can lift the powerset monad to a monad on any category of algebras defined by linear equations. In this short post, we shall tidy some loose ends, leading to another perspective on what we have done.

Eilenberg-Moore Algebras

As we have discussed previously, every finitary monad

(\mathbb{T} : \mathsf{Set} \rightarrow \mathsf{Set}, \eta, \mu)

arises from the free / forgetful adjunction of an equationally defined category of algebras:

\mathsf{Alg}(\Sigma,E)

Furthermore, the Eilenberg-Moore category $\mathsf{Set}^{\mathbb{T}}$ is equivalent to $\mathsf{Alg}(\Sigma,E)$ .

Putting these two facts together, if $\mathbb{T}$ has a presentation only involving linear equations, the previous post shows that the powerset monad lifts to a monad:

(\hat{\mathbb{P}} : \mathsf{Set}^{\mathbb{T}} \rightarrow \mathsf{Set}^{\mathbb{T}}, \hat{\eta}, \hat{\mu})

Distributive Laws

We have encountered liftings to Eilenberg-Moore categories before. In that case, we were interested in lifting functors to Eilenberg-Moore categories. In this case, we are interested in lifting entire monads.

For monads:

(\mathbb{S}, \eta, \mu)\quad\text{and}\quad(\mathbb{T}, \eta, \mu)

there is a bijection between:

Liftings of the monad $\mathbb{S}$ to $\mathsf{Set}^{\mathbb{T}}$ .
Distributive laws of type $\mathbb{T} \circ \mathbb{S} \Rightarrow \mathbb{S} \circ \mathbb{T}$ .

This is a topic worthy of further discussion, which we will return to in a later post.

Combining this bijection with the previous observation, if the monad $\mathbb{T}$ has a presentation by linear equations, there is a distributive law:

\mathbb{T} \circ \mathbb{P} \Rightarrow \mathbb{P} \circ \mathbb{T}

Summing Up

Using some standard facts, and Gautam’s results about extending algebraic structure to powersets, we have found sufficient conditions for the existence of a distributive law of $\mathbb{T}$ over the powerset monad $\mathbb{P}$ .

Our next steps is to clarify at a higher level of abstraction what is going on, so we can move beyond the powerset to more general monads.

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.

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.