Eilenberg-Moore objects

Monad maps and Algebras Redux

In a previous post, we noted that for a $\mathsf{Set}$ monad $\mathbb{T}$ , and set $A$ , there is a bijective correspondence between:

Eilenberg-Moore algebras for the monad $\mathbb{T}$ with underlying set $A$ .
Monad morphisms of type $\mathbb{T} \rightarrow ((-) \Rightarrow A) \Rightarrow A$ with codomain the continuation monad induced by $A$ .

We also briefly remarked that this observation can be generalised beyond the category $\mathsf{Set}$ . In this post, using some of the ideas we have learned in recent posts, we are going to explore relationships of this type between algebras and morphisms of monads in more detail.

Enrichment

We previously encountered enriched monads. Recall that for a monoidal category $\mathcal{V}$ , a $\mathcal{V}$ -enriched category $\mathcal{C}$ has $\mathcal{C}(A,B)$ an object in $\mathcal{V}$ , rather than a mere set. We can also defined $\mathcal{V}$ -enriched functors and natural transformations which respect this structure.

Example: The category $\mathbf{Pre}$ has objects preorders, and morphisms monotone maps. This category has products, and so can be seen as a monoidal category with respect to this structure. A $\mathbf{Pre}$ -enriched category is a category in which:

The collection of morphisms of type $A \rightarrow B$ is a preorder.
Composition of morphisms is monotone in both arguments. That is $f_1 \leq f_2$ and $g_1 \leq g_2$ implies that $g_1 \circ f_1 \leq g_2 \circ f_2$ .

A $\mathbf{Pre}$ -functor a functor which is also monotone in its action on morphisms.

If a category $\mathcal{V}$ s monoidal closed, this category is itself a $\mathcal{V}$ -category, with hom object $\mathcal{V}(A,B)$ the exponential $A \multimap B$ . This is usually phrased as $\mathcal{V}$ being enriched over itself.

Example: The category $\mathbf{Pre}$ is Cartesian closed, and therefore is enriched over itself. The exponential $A \Rightarrow B$ in $\mathbf{Pre}$ is simply the collection of morphisms of that type, with the pointwise order on monotone functions.

If our base of enrichment $\mathcal{V}$ is symmetric monoidal closed, then for a $\mathcal{V}$ -category $\mathcal{C}$ we can define the opposite category $\mathcal{C}^{op}$ by setting $\mathcal{C}^{op}(A,B) = \mathcal{C}(B,A)$ , and defining the composition morphism of type

$\mathcal{C}^{op}(B,C) \otimes \mathcal{C}^{op}(A,B) \rightarrow \mathcal{C}^{op}(A,C)$

as the composite

$\mathcal{C}(C,B) \otimes \mathcal{C}(B,A) \xrightarrow{\sigma} \mathcal{C}(B,A) \otimes \mathcal{C}(C,B) \xrightarrow{m_{C,B,A}} \mathcal{C}(C,A)$

where $\sigma$ is the symmetry, and $m_{C,B,A}$ is the composition morphism in $\mathcal{C}$ .

With these technical preliminaries in place, for a symmetric monoidal category $\mathcal{V}$ , seen as enriched over itself, and $\mathcal{V}$ -object $A$ , there is a $\mathcal{V}$ -functor$:

$(-) \multimap A : \mathcal{V}^{op} \rightarrow \mathcal{V}$

As in the unenriched case, this functor is adjoint to itself, and so induces continuation or double dualisation $\mathcal{V}$ -enriched monad $((-) \multimap A) \multimap A$ . We then get a generalisation of the previous result, that for any other $\mathcal{V}$ -monad $\mathbb{T}$ , and $\mathcal{V}$ -object $A$ there is a bijective correspondence between:

Eilenberg-Moore algebras for the monad $\mathbb{T}$ , with underlying object $A$ .
Monad maps $\mathcal{T} \rightarrow ((-) \multimap A) \multimap A$ .

So the previous result generalises to enriched category theory. Note that the assumptions are unfortunately quite restrictive, as we can only consider monads on the base of enrichment itself. This is the enriched version of the fact the ordinary category theory result only applied to $\mathsf{Set}$ monads. This seems frustrating, so it is natural to ask if we can do any better.

Codensity and Formality

We previously encountered codensity monads. These were built using right Kan extensions. For a functor $F : \mathcal{A} \rightarrow \mathcal{B}$ , the codensity monad induced by $F$ has endofunctor $\mathsf{Ran}_F(F) : \mathcal{B} \rightarrow \mathcal{B}$ . We will write $\langle F,F \rangle$ for this codensity monad.

