 ### Patrick Stevens

Former mathematics student at the University of Cambridge; now a software engineer.

# Eilenberg-Moore

During my attempts to understand the fearsomely difficult Part III course “Introduction to Category Theory” by PT Johnstone, I came across the monadicity of the power-set functor $\mathbf{Sets} \to \mathbf{Sets}$. The monad is given by the triple $(\mathbb{P}, \eta_A: A \to \mathbb{P}(A), \mu_A: \mathbb{PP}(A) \to \mathbb{P}(A))$, where $\eta_A: a \mapsto \{ a \}$, and $\mu_A$ is the union operator. So $\mu_A(\{ \{1, 2 \}, \{3\} \}) = \{1,2,3 \}$.

It’s easy enough to check that this is a monad. We have a theorem saying that every monad has an associated “Eilenberg-Moore” category - the category of algebras over that monad. What, then, is the E-M category for this monad?

Recall: an algebra over the monad is a pair $(A, \alpha)$ where $A$ is a set and $\alpha: \mathbb{P}(A) \to A$, such that the following two diagrams commute. (That is, $\alpha$ here is an operation which takes a collection of elements of $A$, and returns an element of $A$.) Aha! The second diagram says that the operation $\alpha$ is “massively associative”: however we group up terms and successively apply $\alpha$ to them, we’ll come up with the same answer. Mathematica calls this attribute “Flat“ness, when applied to finite sets only.

Moreover, it doesn’t matter what order we feed the elements in to $\alpha$, since it works only on sets and not on ordered sets. So $\alpha$ is effectively commutative. (Mathematica calls this “Orderless”.)

The first diagram says that $\alpha$ applied to a singleton is just the contained element. Mathematica calls this attribute “OneIdentity”.

Finally, $\alpha(a, a) = \alpha(a)$, because $\alpha$ is implemented by looking at a set of inputs.

So what is an algebra over this monad? It’s a set equipped with an infinitarily-Flat, OneIdentity, commutative operation which ignores repeated arguments. If we forgot that “repeated arguments” requirement, we could use any finite set with any commutative monoid structure; the nonnegative reals with infinity, as a monoid, with addition; and so on. However, this way we’re reduced to monoids which have an operation such that $a+a = a$. That’s not many monoids.

What operations do work this way? The Flatten-followed-by-Sort operation in Mathematica obeys this, if the underlying set $A$ is a power-set of a well-ordered set. The union operation also works, if the underlying set is a complete poset - so the power-set example is subsumed in that.

Have we by some miracle got every algebra? If we have an arbitrary algebra $(A, \alpha)$, we want to define a complete poset which has $\alpha$ acting as the union. So we need some ordering on $A$; and if $x \leq y$, we need $\alpha(\{x, y\}) = y$. That looks like a fair enough definition to me. It turns out that this definition just works.

So the Eilenberg-Moore category of the covariant power-set functor is just the category of complete posets.

(Subsequently, I looked up the definition of “complete poset”, and it turns out I mean “complete lattice”. I’ve already identified the need for unions of all sets to exist, so this is just a terminology issue. A complete poset only has sups of directed sequences. A complete lattice has all sups.)