Semigroups, Monoids, Groups

Semigroups and Monoids

Definition 1 A magma \((A, \star)\) satisfying the associative law is called a semigroup.

The homomorphisms, substructures, and quotient structures defined on magmas are well-defined for semigroups without any modifications. In particular, if \(A\) is a semigroup, then any submagma \(S\) of \(A\) is also a semigroup.

Definition 2 For any magma \((A,\star)\), if some \(e\in A\) satisfies

\[x\star e=e\star x=x\]

for all \(x\in A\), then \(e\) is called an identity element.

Any magma \(A\) has at most one identity element. If both \(e\) and \(e'\) are identity elements of \(A\), then

\[e=e\star e'=e'\star e=e'\]

so they must be equal.

On the other hand, any element of a set \(A\) can be regarded as a function from a singleton \(\ast\) to \(A\). ([Category Theory] §Representable Functors, ⁋Example 2) Applying this perspective, \(e:\ast\rightarrow A\) is an identity element precisely when the following diagram

commutes.

Definition 3 A semigroup \((A,\star)\) with an identity element is called a monoid.

Since a monoid is well-defined only when we have the set \(A\), the operation \(\star\) defined on it, and the identity element \(e\) with respect to \(\star\), we denote a monoid as a triple \((A,\star, e)\). From the above discussion, we see that a monoid is a monoid object in \(\Set\). ([[Category Theory] §Monoid Objects, ⁋Definition 1)

When defining monoid homomorphisms and submonoids, we must be careful. For two monoids \((A,\star,e)\) and \((A',\star',e')\), a magma homomorphism \(f:A\rightarrow A'\) need not preserve the identity element, so a monoid homomorphism is defined to preserve the identity element \(e\) as well.

Definition 4 For two monoids \((A, \star, e)\) and \((A',\star', e')\), a magma homomorphism satisfying \(f(e)=e'\) is called a monoid homomorphism.

Monoids and monoid homomorphisms defined in this way form a category.

Proposition 5 There exists a category \(\Mon\) whose objects are monoids and whose morphisms are monoid homomorphisms.

Proof

Let monoid homomorphisms \(f:M_1\rightarrow M_2\) and \(g:M_2\rightarrow M_3\) be given. By §Algebraic Structures, ⁋Proposition 7, \(g\circ f\) is a magma homomorphism. Also, from

\[(g\circ f)(e_1)=g(f(e_1))=g(e_2)=e_3\]

we see that \(g\circ f\) is also a monoid homomorphism.

Now, monoid homomorphisms are functions, so their composition is associative. Also, for any monoid \(M\), the identity function \(\id_M\) is always a monoid homomorphism.

Also, a submagma of a monoid need not contain the identity element, so a new definition is required as follows.

Definition 6 A submonoid of a monoid \((A,\star, e)\) is a submagma of \(A\) that contains the identity element \(e\).

However, if a family of submonoids \((S_i)\) of a monoid \((A,\star,e)\) is given, the intersection \(S=\bigcap S_i\) is again a submonoid. This is because \(e\in S_i\) for all \(i\), and therefore \(e\in S\).

For quotient structures, if a monoid \((A, \star,e)\) and an equivalence relation \(R\) compatible with \(\star\) are given, then \(A/R\) naturally inherits a monoid structure. Considering the equivalence class \([e]\) of \(e\) in the set \(A/R\), for any \([x]\in A/R\),

\[[x]\mathbin{\tiny\char"2606}[e]=[x\star e]=[x]=[e\star x]=[e]\mathbin{\tiny\char"2606}[x]\]

holds.

Assuming the existence of an identity element on a magma is a strong condition. For example, the following theorem shows that there is only one way to equip a set \(X\) with two compatible magma structures with identity elements, and the result is a commutative monoid.

Theorem 7 (Eckmann-Hilton) Let two operations \(\star_1\) and \(\star_2\) on a set \(X\) be such that \((X,\star_1,e_1)\) and \((X,\star_2,e_2)\) are both magmas with identity elements. If

\[(a\star_1 b)\star_2(c\star_1 d)=(a\star_2 c)\star_1(b\star_2 d)\]

holds for all \(a,b,c,d\in X\), then \(\star=\star_1=\star_2\), \(e=e_1=e_2\), and \((X,\star,e)\) is a commutative monoid.

Proof

First, we show that \(e_1=e_2\). This follows from the equation

\[e_1=e_1\star_1 e_1=(e_1\star_2e_2)\star_1(e_2\star_2e_1)=(e_1\star_1 e_2)\star_2(e_2\star_1 e_1)=e_2\star_2 e_2=e_2\]

Now for any \(a,b\),

\[a\star_1 b=(a\star_2 e_2)\star_1(e_2\star_2b)=(a\star_1 e_2)\star_2(e_2\star_1b)=a\star_2b\]

so \(\star=\star_1=\star_2\), and

\[a\star b=(e\star a)\star(b\star e)=(e\star b)\star(a\star e)=b\star a\]

and

\[a\star(b\star c)=(a\star 1)\star(b\star c)=(a\star b)\star(1\star c)=(a\star b)\star c\]

so \((X,\star,e)\) is a commutative monoid.

Groups

Finally, we define groups. Intuitively, these can be thought of as monoids in which every element has an inverse.

Definition 8 For a monoid \((A,\star,e)\), an element \(x\) is left cancellable if for any \(a,b\in A\), \(x\star a=x\star b\) implies \(a=b\). Similarly, we can define right cancellable elements. Also, \(x\) is a left inverse of \(y\) if \(x\star y=e\) holds. Similarly, we can define when \(x\) is a right inverse of \(y\).

If \(x\) is both a left inverse and a right inverse of \(y\), then \(x\) is called an inverse of \(y\), and in this case, \(y\) is said to be invertible.

In general, a monoid may have elements with left inverses but not right inverses, and conversely, elements with right inverses but not left inverses. The inverse of an element \(x\) is typically denoted by \(x^{-1}\), but if the operation is denoted by \(+\), then we write \(-x\) instead. To assign such a symbol to an inverse, the inverse must be uniquely determined.

Proposition 9 For a monoid \((A, \star, e)\), if an element \(x\in A\) is invertible, then the inverse of \(x\) is unique.

Proof

If \(x'\) and \(x''\) are both inverses of \(x\), then

\[x'=x'\star e=x'\star( x\star x'')=(x'\star x)\star x''=e\star x''=x''\]

so \(x'=x''\).

Using this, we obtain the following corollary.

Corollary 10 For invertible elements \(a,b\) of a monoid \((A,\star,e)\), the following hold.

1. $(a^{-1})^{-1}=a$
2. $(a\star b)^{-1}=b^{-1}\star a^{-1}$.

Proof

Since the inverse is unique by the previous proposition, it suffices to directly verify that the right-hand sides satisfy the conditions for being inverses.

First, let us check whether \(a\) is the inverse of \(a^{-1}\). The inverse of \(a^{-1}\) is an \(x\) satisfying the two equations

\[a^{-1}\star x=x\star a^{-1}=e\]

But since

\[a^{-1}\star a=a\star a^{-1}=e\]

holds by the definition of \(a^{-1}\), \(x=a\) satisfies the above equations. Now since the inverse of \(a^{-1}\) is unique, the inverse of \(a^{-1}\), namely \((a^{-1})^{-1}\), must be \(a\).

Similarly, the second claim follows immediately from the two equations

\[\begin{aligned}(a\star b)\star(b^{-1}\star a^{-1})&=a\star(b\star b^{-1})\star a^{-1}=a\star e\star a^{-1}=a\star a^{-1}=e,\\(b^{-1}\star a^{-1})\star(a\star b)&=b^{-1}\star(a^{-1}\star a)\star b=b^{-1}\star e\star b=b^{-1}\star b=e.\end{aligned}\]

Now we define groups as follows.

Definition 10 A monoid in which every element is invertible is called a group. If \(\star\) is commutative, it is called an abelian group (or commutative group).

Taking inverses is a function from \(G\) to itself¹, so a group \(G\) is determined by the data \((G,\star,e, (-)^{-1})\). The inverse \((-)^{-1}\) can be expressed by the following diagram

From this, we can verify that any group is a group object in \(\Set\). ([Category Theory] §Monoid Objects, ⁋Definition 1)

On the other hand, a monoid homomorphism \(f:G\rightarrow G'\) must preserve inverses.

\[f(x)\star'f(x^{-1})=f(x\star x^{-1})=f(e)=e',\qquad f(x^{-1})\star'f(x)=f(x^{-1}\star x)=f(e)=e'.\]

Thus \(\Grp\) is a full subcategory of \(\Mon\). ([Category Theory] §Functors, ⁋Definition 10)

Moreover, for a magma homomorphism \(f:G\rightarrow G'\) between two groups,

\[e'\star' f(e)=f(e)=f(e\star e)=f(e)\star'f(e)\]

and multiplying the inverse of \(f(e)\) on the right side of both equations gives \(e'=f(e)\). Thus by the previous argument, \(\Grp\) is also a full subcategory of \(\Magma\).

The above argument used the following lemma.

Lemma 12 (Cancellation law) Any invertible element is cancellable.

Proof

Multiply by the inverse of \(a\) on the left or right side of both equations.

On the other hand, for the same reason as Proposition 5, groups and group homomorphisms also form a category.

Proposition 13 There exists a category \(\Grp\) whose objects are groups and whose morphisms are group homomorphisms. Also, there exists a full subcategory \(\Ab\) whose objects are abelian groups and whose morphisms are group homomorphisms.

We can verify that these categories have a zero object \(\{e\}\). We can define subgroups similarly to submonoids.

Definition 14 A subset \(S\) of a group \((G,\star, e, {}^{-1})\) is a subgroup if \(S\) is a submonoid that is closed under taking inverses.

The following proposition allows us to determine whether a given subset is a subgroup using a single criterion, omitting checks for the existence of an identity element, closure under inverses, and so on.

Proposition 15 A nonempty subset \(S\) of a group \((G, \star, e, {}^{-1})\) is a subgroup of \(G\) if and only if \(a\star b^{-1}\in S\) always holds for any \(a,b\in S\).

Proof

If \(S\) is a subgroup of \(G\), then since \(b\in S\), we have \(b^{-1}\in S\), and therefore \(a\star b^{-1}\in S\) holds trivially.

Thus it suffices to show the reverse direction. Since \(S\) is nonempty, there exists some \(a\in S\), and then \(a\star a^{-1}\in S\), so \(e\in S\). Now for any \(a\in S\), \(a^{-1}=e\star a^{-1}\in S\) holds. Also, for any \(a,b\in S\), \(a\star b^{-1}=a\star(b^{-1})^{-1}\in S\) holds.

For a family of subgroups \((S_i)\) of a group \(G\), the intersection \(S=\bigcap S_i\) is a subgroup. If we choose arbitrary \(a,b\in S\), then \(ab^{-1}\in S_i\) for all \(i\), and therefore \(ab^{-1}\in S\). In particular, for any subset \(S\) of \(G\), applying this discussion to the collection of subgroups of \(G\) containing \(S\) yields the smallest subgroup containing \(S\). This is denoted by \(\langle S\rangle\). With some effort, one can also prove that \(\langle S\rangle\) coincides with the set of all elements obtained by finitely many operations on elements of \(S\).

On the other hand, we verified that for a group \((G, \star, e)\) and an equivalence relation \(R\) compatible with \(\star\), \(G/R\) has a monoid structure; moreover, \(G/R\) also has a group structure. To verify this, it suffices to show that any element \([x]\) of \(G/R\) is invertible. Since

\[[x]\mathbin{\tiny\char"2606}\bigl[x^{-1}\bigr]=\bigl[x\star (x^{-1})\bigr]=[e]=\bigl[x^{-1}\star x\bigr]=\bigl[x^{-1}\bigr]\mathbin{\tiny\char"2606}[x]\]

holds, every element of \(G/R\) is invertible.

When dealing with general groups, we will always denote the operation as multiplication, and thus abbreviate \(x\star y\) as \(xy\), denote the inverse of \(x\) as \(x^{-1}\), and denote the identity element as \(e\) as before. However, if a group \(G\) is abelian, we denote the operation as addition, the inverse of \(x\) as \(-x\), and the identity element as \(0\).

---

References

[Bou] Bourbaki, N. Algebra I. Elements of Mathematics. Springer. 1998.

---

1. Except when \(G\) is an abelian group, \((-)^{-1}\) is not a group homomorphism. ↩