Lifting Algebras to Powersets

Lifting Monoids

Imagine I give you a monoid (M,\times,1), is there a way to construct a new monoid structure (\mathcal{P}(M),\hat{\times},\hat{1}) with underlying set the powerset of M?

A natural approach is to extend the monoid operations pointwise:

U×^V={u×v|u∈U,v∈V}U \hat{\times} V = \{ u \times v \mid u \in U, v \in V \}

and

1^={1}\hat{1} = \{ 1 \}

For this to yield a legitimate monoid, we need to verify the associativity and unit equations hold. For associativity:

U×^(V×^W)={u×(v×w)|u∈U,v∈V,w∈V}U \hat{\times} (V \hat{\times} W) = \{ u \times (v \times w ) \mid u \in U, v \in V, w \in V \}

and

(U×^V)×W={(u×v)×w|u∈U,v∈V,w∈W}(U \hat{\times} V) \times W = \{ (u \times v) \times w \mid u \in U, v \in V, w \in W \}

The resulting sets are equal by the associativity of the original monoid multiplication. Similarly for the left unit axiom:

1^×^U={1×u|u∈U}=U\hat{1} \hat{\times} U = \{ 1 \times u \mid u \in U \} = U

where the second equality uses the unit axiom of the original monoid. The other unit axiom follows symmetrically. The pointwise construction yields a monoid as we might have hoped.

Lifting special classes of monoids

As the obvious pointwise construction worked out nicely, allowing us to lift monoid structure to powersets, lets push our luck a bit. What if we want to lift commutative monoid structure in the same way? We then need to check that the commutativity axiom is also preserved by our construction:

U×^V={u×v|u∈U,v∈V}={v×u|v∈V,u∈U}=V×^UU \hat{\times} V = \{ u \times v \mid u \in U, v \in V \} = \{ v \times u \mid v \in V, u \in U \} = V \hat{\times} U

Again, the only interesting step is to exploit the new assumption of commutativity for the underlying commutative monoid.

This is looking pretty good, maybe this construction always works? Let’s push our luck a bit further. Can we lift commutative, idempotent monoids (a.k.a semilattices) to powersets? We now need to verify that idempotence is preserved:

U×^U={u1×u2|u1,u2∈U}≠UU \hat{\times} U = \{ u_1 \times u_2 \mid u_1,u_2 \in U \} \neq U

In this case we get into trouble, as applying the assumed idempotence of the underlying monoid doesn’t allow us to relate the left and right hand sides in general. Idempotence is not preserved by this construction. Disappointing, but at least we’ve learnt something. We also have an interesting question: which equations are preserved by the pointwise construction, and which ones are not?

When are Equations Preserved?

As we only have one example of an equation that breaks so far, we don’t have much to go on. Lets try and get another data point. Instead of assuming our original structure is a monoid, lets assume it satisfies the following annihilation property:

1×x=11 \times x = 1

Is this property preserved when we move to powersets?

1^×^U={1×u|u∈U}\hat{1} \hat{\times} U = \{ 1 \times u \mid u \in U \}

We need to be a bit careful here. If U is non-empty then the above is equal to \hat{1}, but if U is the empty set:

1^×^∅=∅≠1^\hat{1} \hat{\times} \emptyset = \emptyset \neq \hat{1}

So the annihilation property is not preserved. (You may want to double-check the emptyset doesn’t cause any trouble for the previous equations we’ve looked at).

Lets recap, and see if we can spot a pattern. The following equations are preserved:

  • Associativity: x \times (y \times z) = (x \times y) \times z
  • Left unit: 1 \times x = x
  • Right unit: x \times 1 = x
  • Commutativity: x \times y = y \times x

On the other hand, the following equations are not preserved:

  • Idempotence: x \times x = x
  • (Left) annihilation: 1 \times x = 1

If you’ve made it this far, you may wish to pause before continuing and see if you can conjecture what the key difference between these two classes of properties is. You may wish to experiment with a few more equational properties to gather more data points.

Looking at the equations above, there is a pattern in terms of how variables are used:

  • For equations that are preserved the same set of variables appear on the left and right hand side, and they each appear exactly once.
  • Otherwise the equation is not preserved.

We say that an equation is linear if it satisfies this property.

Of course, this observation applies more generally, to algebraic structures with arbitrary signatures. Linear equations are exactly the equations that are preserved when lifting algebraic structure pointwise to the powerset.

This result in due to Gautam “The Validity of Equations of Complex Algebras”.

Where are the Monads?

This is supposed to be a blog about monads, but we have not mentioned them so far. In fact, Gautam’s work is a first step into some interesting ideas involving monads; we will start to explore the implications in the next post. Enthusiastic readers might want to speculate how the observations above can be applied.

Leave a comment