# On the powerset of a monoid, does the second operation play nice with the first? Indeed, is it even useful?

Let $X$ denote a monoid. Then we can make $Y = \mathcal{P}(X)$ into a monoid, too. Define $$AB = \{ab \mid a \in A, b \in B\}$$ for all $A,B \in Y.$ We see immediately that $1$ (shorthand for $\{1\}$) is our new identity:

$$A1 = A, \;\; 1B = B.$$

In fact, $Y$ becomes an ordered monoid by defining that $A \leq B$ is notation for $A \subseteq B$. It follows that:

• $A \leq B \rightarrow AC \leq BC$
• $A \leq B \rightarrow CA \leq CB$

Furthermore, $Y$ is a complete atomistic Boolean algebra, and we have compatibility of composition with joins:

• $A \left(\bigvee_{i \in I} B_i\right) = \bigvee_{i \in I} AB_i$

• $\left(\bigvee_{i \in I} A_i\right) B = \bigvee_{i \in I} A_i B$

Now most authors would probably stop there. And perhaps that is the right thing to do. But, for the sake of experimentation, lets go a step further. Define another monoid structure on $Y$ by writing

$$A*B = (A^cB^c)^c.$$

Question. Does this new operation "play nice with" the earlier-defined operation in some sense? Indeed, is the $*$ operation in any way useful?

Discussion. We see that $*$ is associative, and that $1^c$ is its identity

$$A * 1^c = A, \;\; 1^c * B = B.$$

We also have the following.

• $A \leq B \rightarrow A*C \leq B*C$
• $A \leq B \rightarrow C*A \leq C*B$

• $A * \left(\bigwedge_{i \in I} B_i\right) = \bigwedge_{i \in I} (A*B_i)$

• $\left(\bigwedge_{i \in I} A_i\right) * B = \bigwedge_{i \in I} (A_i * B).$

Remark. We can do something similar with the binary relations on a set. Given binary relations $\alpha$ and $\beta$ on a set $S$, define

$$\alpha\beta = \{(x,y) \in S^2 \mid \exists s \in S : (x,s) \in \alpha \wedge (s,y) \in \beta\}$$

$$\alpha * \beta = \{(x,y) \in S^2 \mid \forall s \in S : (x,s) \in \alpha \vee (s,y) \in beta\}.$$

This makes $\mathcal{P}(S^2)$ into an ordered monoid in two distinct ways. In the first way, the diagonal relation is the identity. In the second, its complement is the identity. All the expected interactions with order-theoretic concepts hold. Actually, we can go further. In particular, the class of all sets can be made into a category whose morphisms are binary relations. However, this can be done in two different ways, corresponding to two different laws of composition. Once again, all the expected interactions with order-theoretic concepts hold.

Too many questions in the one. I answer on the first:

The new monoid $\mathcal{P}(X)(*)$ is isomorphic to $\mathcal{P}(X)$ by the map $A\to A^c$ so probably it is not useful.

• It may be of interest whether the two multiplications, $AB$ and $A*B$, are distributive over each other, as in Boolean algebra with union and intersection. – coffeemath Nov 22 '13 at 11:49
• Obviously. So? That's like saying that intersection isn't useful, because its isomorphic to union. The question is, do they interact nicely? – goblin Nov 22 '13 at 11:50
• The difference between $\cap$ and $*$ is that the first is quite natural, but the last... However, search in papers on theory of languages (e.g., by J.-E.Pin). The monoid $\mathcal{P}(X)$ is used in them. – Boris Novikov Nov 22 '13 at 12:09

This does not really answer your question, but it is something you might find interesting: the powerset of a monoid and the set of binary relations on a set are examples of residuated lattices. These examples are explained in detail in the book Residuated Lattices: An Algebraic Glimpse at Substructural Logics by Galatos, Jipsen, Kowalski and Ono.

In the case of the set $A=\mathcal P(S\times S)$ of binary relations on a set $S$, we have two unary operations on $A$:

• the converse of $\alpha\in A$ is the relation $\alpha^{\mathrm{op}}$ defined by $(x,y)\in\alpha^{\mathrm{op}}\iff(y,x)\in\alpha$; and
• the complement of $\alpha\in A$ is the relation $\alpha^{\mathrm c}$ defined by $(x,y)\in\alpha^{\mathrm c}\iff(x,y)\notin\alpha$.

We can then define a binary operation $\backslash$ on $A$ by setting $\alpha\mathop\backslash\beta=(\alpha^{\mathrm{op}}\beta^{\mathrm c})^\mathrm c$. This operation satisfies the 'residuation' identity $$\alpha\gamma\leq\beta\iff\gamma\leq\alpha\mathop\backslash\beta$$ for all $\alpha,\beta,\gamma\in A$, or in other words, for each $\alpha\in A$ the functions $\alpha\mathord-\colon A\to A$ and $\alpha\mathop\backslash\mathord-\colon A\to A$ constitute a (monotone) Galois connection.

Since it is a very late answer to your question, I will try to be as complete as possible.

You start with a monoid $$M$$ and equip $$\mathcal{P}(M)$$ with several operations and a partial order. In order to get ordered structures from beginning to end, one can start with an ordered monoid $$(M, \leqslant)$$ and consider the ordered monoid $$\mathcal{P}^\uparrow(M)$$ of upper sets of $$M$$ and the ordered monoid $$\mathcal{P}^\downarrow(M)$$ of lower sets of $$M$$. The product on these monoids are respectively defined by $$XY = \begin{cases} {\uparrow\!\{ xy \mid x \in X \text{ and } y \in Y \}} &\text{if X, Y \in \mathcal{P}^\uparrow(M)} \\ {\downarrow\!\{ xy \mid x \in X \text{ and } y \in Y \}} &\text{if X, Y \in \mathcal{P}^\downarrow(M)} \end{cases}$$ where $$\uparrow\!S$$ and $$\downarrow\! S$$ denote the upper and lower sets generated by $$S$$, respectively.

Then inclusion [resp. reverse inclusion] makes $$\mathcal{P}^\downarrow(M)$$ [resp. $$\mathcal{P}^\uparrow(M)$$] an ordered monoid. Let me just mention for the record that the other natural way to define an order on $$\mathcal{P}^\uparrow(M)$$ yields exactly the same definition: one has $$X \leqslant Y$$ if and only if, for each $$y \in Y$$, there exists $$x \in X$$ such that $$x \leqslant y$$.

Furthermore, $$\mathcal{P}^\downarrow(M)$$ and $$\mathcal{P}^\uparrow(M)$$ are semirings and even complete semirings with union as addition. Now, I let you verify that the map $$S \to S^c$$ defines an isomorphism from $$\mathcal{P}^\downarrow(M)$$ to $$\mathcal{P}^\uparrow(M)$$.

Coming back to your original setting, a monoid $$M$$ can be seen as the ordered monoid $$(M, =)$$, equipped with the equality order. In this case, upper sets and lower sets are simply subsets, so that $$\mathcal{P}(M) = \mathcal{P}^\downarrow(M) = \mathcal{P}^\uparrow(M)$$. But introducing $$\mathcal{P}^\downarrow(M)$$ and $$\mathcal{P}^\uparrow(M)$$ may better explain the nature of the isomorphism $$S \to S^c$$.