2.4 The monoid of subsets of a monoid
Suppose \(X\) is a set. We write \(\mathcal{P}(X)\) for the set of all subsets of \(X\). The set \(\mathcal{P}(X)\) is often called the power set of \(X\). If \(X\) is a finite set with \(n\) elements, then \(\mathcal{P}(X)\) has \(2^n\) elements. Because of this we sometimes write \(2^X\) for \(\mathcal{P}(X)\) even when \(X\) is not finite.
If \((M,*)\) is a magma, we can define a binary operation on the power set \(\mathcal{P}(M)\) by setting
for \(S\), \(T\subseteq M\).
Usually, we just write \(ST\) instead of \(S*T\), except when the binary operation \(*\) on \(M\) is called \(+\). In that case, we always write \(S+T\).
Suppose \(M\) is a monoid with identity element \(1\). Then \(\mathcal{P}(M)\) with the binary operation defined above is also a monoid with identity element \(\{ 1\} \).
Suppose \(X\subseteq M\). Then \(X\{ 1\} = \{ x1 : x\in X\} = \{ x: x\in X\} = X\). And similarly, \(\{ 1\} X = X\). This shows that \(\{ 1\} \) is the (necessarily unique) identity element of the magma \(\mathcal{P}(M)\).
On the other hand, if \(X\), \(Y\) and \(Z\) are subsets of \(M\), then it’s easy to see that \(X(YZ) = \{ xyz: x\in X, y\in Y, z\in Z\} = (XY)Z\).
Suppose \(m\in M\) and \(X\subseteq M\). Then we sometimes abuse notation and write \(mX = \{ m\} X\) and \(Xm = X\{ m\} \). It should be clear from the context when we do this. Of course, if the binary operation is written as “\(+\),” then we write \(X + m = X + \{ m\} \) or \(m + X = \{ m\} + X\).
Suppose \(S\subseteq M\) and \(n\) is a positive integer. Then \(S^n = \{ s_1s_2\cdots s_n: \forall i, s_i\in S\} \).
By definition, \(S^0 = \{ 1\} \) and, for \(n {\gt} 0\), \(S^n = SS^{n-1}\). So \(S^1 = S1 = S\).
Now, let’s prove the proposition by induction on \(n\) starting with \(n=1\). We’ve already proved the base case. So, suppose that the proposition holds for \(n-1\). Then \(S^n = SS^{n-1} = S\{ s_2\cdots s_n: \forall i, s_i \in S\} = \{ s_1s_2\cdots s_n: \forall i, s_i\in S\} \).
Now suppose \(G\) is a group. If \(X\subseteq G\), we write \(X^{-1} = \{ x^{-1}: x\in X\} \) or, when \(G\) is abelian with binary operation written “\(+\),” we write \(-X = \{ -x: x\in X\} \).