With any unfamiliar construction, it is natural to consider what it does in some simple cases. One obvious choice is to fix a set $A$ , and consider the codensity monad induced by the functor $A : 1 \rightarrow \mathsf{Set}$ that picks out that object. This will induce a monad on $\mathsf{Set}$ . Using some standard tools for calculating right Kan extensions in $\mathsf{Set}$ , we find something familiar. $\langle A,A \rangle$ is the continuation monad induced by $A$ .

We can therefore rephrase the original result that motivated our investigations as saying for monad $\mathbb{T}$ on $\mathsf{Set}$ , there is a bijective correspondence between:

Eilenberg-Moore algebras for $\mathbb{T}$ , with underlying set $A$ .
Monad morphisms $\mathbb{T} \rightarrow \langle A,A \rangle$ , with codomain the codensity monad induced by the functor $A : 1 \rightarrow \mathsf{Set}$ .

So far, we don’t have anything new, except a shift in viewpoint from emphasising the continuation monad, to a codensity based perspective. It is natural to then consider whether there is anything special about the category $\mathsf{Set}$ in this observation, and in fact there isn’t. So we can make a much stronger statement.

For a monad $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ and $\mathcal{C}$ -object $A$ , assuming the required right Kan extensions exist, there is a bijective correspondence between:

Eilenberg-Moore algebras for $\mathbb{T}$ , with underlying object $A$ .
Monad morphisms $\mathbb{T} \rightarrow \langle A,A \rangle$ , with codomain the codensity monad induced by the functor $A : 1 \rightarrow \mathcal{C}$ .

We can go further still, and ask if there’s anything special about the fact we’re doing category theory? Can we use the formal category theory perspective we’ve introduced in recent posts to get a more general result?

To do so, we must address a couple of wrinkles:

We need to abstract the notion of right Kan extension to an arbitrary 2-category. This is routine, we just require the same universal property, but now of abstract 0,1 and 2-cells, rather than categories, functors and natural transformations. The resulting structures are usually called a right extensions.
We have been making heavy use of the terminal category to pick out objects, via functors of the form $A : 1 \rightarrow \mathcal{C}$ . This may not make sense in an arbitrary 2-category.

To address the second point, we are looking to generalise from Eilenberg-Moore algebras built upon individual objects, to something more suitable in an arbitrary 2-category. We have already seen the required abstraction before, left monad actions, which solved a similar problem when we looked at Eilenberg-Moore objects.

Putting this all together, we get a much more general statement. Let $\mathcal{K}$ be a 2-category, and $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ a monad in $\mathcal{K}$ . For a 1-cell $A : \mathcal{B} \rightarrow \mathcal{C}$ , there is a bijective correspondence between:

Left $\mathbb{T}$ actions with underlying 1-cell $A$ .
Monad morphisms $\mathbb{T} \rightarrow \langle A,A \rangle$ with codomain the codensity monad induced by $A : \mathcal{B} \rightarrow \mathcal{C}$ .

So we learn that the previous result only hinged on the universal property of extensions, and nothing specific to category theory. The previous result about enriched monads arises as a special case in the 2-category of $\mathcal{V}$ -categories.

Conclusion

We’ve explored a classic result that often crops up in many guises in the literature. By exploiting our new tools of codensity monads, formal category theory, and left monad actions, we abstracted away a lot of distracting clutter, and reached a clearer understanding of what was really making this bijection work.

Further reading: This post was motivated by some discussions in the excellent “A 2-Categories Companion” by Lack, which is well worth reading. The material about enriched dual dualisation monads is almost exclusively contained in Kock’s “On Double Dualization Monads”. Readers wanting more than the details we briefly sketched will find a thorough and very readable account in that paper.

Eilenberg-Moore Objects

This time, our aim is to understand the Eilenberg-Moore construction better. To do so, we will look for a generalisation of this construction for monads in an arbitrary 2-category $\mathbf{K}$ . Working at this level of abstraction will provide results that apply in other settings, for example monads in the sense of enriched category theory. Even if all you care about is ordinary monads, this perspective forces us towards a universal property characterisation of the usual Eilenberg-Moore category, rather than our previous focus on an explicit construction.

Remark: Moving to a 2-categorical setting has a certain “intimidation factor”. It may help to recall that 0, 1 and 2 cells in $\mathbf{K}$ are analogous to categories, functors and natural transformations in $\mathbf{Cat}$ . In particular, 1 and 2-cells can be composed vertically and horizontally just as functors as natural transformations can. For readers aware of such issues, we will be working entirely with strict 2-categories and 2-functors, so there are no distracting coherence isomorphisms to worry about either.

Eilenberg-Moore locally

