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:

  1. The unit and multiplication of the monad, and the axioms they satisfy.
  2. 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:

  1. \eta_A : A \rightarrow \mathbb{T}(A).
  2. \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.

Leave a comment