Semigroups, Monoids, and Groups

This post was machine-translated from the Korean original by Marvin (via Kimi). It may contain errors or awkward phrasing — the Korean original is the source of truth.

Semigroups and Monoids

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

The notions of homomorphism, substructure, and quotient structure defined for magmas carry over to semigroups without any modification. 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 an element \(e\in A\) satisfies

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

for all \(x\in A\), we call \(e\) an identity element.

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

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

On the other hand, an arbitrary element of a set \(A\) is the same thing as a function from the singleton \(\ast\) to \(A\). ([Category Theory] §Representable Functors, ⁋Example 2) From this point of view, the fact that \(e:\ast\rightarrow A\) is an identity element means that the following diagram

commutes.

Definition 3 If a semigroup \((A,\star)\) has an identity element, we call it a monoid.

Since a monoid requires a set \(A\), an operation \(\star\) on it, and an identity element \(e\) for \(\star\) in order to be well defined, we denote a monoid by a tuple such as \((A,\star, e)\). From the above discussion we see that a monoid is a monoid object in \(\Set\). ([Category Theory] §Monoid Objects, ⁋Example 2)

Some care is needed when defining monoid homomorphism and submonoid. For instance, given 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 as one that also preserves the identity element \(e\).

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 \(f:M_1\rightarrow M_2\) and \(g:M_2\rightarrow M_3\) be arbitrary monoid homomorphisms. Then by §Algebraic Structures, ⁋Proposition 7, \(g\circ f\) is a magma homomorphism. Moreover, from the equation

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

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

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

Furthermore, 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\).

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

As for quotient structures, suppose 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 \(A/R\), for any \([x]\in A/R\) we have

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

so the claim follows.

Assuming the existence of an identity element on a magma is one of the stronger conditions. For example, the following theorem shows that when two magma structures with identity elements are given on a set \(X\), in order for them to be compatible they must in fact coincide, and the result is a commutative monoid.

Theorem 7 (Eckmann–Hilton) Suppose two operations \(\star_1\), \(\star_2\) on a set \(X\) are given 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 \(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 arbitrary \(a,b\) we have

\[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 e)\star(b\star c)=(a\star b)\star(e\star c)=(a\star b)\star c\]

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

Groups

We finally define a group. Intuitively, it can be thought of as a monoid 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 an element to be right cancellable. Also, \(x\) is a left inverse of \(y\) if \(x\star y=e\) holds. Likewise, we can define \(x\) to be a right inverse of \(y\).

If \(x\) is both a left inverse and a right inverse of \(y\), we call \(x\) an inverse of \(y\), and in this case \(y\) is called invertible.

An element of a general monoid may have a left inverse but not a right inverse, or conversely a right inverse but not a left inverse. We generally write the inverse of \(x\) as \(x^{-1}\), but if the operation is denoted by \(+\) we instead write \(-x\). In order to assign a symbol to the inverse in this way, the inverse must be uniquely determined.

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

Proof

If \(x'\) and \(x''\) were 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

By the preceding proposition the inverse is unique, so it suffices to verify directly that the right-hand sides of the given equations satisfy the condition for being an inverse.

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

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

However, since

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

holds by the definition of \(a^{-1}\), we see that \(x=a\) satisfies the above equations. Since the inverse of \(a^{-1}\) is now unique, the inverse \((a^{-1})^{-1}\) of \(a^{-1}\) must be \(a\).

Similarly, the second claim also follows immediately from the following 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}\]

A group is now defined as follows.

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

Taking inverses is a function from \(G\) to itself¹, and hence 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, ⁋Example 4)

On the other hand, a monoid homomorphism \(f:G\rightarrow G'\) must necessarily 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] §Functor, ⁋Definition 10)

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

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

and multiplying on the right by the inverse of \(f(e)\) on both sides yields \(e'=f(e)\). Thus by the preceding argument, \(\Grp\) is also a full subcategory of \(\Magma\).

In the above argument we used the following lemma.

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

Proof

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

On the other hand, for the same reason as in 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\}\). Just as with submonoids, we can define a subgroup.

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

The following proposition tells us whether a given subset is a subgroup by a single criterion, without having to check the existence of an identity element or closure under inverses separately.

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\) holds for all \(a,b\in S\).

Proof

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

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

For a family \((S_i)\) of subgroups of a group \(G\), the intersection \(S=\bigcap S_i\) is a subgroup of \(G\) provided it is nonempty. Indeed, if we choose arbitrary \(a,b\in S\), then \(ab^{-1}\in S_i\) for all \(i\), and hence \(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\). We denote this by \(\langle S\rangle\). With a little effort one can also prove that \(\langle S\rangle\) coincides with the set of all elements obtained by performing finitely many operations on elements of \(S\cup S^{-1}\).

On the other hand, for a group \((G, \star, e)\) and an equivalence relation \(R\) compatible with \(\star\), we have verified that \(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. But 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, we see that every element of \(G/R\) is invertible.

From now on, when dealing with a general group we always denote the operation by multiplication, write \(x\star y\) simply as \(xy\), write the inverse of \(x\) as \(x^{-1}\), and the identity element as \(e\) as before. However, if the group \(G\) is specifically abelian, we denote the operation by addition, write the inverse of \(x\) as \(-x\), and the identity element as \(0\).

Generators and Presentations of Groups

So far we have treated groups abstractly from the axioms. We now look at one concrete example of a group, and through it summarize how to describe a group with a small amount of data.

Example 16 The symmetries of the plane taking a regular \(n\)-gon (\(n\ge3\)) to itself form a group under composition, called the dihedral group \(D_n\). Such symmetries consist of \(n\) rotations about the center by integer multiples of \(2\pi/n\) and \(n\) reflections about \(n\) axes of symmetry, so \(\lvert D_n\rvert=2n\).

Let \(r\) denote the smallest rotation and \(s\) one of the reflections; then applying \(r\) \(n\) times returns the identity, and applying \(s\) twice returns the identity. The smallest such positive integers are called the orders of \(r\) and \(s\) respectively. Also, in the dihedral group “rotate then flip” and “flip then rotate backwards” are the same symmetry, so

\[srs^{-1}=r^{-1}\]

holds. Since any symmetry is uniquely expressed in the form \(r^k\) or \(r^ks\) (\(0\le k<n\)), every element of \(D_n\) is obtained by repeatedly operating with \(r\) and \(s\), and hence \(\langle r,s\rangle=D_n\).

Earlier we wrote \(\langle S\rangle\) for the smallest subgroup of a group \(G\) containing a subset \(S\). If \(\langle S\rangle=G\) holds, we say that \(S\) generates \(G\), and each element of \(S\) is called a generator of \(G\). In particular, a group generated by a finite set is called finitely generated; the above dihedral group is the archetypal example of a group generated by two elements \(r,s\).

A set of generators alone does not determine a group; one must also specify the equations that hold among the generators, each called a relation, before the group is determined. This way of describing a group by a list of generators and relations is called a presentation; for instance, the dihedral group is written as

\[D_n=\langle r,s\mid r^n=s^2=e,\ srs^{-1}=r^{-1}\rangle.\]

The vertical bar separates generators on the left from relations on the right, and this notation denotes the most general group generated by the given generators in which the specified relations hold.

---

References

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

---

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