For a monad $(\mathcal{C},\mathbb{T},\eta,\mu)$ in $\mathbf{K}$ , where should we start looking for an analogue of the conventional Eilenberg-Moore construction? In that case, we built a well-chosen 0-cell in the 2-category $\mathbf{Cat}$ , as we know these are simply categories, which we understand well. As we now work with an arbitrary 2-category $\mathbf{K}$ , we’ve no idea what the 0-cells are, so we cannot persist with this plan directly.

A natural plan of attack is to reduce this problem to one we’re more familiar with. To do so, for a 0-cell $\mathcal{X}$ , we consider the representable 2-functor

$\mathbf{K}(\mathcal{X},-) : \mathbf{K} \rightarrow \mathbf{Cat}$

This maps structures in $\mathbf{K}$ , which we don’t understand very well, into $\mathbf{Cat}$ , for which we have more understanding. As monads are defined in terms of equations between structures in a 2-category, they are preserved by 2-functors. Therefore

$\mathbf{K}(\mathcal{X},\mathbb{T})$

is an ordinary monad on the category $\mathbf{K}(\mathcal{X},\mathcal{C})$ . Concretely, the functor part of this monad acts as:

$U : \mathcal{X} \rightarrow \mathcal{C} \;\mapsto\; \mathbb{T} \circ U : \mathcal{X} \rightarrow \mathcal{C}$

The components of the unit and multiplication at $U : \mathcal{X} \rightarrow \mathcal{C}$ are $\eta \circ U$ and $\mu \circ U$ . We can then consider the Eilenberg-Moore category

$\mathbf{K}(\mathcal{X},\mathcal{C})^{\mathbf{K}(\mathcal{X},\mathbb{T})}$

Here we find something familiar, the Eilenberg-Moore algebras are left actions for the monad $\mathbb{T}$ in $\mathbf{K}$ . Of course we must generalise our original definition of left action from the 2-category $\mathbf{Cat}$ to an arbitrary 2-category $\mathbf{K}$ , but this is routine.

We now need to abstract a bit further, as we have defined this construction for an arbitrary 0-cell $\mathcal{X}$ . To remove this arbitrary choice, we make this component a parameter, and consider the 2-functor:

$\mathbf{K}(-,\mathcal{C})^{\mathbf{K}(-,\mathbb{T})} : \mathbf{K}^{op} \rightarrow \mathbf{Cat}$

A standard next step for such a functor is to ask when it is representable, that is when there is a 0-cell $\mathcal{C}^{\mathbb{T}}$ and 2-natural isomorphism:

$\mathbf{K}(\mathcal{X}, \mathcal{C}^{\mathbb{T}}) \cong \mathbf{K}(\mathcal{X}, \mathcal{C})^{\mathbf{K}(\mathcal{X},\mathbb{T})}$

If such a representation exists, $\mathcal{C}^{\mathbb{T}}$ is referred to as the Eilenberg-Moore object for the monad $\mathbb{T}$ , and establishes its universal property. We can think of this as internalising the collection of left monad actions, in a similar way to the relationship between hom sets and exponentials for example.

To unpick the universal property a bit further, write $\mathbf{\theta}$ for the 2-isomorphism. We consider the image of the identity 1-cell under $\mathbf{\theta}$ into:

$\mathbf{K}(\mathcal{C}^{\mathbb{T}}, \mathcal{C})^{\mathbf{K}(\mathcal{C}^\mathbb{T},\mathbb{T})}$

This is a left $\mathbb{T}$ -action

$\chi : \mathbb{T} \circ U^\mathbb{T} \Rightarrow U^\mathbb{T}$

This action is said to be a universal left action, and fully defines $\mathbf{\theta}$ . The action of $\mathbf{\theta}$ on 1-cells is:

$H : X \rightarrow \mathcal{C}^\mathbb{T} \;\mapsto\; \chi \circ H$

and on 2-cells:

$\sigma : H \Rightarrow H' \;\mapsto\; U^\mathbb{T} \circ \sigma$

Unravelling these details is a worthwhile exercise if you want to develop understanding representable 2-functors and 2-naturality, generalising a similar argument ordinary representable functors.

Example: The 2-category $\mathbf{Cat}$ has Eilenberg-Moore objects for every monad. This is also the case in the enriched category setting of $\mathcal{V}-\mathbf{Cat}$ for a base of enrichment $\mathcal{V}$ with (enough) equalizers. In both cases, the Eilenberg-Moore objects are given by the usual construction of the Eilenberg-Moore category. The universal left action is given by

$U^\mathbb{T} \circ \epsilon : \mathbb{T} \circ U^{\mathbb{T}} \Rightarrow U^\mathbb{T}$

where $\epsilon$ is the counit of the free / forgetful adjunction for the Eilenberg-Moore category.

