Why is the power set monoid stable under the inclusion order?

Question

Background:

On page 14 of Lang's Algebra, Lang makes the case, given subgroup $H$ of $G$, that the condition $xH \subset Hx$ for all $x \in G$ is equivalent to $xHx^{-1} \subset H$ and that both are equivalent to the normal definition(s) of a normal subgroup. Below is an excerpt from George Bergman's Companion to Lang's Algebra.

Excerpt:

Discussion:

I think I can see why the power set of a group or monoid, together with subset multiplication, forms a monoid. What I do not understand is why this is stable under the order relation of the power set. In other words, I think Bergman is saying the following: given monoid $M$ and subset multiplication $\bullet$, $\big( \mathcal P(M), \bullet \big)$ forms a monoid, and furthermore, if $A, B, C \in \mathcal P(M)$ and $A \subset B$, then $AC \subset BC$. It's not clear to me why this is true.

The way I justify the equivalence of $xH \subset Hx$ and $xHx^{-1} \subset H$ is as follows. Begin with the former expression and pick some $h \in H$. The expression implies that $xh = h' x$ for some $h' \in H$. Therefore $xhx^{-1} = h'$ which implies that any element from the set $xHx^{-1}$ is an element of $H$, and thus $xHx^{-1} \subset H$ as desired.

I appreciate any help.

Answer 1

Forget normality, and indeed groups; this is really just a general fact about operations on sets:

Suppose we have a set $X$ equipped with a binary operation $*$. Consider the relation $\hat{*}$ defined on $\mathcal{P}(X)$ by $$A\hat{*}B=\{a*b: a\in A, b\in B\},$$ or equivalently $$A\hat{*}B=\{x: \exists a\in A, b\in B(a*b=x)\}.$$ Then $A_1\subseteq A_2, B_1\subseteq B_2$ implies $$A_1\hat{*}B_1\subseteq A_2\hat{*}B_2.$$

This is basically just by the definition of subsethood. Suppose $x\in A_1\hat{*}B_1$; we want to show $x\in A_2\hat{*}B_2$.

• Since $x\in A_1\hat{*}B_1$, by definition of $\hat{*}$ there are $a\in A_1, b\in B_1$ such that $a*b=x$.

• But since $A_1\subseteq A_2$ we have $a\in A_2$, and since $B_1\subseteq B_2$ we have $b\in B_2$.

• So we can write $x$ as a thing in $A_2$ $*$ a thing in $B_2$ - which, again by the definition of $\hat{*}$, is to say $x\in A_2\hat{*} B_2$ as desired. $\quad\Box$

---

The analogous fact holds for $n$-ary operations in general. The "high-level" point is that $\hat{*}$ and its higher-arity analogues are defined by existentially quantifying over the input sets, and adding more things to those sets only makes existential quantifications more likely to be true. This ultimately leads to the idea of monotone operations on sets, but that's going a bit far afield.

Answer 2

Let $M$ be a monoid. The subset multiplication on ${\cal P}(M)$ is defined as follows. If $A, B \in {\cal P}(M)$, then $$ AB = \{ab \mid a \in A, b \in B\}. $$ Let us show that if $A \subseteq B$ and $C \in {\cal P}(M)$, then $AC \subseteq BC$. Indeed if $x \in AC$, there exist $a \in A$ and $c \in C$ such that $x = ac$. Since $A \subseteq B$, $a \in B$ and hence $ac \in BC$.

Note that I used the symbol $\subseteq$ on purpose. If you interpret $\subset$ as a strict inclusion (that is, $\varsubsetneq$), then the result is not true. Indeed, let $M$ be the two-element monoid $\{0,1\}$ under the usual multiplication of integers. Then $\{1\} \varsubsetneq M$, but $\{1\}\{0\} = M\{0\} = \{0\}$.

Actually, ${\cal P}(M)$ is an idempotent semiring with respect to union as addition and subset multiplication.