Semigroups, Monoids, and Groups

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 on magmas carry over to semigroups without any modification. In particular, if \(A\) is a semigroup, any submagma \(S\) of \(A\) is also a semigroup.

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

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

then \(e\) is called an identity element.

Any magma \(A\) has at most one identity element. For if both \(e\) and \(e'\) are identity elements of \(A\), this is because

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

holds.

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) Applying this perspective, 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 set \(A\), an operation \(\star\) defined on it, and with respect to \(\star\) an identity element \(e\) must all be present for a monoid to be well-defined, when denoting a monoid we write it as 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, 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 also preserve the data of 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. Meanwhile, from the equation

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

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

Now 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, since a submagma of a monoid also does not need to contain the identity element, a new definition is required as below.

Definition 6 A submonoid of a monoid \((A,\star, e)\) means a submagma containing the identity element \(e\) in \(A\).

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

In the case of quotient structures, if a monoid \((A, \star,e)\) and, compatible with \(\star\), an equivalence relation \(R\) are given, \(A/R\) naturally inherits the monoid structure. This is because in the set \(A/R\), considering for \(e\) the equivalence class \([e]\), 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 one of the strong conditions. For example, the following theorem shows that when endowing a set \(X\) with information about two magmas and identity elements, in order for them to have mutually compatible structures the two structures must be the same, and the result is a commutative monoid.

Theorem 7 (Eckmann-Hilton) Suppose that on a set \(X\) there exist two operations \(\star_1\), \(\star_2\) 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, let us show \(e_1=e_2\). This is obtained by the following 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\), since

\[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\]

we have \(\star=\star_1=\star_2\), and since

\[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\]

, \((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)\), that \(x\) is left cancellable means that for any \(a,b\in A\), if \(x\star a=x\star b\) then \(a=b\) holds. Similarly, we can define what it means for an element \(x\) to be right cancellable. Also, that \(x\) is a left inverse of \(y\) means that \(x\star y=e\) holds. Similarly, we can define what it means for \(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 a monoid \((A,\star,e)\) and invertible elements \(a,b\), 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 show by direct calculation that the right-hand sides of the given equations satisfy the conditions for an inverse.

First, let us see whether the inverse of \(a^{-1}\) is \(a\). The inverse of \(a^{-1}\) is such that the two equations

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

are satisfied by \(x\). However, since

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

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

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

Now a group is 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 the inverse is a function from \(G\) to itself¹, and thus 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)

Meanwhile, 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'.\]

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

Not only that, 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 operating on the right of both sides by the inverse of \(f(e)\) yields \(e'=f(e)\). That is, by the preceding argument, \(\Grp\) is also a full subcategory of \(\Magma\).

In the above argument, the following lemma was used.

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

Proof

It suffices to operate on the left or right of both sides by the inverse of \(a\).

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 For a group \((G,\star, e, {}^{-1})\), a subset \(S\) 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, omitting checking whether an identity element exists, whether it is closed under inverses, and so on.

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

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 converse direction. First, 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\), we have \(a^{-1}=e\star a^{-1}\in S\). Also, for any \(a,b\in S\), \(a\star b=a\star(b^{-1})^{-1}\in S\) holds.

For a group \(G\), given a family \((S_i)\) of subgroups, the intersection \(S=\bigcap S_i\) is again a subgroup of \(G\). This is because if we choose arbitrary \(a,b\in S\), then for all \(i\) we have \(ab^{-1}\in S_i\), and therefore \(ab^{-1}\in S\). In particular, for a group \(G\), given any subset \(S\), if we apply this argument to the collection of subgroups containing \(S\) in \(G\), we obtain 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 operating finitely many times on elements of \(S\cup S^{-1}\).

Meanwhile, for a group \((G, \star, e)\) and, compatible with \(\star\), an equivalence relation \(R\), we had confirmed that \(G/R\) has a monoid structure; moreover, \(G/R\) also has a group structure. To verify this, it suffices to show that in \(G/R\), any element \([x]\) is invertible. However, 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 any element of \(G/R\) is invertible.

From now on, when dealing with a general group, the operation is always denoted by multiplication, so that \(x\star y\) is simply written as \(xy\), the inverse of \(x\) is denoted by \(x^{-1}\), and the identity element is denoted by \(e\) as now. However, especially when a group \(G\) is abelian, the operation is denoted by addition, the inverse of \(x\) is denoted by \(-x\), and the identity element is denoted by \(0\).

Generators and Presentations of Groups

So far, we have treated groups abstractly from the axioms. Now we examine one concrete example of a group, and through this summarize how to describe a group with a small amount of data.

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

If we let the smallest rotation be \(r\) and one of the reflections be \(s\), then \(r\) returns to the identity when applied \(n\) times, and \(s\) returns to the identity when applied twice. The smallest among such positive integers are called the orders of \(r\) and \(s\), respectively. Also, in the dihedral group, “rotate then flip” and “flip then rotate in reverse” 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 therefore \(\langle r,s\rangle=D_n\).

Earlier, for a group \(G\) and its subset \(S\), we denoted the smallest subgroup containing \(S\) by \(\langle S\rangle\). 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, and the above dihedral group is a typical example generated by two elements \(r,s\).

A set of generators alone does not determine a group, and only when specifying together the equations holding among generators, each called a relation, is a group determined. Describing a group by a list of generators and relations in this way 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\]

. With respect to the vertical bar, the left is generators and the right is relations; 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. ↩