That Eilenberg-Moore objects in the settings of ordinary and enriched category theory are the usual constructions is encouraging.

As further evidence of the usefulness of this perspective, if a monad $\mathbb{T}$ has an Eilenberg-Moore object, then other aspects of monad theory can be developed directly from the universal property. Of immediate interest are:

There is a 1-cell $F^\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}^\mathbb{T}$ such that $\mathbb{T}$ is induced by an adjunction $F^\mathbb{T} \dashv U^\mathbb{T}$ in $\mathbf{K}$ .
There is a unique comparison 1-cell in $\mathbf{K}$ exhibiting this adjunction as the terminal such adjunction.

We avoid spelling out the details, but they follow fairly directly from the universal property, and details can be found in Street’s paper.

Eilenberg-Moore globally

In an earlier post, we introduced the 2-category $\mathbf{\mathsf{Mnd}}(\mathbf{K})$ . Sketching the details:

0-cells monads in $\mathbf{K}$ .
1-cells Eilenberg-Moore laws between a pair of monads.
2-cells are 2-cells from $\mathbf{K}$ which suitably commute with the Eilenberg-Moore laws.

The full details can be found in an earlier discussion about distributive laws.

There is a 2-functor:

$\mathbf{K} \rightarrow \mathbf{\mathsf{Mnd}}(\mathbf{K})$

sending a 0-cell to its corresponding identity monad. This functor has a right 2-adjoint $\mathbf{\mathsf{Alg}}$ exactly when there is a 2-natural isomorphism:

$\mathbf{K}(\mathcal{X}, \mathbf{\mathsf{Alg}}(\mathcal{C}, \mathbb{T})) \cong \mathbf{\mathsf{Mnd}}(\mathbf{K})((\mathcal{C}, \mathsf{Id}), (\mathcal{C}, \mathbb{T}))$

This doesn’t immediately look familiar, but if we unravel the definitions, we find that Eilenberg-Moore laws of type:

$\mathbb{T} \circ H \Rightarrow \mathbb{H} \circ \mathsf{Id}$

are the same thing as left $\mathbb{T}$ -actions, and so we are simply requiring the representability discussed in the previous section globally. Therefore, this right adjoint exists exactly when there is an Eilenberg-Moore object for every monad at $\mathbf{K}$ . In this case, we say that $\mathbf{K}$ admits the construction of algebras.

Intuitively, we might have anticipated that Eilenberg-Moore objects arise as part of an adjunction, as they are involved in an extremal resolution of monads.

Example: $\mathbf{Cat}$ admits the construction of algebras. This extends to the enriched setting, where $\mathcal{V}-\mathbf{Cat}$ for a sufficiently complete base of enrichment.

Duality

For our 2-category $\mathbf{K}$ , we can consider its various duals. Eilenberg-Moore objects in $\mathbf{K}^{op}$ , where we reverse 1-cells are what are known as Kleisli objects. These appropriately generalise the Kleisli construction to a 2-categorical setting, and the resulting universal property of Kleisli objects involves a universal right monad action. The duals $\mathbf{K}^{co}$ and $\mathbf{K}^{coop}$ , where we reverse 2-cells, recover the corresponding theory for comonads, involving what might be called universal left and right co-actions of a comonad.

Example: $\mathbf{Cat}$ admits the construction of algebras for all 4 of its duals, given by the usual Eilenberg-Moore and Kleisli constructions for monads and comonads.

Conclusion

By considering the 2-categorical generalisation of the Eilenberg-Moore construction, we have encountered further aspects of left monad actions:

They are the appropriate 2-categorical generalisation of ordinary Eilenberg-Moore algebras.
They are themselves algebras for a suitably defined monad.
They are also a special case of Eilenberg-Moore laws.
Left and right monad actions are fundamental to giving universal properties for the Eilenberg-Moore and Kleisli constructions.

It is beautiful that the theory can be developed at this level of abstraction, and that the results for the Kleisli construction and comonads fall out via duality, providing a deeper mathematical relationship between all these constructions.

Further reading: The ideas in this post originate in Street’s wonderful paper “Formal Theory of Monads”. There are lots of other interesting ideas in this paper, and I strongly recommend reading it. Also useful for background is Kelly and Street “Review of the elements of 2-categories”, and Lack’s “2-categories companion”. Other potential sources on Eilenberg-Moore objects are the nlab, and MacDonald and Sobral’s “Aspects of monads” chapter of “Categorical Foundations” edited by Pedicchio and Tholen.

Acknowledgements: This post was prompted by questions and suggestions on mastodon by users @varkor@mathstodon.xyz and @maxsnew@types.pl. I am very grateful for these comments, as they pointed to some gaps in my understanding, and encouraged me to explore further.