2.2 Monoids and Groups
A monoid is an associative magma which has an identity element.
The natural numbers form a monoid under addition. This means that \((\mathbb {N},+)\) is a monoid. The natural numbers also form a monoid under multiplication: \((\mathbb {N},\cdot )\) is a monoid. The identity element of \((\mathbb {N},+)\) is \(0\) and the idenitity element of \((\mathbb {N},\cdot )\) is \(1\).
The default notation is to write \(1\) for the identity element of a monoid \(M\) unless the binary operation on \(M\) is written as \(+\). If the binary operation is written as \(+\), the default is to write \(0\) for the identity element. Occasionally, when the binary operation is not written as \(+\), other symbols are used for the identity element. For example, the symbol \(e\) is common (but not as common as the symbol \(1\)). When we need to be clear that \(1\) refers to the identity element of a particular magma \(M\), we sometimes write \(1_M\). For example, we do this in the next definition.
Let \(M\) be a monoid and \(a,b\in M\). Suppose \(ab=ba=1\). Then, for \(c\in M\), the following are equivalent.
\(ac=1\);
\(ca=1\);
\(b=c\).
(iii)\(\Rightarrow \) (i) and (iii) \(\Rightarrow \) (ii) are both obvious from the hypothesis. To see that (i)\(\Rightarrow \) (iii), suppose \(ac=1\). Then \(b=b1=b(ac)=(ba)c=1c=c\). To see that (ii)\(\Rightarrow \) (iii), apply (i)\(\Rightarrow \) (iii) to \(M^{\mathrm{op}}\).
Let \(M\) be a monoid. An element of \(m\in M\) is invertible if there exists an \(n\in M\) such that \(mn=nm=1\). I write \(M^{\times }\) for the set of \(m\in M\) such that \(m\) is invertible.
Note that, by Proposition 2.23, if \(m\) is invertible then \(m\) has a unique inverse. If \(M\) is a commutative and the binary operaiton is written as \((m,n)\mapsto m+n\), then it is traditional to denote let \(-m\) denote the inverse of \(m\). Otherwise it is traditional to write \(m^{-1}\) for the inverse.
Suppose \(M\) is a monoid. Then
If \(x,y\in M^{\times }\), then \(xy\in M^{\times }\) with \((xy)^{-1}=y^{-1}x^{-1}\);
\(M^{\times }\) is a submonoid of \(M\);
if \(m\in M^{\times }\) then \((m^{-1})^{-1}=m\). Moreover, \((M^{\times })^{\times }=M^{\times }\), and
\((M^{\times })^{\times }=M^{\times }\).
Exercise.
A monoid \(M\) is a group if \(M=M^{\times }\).
From Exercise 2.25, it follows that, if \(M\) is a monoid, \(M^{\times }\) is a group.
Here are the prototypical examples of monoids and groups. Let \(X\) be a set. Write \(E(X)\) for the set of all functions \(f:X\to X\). Equip \(E(X)\) with the binary operation \((f,g)\mapsto f\circ g\). Then \(E(X)\) is a monoid because composition of functions is associative and \(\operatorname{\mathrm{id}}_X\circ f=f\circ \operatorname{\mathrm{id}}_X=f\) for all \(f\in \operatorname{\mathrm{End}}X\). Write \(A(X)\) for \(E(X)^{\times }\). Then \(A(X)\) is called the automorphism group of \(X\) or the group of permutations of \(X\).
Suppose \(f\in E(X)\), where \(X\) is a set. Then \(f\in A(X)\) if and only if the map \(f:X\to X\) is one-one and onto.
By definition, a map \(f:X\to X\) is in \(A(X)\) if and only if there exists a \(g:X\to X\) such that \(f\circ g = g\circ f = \operatorname{\mathrm{id}}_X\). But this condition is equivalent to the condition that \(f\) is one-one and onto.