Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.