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 homomorphisms, substructures, and quotient structures defined on a magma require no modification and remain well-defined for semigroups. In particular, if \(A\) is a semigroup, then any submagma \(S\) of \(A\) is also a semigroup.

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

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

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

An arbitrary magma \(A\) has at most one identity element. For if \(e\) and \(e'\) are both 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 as a function from the singleton \(\ast\) to \(A\). (§Representable Functors, ⁋Example 2) Applying this viewpoint, 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 an identity element \(e\) for \(\star\) are all required for a monoid 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\). (§Monoid Objects, ⁋Example 2)

Some care is needed when defining monoid homomorphisms and submonoids. For example, 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.

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.

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

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

However, if a family \((S_i)\) of submonoids 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\).

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 the set \(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 this holds.

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

Theorem 7 (Eckmann-Hilton) Let two operations \(\star_1\) and \(\star_2\) exist on a set \(X\), and suppose \((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 arbitrary \(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

We finally define a group. Intuitively, this 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, we say \(x\) is a left inverse of \(y\) if \(x\star y=e\) holds. Similarly, 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\) the inverse of \(y\), and in this case \(y\) is called invertible.

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 write it instead as \(-x\). 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, inverses are 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 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.\]

However, 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 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\) satisfies the commutative law, we call it an abelian group (or commutative group).

Taking inverses 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 represented by the following diagram:

From this, we can verify that any group is a group object in \(\Set\). (§Monoid Objects, ⁋Example 4)

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\). (§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 operating on the right of both sides by the inverse of \(f(e)\), we obtain \(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

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 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\) 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 converse. First, 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\), \(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 \((S_i)\) of subgroups of a group \(G\), the intersection \(S=\bigcap S_i\) is a subgroup. For 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\). We denote this by \(\langle S\rangle\). With a little effort, we can also prove that \(\langle S\rangle\) coincides with the set of all elements obtained by operating the elements of \(S\) a finite number of times.

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

From now on, when dealing with a general group we always denote the operation by multiplication, and thus write \(x\star y\) simply as \(xy\), 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, the inverse of \(x\) by \(-x\), and the identity element by \(0\).

Generators and Presentations of Groups

Until now, we have treated groups abstractly from axioms. We now examine 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 that map a regular \(n\)-gon (\(n\ge3\)) to itself form a group under composition; this is called the dihedral group \(D_n\). Such symmetries consist of \(n\) rotations by integer multiples of \(2\pi/n\) about the center and \(n\) reflections about \(n\) axes of symmetry, so \(\lvert D_n\rvert=2n\).

Let \(r\) be the smallest rotation and \(s\) be one of the reflections; then applying \(r\) \(n\) times returns the identity element, and applying \(s\) twice returns the identity element. The smallest such positive integers are called the order of \(r\) and \(s\), respectively. Also, in the dihedral group, “rotate then flip” and “flip then rotate backward” 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 on \(r\) and \(s\), and thus \(\langle r,s\rangle=D_n\).

Earlier, for a subset \(S\) of a group \(G\), 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; the above dihedral group is the archetypal example of a group generated by two elements \(r,s\).

A group is not determined by its set of generators alone; we must also specify the equations that hold among the generators — each called a relation — before the group is finally determined. This way of describing a group by a list of generators and relations is called a presentation; for example, 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 the generators on the left from the relations on the right; this notation means 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. Except when \(G\) is an abelian group, \((-)^{-1}\) is not a group homomorphism. ↩