Lifting the Powerset Monad

In the previous post, we discussed extending algebraic operations on some set X to operations on the powerset \mathcal{P}(X). It turned out that the construction we used preserved linear equations, such as those used to define monoids. As promised, we now relate these ideas to monads.

Categories of Algebras

We will work with a category of algebras \mathcal{C} with:

  • Objects: A set X, with a binary operation \bullet: X \times X \rightarrow X and a constant 1 \in X.
  • Morphisms: A morphism (X_1, \bullet_1, 1_1) \rightarrow (X_2, \bullet_2, 1_2) is a function h : X_1 \rightarrow X_2 that preserves the binary operation and constant.

Equationally, the homomorphism conditions are:

h(x∙1y)=h(x)∙2h(y)andh(11)=12h(x \bullet_1 y) = h(x) \bullet_2 h(y) \quad\text{and}\quad h(1_1) = 1_2

The obvious forgetful functor U : \mathcal{C} \rightarrow \mathsf{Set} will feature prominently in what follows.

Although we will restrict our discussions to this simple category of algebras, everything we discuss will generalise to categories of algebras with any number of operations with arbitrary arities.

Lifting the Powerset Functor

We would like to lift the powerset functor:

𝒫:𝖲𝖾𝗍→𝖲𝖾𝗍\mathcal{P} : \mathsf{Set} \rightarrow \mathsf{Set}

to a functor:

𝒫^:𝒞→𝒞\hat{\mathcal{P}} : \mathcal{C} \rightarrow \mathcal{C}

By lift we mean that these functors will commute with the forgetful functor as follows:

U∘𝒫^=𝒫∘UU \circ \hat{\mathcal{P}} = \mathcal{P} \circ U

We already identified a suitable action on objects in the previous post. The lifting condition means there is only one potential action on morphisms:

𝒫^(h)=𝒫(h)\hat{\mathcal{P}}(h) = \mathcal{P}(h)

This will automatically commute with identities and composition, but we must verify that it yields a legitimate algebra morphism. For the binary operation:

𝒫(h)(U∙1^V)={h(u∙1v)|u∈U,v∈V}={h(u)∙2h(v)|u∈U,v∈V}=𝒫(h)(U)∙2^𝒫(h)(V)\mathcal{P}(h)(U \hat{\bullet_1} V) = \{ h(u \bullet_1 v) \mid u \in U, v \in V \} = \{ h(u) \bullet_2 h(v) \mid u \in U, v \in V \} = \mathcal{P}(h)(U) \hat{\bullet_2} \mathcal{P}(h)(V)

and for the constant:

𝒫(h)(11^)={h(11)}={12}=12^\mathcal{P}(h)(\hat{1_1}) = \{ h(1_1) \} = \{ 1_2 \} = \hat{1_2}

Lifting the Powerset Monad

As we have successfully lifted the powerset functor, our next steps is to lift the powerset monad

(ℙ:𝖲𝖾𝗍→𝖲𝖾𝗍,η,μ)(\mathbb{P} : \mathsf{Set} \rightarrow \mathsf{Set}, \eta, \mu)

to a monad:

(ℙ^:𝒞→𝒞,η^,μ^)(\hat{\mathbb{P}} : \mathcal{C} \rightarrow \mathcal{C}, \hat{\eta}, \hat{\mu})

to \mathcal{C}. By lifting, we mean a lifting of the powerset functor with unit \hat{\eta} : 1 \rightarrow \hat{\mathbb{P}} and \hat{\mu} : \hat{\mathbb{P}} \circ \hat{\mathbb{P}} \rightarrow \hat{\mathbb{P}} such that:

U∘η^=η∘UandU∘μ^=μ∘UU \circ \hat{\eta} = \eta \circ U \quad\text{and}\quad U \circ \hat{\mu} = \mu \circ U

These conditions force that the unit and multiplication of the lifted monad have the same components as for the original powerset monad. We need to verify that these are legitimate algebra morphisms. For the unit:

η^(u∙1v)={u∙1v}={u}∙1^{v}=η(u)∙1^η(v)\hat{\eta}(u \bullet_1 v) = \{ u \bullet_1 v \} = \{ u \} \hat{\bullet_1} \{ v \} = \eta(u) \hat{\bullet_1} \eta(v)

and for the multiplication:

𝐔∙^^𝐕=⋃{U∙^V|U∈𝐔,V∈𝐕}={u∙v|u∈⋃𝐔,v∈⋃𝐕}=μ(𝐔)∙^μ(𝐕)\mathbf{U} \hat{\hat{\bullet}} \mathbf{V} = \bigcup \{ U \hat{\bullet} V \mid U \in \mathbf{U}, V \in \mathbf{V}\} = \{ u \bullet v \mid u \in \bigcup \mathbf{U}, v \in \bigcup \mathbf{V} \} = \mu(\mathbf{U}) \hat{\bullet} \mu(\mathbf{V})

That’s actually all we have to check. Naturality of the unit and multiplication, and the monad axioms follow from the forgetful functor being faithful, and the lifting conditions.

Summing up, we have shown that we can lift the powerset monad to the category \mathcal{C}. Again, we can generalise, and lift the powerset monad to any category of algebraic structures.

Lifting the Powerset to Equational Classes

So far, we have lifted the powerset monad to categories of sets equipped with some completely unconstrained operations. This is moderately interesting, but normally we want such structures such as monoids which are required to satisfy some equations.

This is where the preservation of equations discussed in the previous post comes in. The object mapping

A↦ℙ^(A)A \mapsto \hat{\mathbb{P}}(A)

is such that \mathbb{P}(A) satisfies any linear equation satisfied by A. This means we can restrict our lifted powerset monad to any class of algebras defined by linear equations. Intuitively, when we restrict to classes of algebras defined by linear equations, our lifted monad won’t “jump out” of the class we are interested in.

Example: The powerset monad lifts to the category of monoids, and the category of commutative monoids.

Example: This construction does not lift the powerset monad to the category of meet semilattices, as the idempotence equation is not linear, and will not be preserved in general.

Summing Up

We have shown that the powerset monad can be lifted to any category of algebras defined by linear equations. There are a few questions we should ask ourselves:

  1. Can we generalise this construction beyond the powerset to other monads?
  2. What’s going on with the mysterious linearity requirement on the equations?
  3. Can we do anything with classes of algebras defined by more general equations?

We will move onto these questions in subsequent posts.

One thought on “Lifting the Powerset Monad”

  1. Pingback: Distributing over the powerset – Dan Marsden

Leave a comment