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.)