Definition 2.1. Semigroup.
A semigroup is a pair \((S,\ast)\text{,}\) where \(S\) is a set and \(\ast \colon S \times S \to S\) is an associative binary operation.
Chapter 2 Groups
Section 2.1 Axioms
Subsection 2.1.1 Semigroups
Example 2.2. Additive Semigroup of Numbers.
Each of the number systems (e.g. \(\N\text{,}\) \(\Z\text{,}\) \(\Q\text{,}\) \(\R\text{,}\) or \(\C\)) is a semigroup under addition.
Example 2.3. Multiplicative Semigroup of Numbers.
Each of the number systems (e.g. \(\N\text{,}\) \(\Z\text{,}\) \(\Q\text{,}\) \(\R\text{,}\) or \(\C\)) is a semigroup under multiplication.
Example 2.4. Semigroup of Endomorphisms.
Example 2.5. Additive Semigroup of Vectors.
Recall from linear algebra that addition of vectors is commutative and associative. Hence the set \(\R^n\) of \(n\)-dimensional vectors is a commutative semigroup under vector addition.
Example 2.6. Additive Semigroup of Rectangular Matrices.
Recall from linear algebra that addition of matrices is commutative and associative. Hence \(\operatorname{M}_{m \times n}(\R)\) is a commutative semigroup under matrix addition.
Example 2.7. Semigroup of Endomorphisms.
Example 2.8. Multiplicative Semigroup of Square Matrices.
Recall from linear algebra that multiplication of square matrices is associative. Hence \(\operatorname{M}_{n}(\R)\) is a semigroup under matrix multiplication.
Subsection 2.1.2 Monoids
Definition 2.9. Monoid.
Example 2.10. Additive Monoids of Numbers.
The additive identity for numbers is \(0\text{.}\) Hence the additive semigroups \(\Z\text{,}\) \(\Q\text{,}\) \(\R\text{,}\) and \(\C\) each have the structure of a commutative monoid under addition.
Warning 2.11.
Since \(0 \not \in \N\text{,}\) the natural numbers do not form an additive monoid.
Example 2.12. Multiplicative Monoids of Numbers.
The identity for multiplication of numbers is \(1\text{.}\) This endows the multiplicative semigroups \(\N\text{,}\) \(\Z\text{,}\) \(\Q\text{,}\) \(\R\text{,}\) and \(\C\) with the structure of a commutative monoid under multiplication.
Example 2.13. Monoid of Endomorphisms.
The identity function
\begin{align*}
\id_X \colon X \amp\to X\\
x \amp\mapsto x
\end{align*}
is the identity for composition on \(\End_{\Set}(X)\text{.}\) This endows \(\End_{\Set}(X)\) with the structure of a monoid.
Example 2.14. Additive Monoid of Vectors.
The additive identity for \(\R^n\) is the zero vector, \(0 = (0,0,\ldots,0)\text{.}\) This endows the \(\R^n\) with the structure of a commutative monoid under addition.
Example 2.15. Additive Monoid of Rectangular Matrices.
The additive identity for \(\operatorname{M}_{m \times n}(\R)\) is the zero matrix. This endows \(\operatorname{M}_{m \times n}(\R)\) with the structure of an commutative monoid under addition.
Example 2.16. Multiplicative Monoid of Square Matrices.
The multiplicative identity for \(\operatorname{M}_n(\R)\) is the identity matrix \(I_n\text{.}\) This endows \(\operatorname{M}_n(\R)\) with the structure of a monoid under multiplication. Note that this is not commutative in general.
Subsection 2.1.3 Groups
Definition 2.17. Group.
A group is a monoid in which every element has an inverse.
Remark 2.18.
When the operation is clear from context, we will frequently omit it and simply state that \(G\) is a semigroup/monoid/group.
Definition 2.19. Abelian Group.
A group is abelian if its operation is commutative.
Section 2.2 Basic Examples of Groups
Example 2.20. Additive Groups of Numbers.
The additive monoids \(\Z\text{,}\) \(Q\text{,}\) \(\R\text{,}\) and \(\C\) each admit inverses: for all numbers \(x\text{,}\) \(x + (-x) = 0 = -x + x\text{.}\) This endows each with the structure of an additive abelian group because addition of numbers is commutative.
Example 2.21. Additive Groups of Matrices.
Recall from linear algebra that for any \(M \in \operatorname{M}_{m \times n}(\R)\text{,}\) the additive inverse of \(M\) is the matrix \(-M\text{,}\) whose entry in row \(i\) and column \(j\) is the negative of the entry in row \(i\) and column \(j\) of \(M\text{.}\) This endows \(\operatorname{M}_{m \times n}(\R)\) with the structure of an additive abelian group.
Warning 2.22.
It is important to note that each example of a multiplicative monoids above (\(\N, \Z, \Q, \R, \C,\operatorname{M}_{m \times n}(\R),\End_{\Set}(X)\)) fails to be a group. This is because each set contains at least one element that does not have a multiplicative inverse.
-
The only element of \(\N\) that has an inverse in \(\N\) under multiplication is \(1\text{.}\) If \(n > 1\text{,}\) then the multiplicative inverse is \(1/n\) which is not and integer.
-
The monoids \(\Z\text{,}\) \(\Q\text{,}\) \(\R\text{,}\) \(\C\text{,}\) and \(\operatorname{M}_n(\R)\) also carry the structure of an additive abelian group. The additive identity, \(0\text{,}\) satisfies the condition that for all elements \(x\text{,}\) \(0x = 0 = x0\text{.}\) Since \(0 \neq 1\text{,}\) we see that \(0\) cannot have a multiplicative inverse for any of these multiplicative monoids.
-
Observe that if an endomorphism \(f \in \End_{\Set}(X)\) has an inverse under composition, \(f^{-1} \in \End_{\Set}(X)\text{,}\) then \(f\) is injective because\begin{equation*} f(x_1) = f(x_2) \implies x_1 = f^{-1} \circ f(x_1) = f^{-1} \circ f(x_2) = x_2\text{.} \end{equation*}Hence if \(X\) has at least two distinct elements, \(x_1\) and \(x_2\text{,}\) then the function\begin{align*} f \colon X \amp\to X\\ x \amp\mapsto x_1 \end{align*}is not injective because \(f(x_1) = f(x_2)\) and hence not invertible. Therefore if \(X\) has at least two elements, \(\End_{\Set}(X)\) is not a group under composition.
Theorem 2.23.
Assume \(M\) is a Monoid written multiplicatively. The subset
\begin{equation*}
M^\times = \left\{m \in M \;\middle\vert\; m\ \text{is invertible}\right\}
\end{equation*}
is a group under the binary operation on \(M\text{.}\)
Proof.
First we prove that \(M^\times\) is closed under the binary operation on \(M\text{.}\) Given \(m, n \in M^\times\text{,}\)
\begin{align*}
\left(n^{-1}m^{-1}\right)(mn) \amp= n^{-1}\left(m^{-1}(mn)\right)\\
\amp= n^{-1}\left(\left(m^{-1}m\right)n\right)\\
\amp= n^{-1}\left((1)n\right)\\
\amp= n^{-1}n\\
\amp= 1
\end{align*}
and
\begin{align*}
(mn)\left(n^{-1}m^{-1}\right) \amp= m\left(n\left(n^{-1}m^{-1}\right)\right)\\
\amp= m\left(\left(nn^{-1}\right)m^{-1}\right)\\
\amp= m\left(1m^{-1}\right)\\
\amp= mm^{-1}\\
\amp= 1
\end{align*}
by associativity of the binary operation on \(M\text{.}\) Hence \(mn\) has an inverse, \(n^{-1}m^{-1}\text{,}\) and so \(M^\times\) is closed under the binary operation on \(M\text{.}\) Moreover, the binary operation remains associative when restricted to \(M^\times\text{.}\) This establishes that \(M^\times\) is a semigroup under the binary operation on \(M\text{.}\)
To see that \(M^\times\) is a monoid, we observe that \(1 \in M^\times\) because \(1^{-1} = 1\text{.}\) Finally, we note that every element of \(M^\times\) has an inverse by definition. Therefore \(M^\times\) is a group under the binary operation on \(M\text{.}\)
Example 2.24. Multiplicative Groups of Numbers.
For \(\Q\) or \(\R\text{,}\) the only element without an inverse is \(0\text{.}\) Hence \(\Q^\times = \Q \setminus \{0\}\) and \(\R^\times = \R \setminus \{0\}\) form a group under multiplication by Theorem 2.23. In both cases, the multiplicative identity is \(1\) and the multiplicative inverse of an element \(x\) is the usual fraction \(1/x\text{.}\)
Example 2.25. The General Linear Group.
Recall from linear algebra that a matrix \(M \in \operatorname{M}_n(\R)\) is invertible if and only if \(\det{M} \neq 0\text{.}\) By Theorem 2.23, the subset of invertible matrices
\begin{equation*}
\operatorname{GL}_n(\R) = \left\{M \in \operatorname{M}_n(\R) \;\middle\vert\; \det{M} \neq 0\right\}
\end{equation*}
forms a group under matrix multiplication called the General Linear Group of Degree \(n\).
Example 2.26. The Symmetric Groups.
The subset of invertible endomorphisms is known as the Symmetric Group on \(X\), \(S_X\text{.}\) The elements of \(S_X\) are called permutations.
Remark 2.27.
Depending on the author, you may also see the set of invertible endomorphisms written \(\mathfrak{S}_X\text{,}\) \(\Sigma_X\text{,}\) \(X!\text{,}\) or \(\operatorname{Sym}(X)\text{.}\)
Example 2.28. Group-Valued Functions.
If \(G\) is a group and \(X\) is any set, then the set \(G^X\) of functions with domain \(X\) and codomain \(G\) form a group under the pointwise product from Exercise Group 1.3.1–4.
Section 2.3 Basic Properties of Groups
The following properties generalize the familiar operations that we can perform on equations that preserve the set of solutions:
Theorem 2.29. Left Cancellation.
Assume \(G\) is a group. For all \(a, b, c \in G\text{,}\) if \(ab = ac\text{,}\) then \(b = c\text{.}\)
Proof.
Assume \(ab = ac\) and write
\begin{align*}
b \amp= 1b\\
\amp= \left(a^{-1}a\right)b\\
\amp= a^{-1}\left(ab\right)\\
\amp= a^{-1}\left(ac\right)\\
\amp= \left(a^{-1}a\right)c\\
\amp= 1c\\
\amp= c\text{.}
\end{align*}
Theorem 2.30. Right Cancellation.
Assume \(G\) is a group. For all \(a, b, c \in G\text{,}\) if \(ba = ca\text{,}\) then \(b = c\text{.}\)
Proof.
The proof is essentially the same as Theorem 2.29 and is left as an exercise.
Example 2.31.
We are tacitly using cancellation laws for the multiplicative group \(\R^\times\) every time we solve an equation like
\begin{equation*}
3x = 6 \quad\text{or}\quad x2 = 6\text{.}
\end{equation*}
We would normally say that we divide both sides of the equation by \(3\) or by \(2\text{.}\) However, in the language of abstract algebra, we would rewrite these two equations as
\begin{equation*}
3x = 3(2) \quad\text{and}\quad x2 = 3(2)
\end{equation*}
then apply left cancellation to the first to see \(x = 2\) and right cancellation to the right to see \(x = 3\text{.}\) Essentially, this is the proof that the basic algebra mantra that dividing both sides of an equation by a non-zero number preserves the equality.
Similarly, we could consider an equation like
\begin{equation*}
x + 2 = 3 \quad\text{or}\quad 3 + x = 2\text{.}
\end{equation*}
Again, we would normally think about this as subtracting 2 or 3 from both sides of the equation. In the language of abstract algebra, we would rewrite these two equations as
\begin{equation*}
x + 2 = 1 + 2 \quad\text{and}\quad 3 + x = 3 + (-1)
\end{equation*}
and conclude that \(x = 1\) in the first case and \(x = -1\) in the second. Again, this is the proof of the basic algebra mantra that adding any number to both sides of an equation preserves the equality.
Corollary 2.32. Linear Equations in Groups.
Assume \(G\) is a group.
Proof.
We prove (1) and leave (2) as an exercise for the reader.
Let \(a,b \in G\) be given. For existence, we observe \(a^{-1} b\) satisfies
\begin{equation*}
a\left(a^{-1}b\right) = \left(aa^{-1}\right)b = 1b = b
\end{equation*}
For uniqueness, assume that \(x \in G\) satisfies \(ax = b\text{.}\) Then
\begin{equation*}
ax = b = a\left(a^{-1}b\right)
\end{equation*}
implies \(x = a^{-1}b\) by left cancellation. Therefore for all \(a,b \in G\text{,}\) there exists a unique solution to the equation \(ax = b\text{.}\)
Corollary 2.33. The Inverse of a Product.
Proof.
Let \(a,b \in G\) be given. By Corollary 2.32, it suffices to observe that \((ab)^{-1}\) and \(b^{-1}a^{-1}\) are both solutions to the equation \((ab)x = 1\text{.}\) Therefore \((ab)^{-1} = b^{-1}a^{-1}\) by uniqueness.
Exercises 2.4 Exercises for Undergrads & Grads
1.
Prove Theorem 2.30.
2.
Prove the second assertion in Corollary 2.32
Solution.
Let \(a,b \in G\) be given. For existence, we observe that
\begin{equation*}
\left(ba^{-1}\right)a = b\left(a^{-1}a\right)
= b(1) = b
\end{equation*}
is a solution to \(ya = b\text{.}\)
For uniqueness, assume that \(y \in G\) satisfies \(ya = b\text{.}\) Then
\begin{equation*}
ya = b = \left(ba^{-1}\right)a
\end{equation*}
implies \(y = ba^{-1}\) by right cancellation.
3.
Assume \(G\) is a group with finitely many elements. Prove that if \(G\) has an even number of elements, then there exists \(a \in G \setminus \{1\}\) such that \(aa = 1\text{.}\)
Hint.
Solution.
Assume \(G\) is a finite group with identity \(1\) and an even number of elements. Suppose to the contrary that for all \(a \neq 1\text{,}\) \(aa \neq 1\text{.}\) Observe this condition implies \(a \neq a^{-1}\text{,}\) so for all \(a \in G \setminus \{1\}\text{,}\) the set \(\left\{a,a^{-1}\right\}\) has exactly two elements. If there are \(k\) such pairings, then \(G \setminus \{1\}\) contains \(2k\) elements, an even number. This implies \(G = \left(G \setminus \{1\}\right) \cup \{1\}\) has \(2k+1\) elements, contrary to the assumption that \(G\) has an even number of elements. Therefore there exists \(a \in G \setminus \{1\}\) such that \(aa = 1\text{.}\)
4.
Let \(G\) be a group and let \(a,b \in G\text{.}\) Show that \((ab)^{-1} = a^{-1}b^{-1}\) if and only if \(ab=ba\text{.}\)
Solution.
Let \(a,b \in G\) be given. Assume \((ab)^{-1} = a^{-1}b^{-1}\) and write
\begin{align*}
ba \amp= \left(b^{-1}\right)^{-1}\left(a^{-1}\right)^{-1}\\
\amp= \left(a^{-1}b^{-1}\right)^{-1}\\
\amp= \left(\left(ab\right)^{-1}\right)^{-1}\\
\amp= ab
\end{align*}
Therefore if \((ab)^{-1} = a^{-1}b^{-1}\text{,}\) then \(ab = ba\text{.}\)
Conversely, assume \(ab = ba\text{.}\) Write
\begin{equation*}
(ab)^{-1} = (ba)^{-1} = a^{-1}b^{-1}\text{.}
\end{equation*}
Therefore if \(ab = ba\text{,}\) then \((ab)^{-1} = a^{-1}b^{-1}\text{.}\)
5.
Assume \(G\) is a group. Prove that if for all \(x \in G\text{,}\) \(xx = 1\text{,}\) then \(G\) is abelian.
Hint.
Solution.
Assume \(G\) is a group and for all \(x \in G\text{,}\) \(xx =1\text{.}\) For all \(x \in G\text{,}\) \(xx = 1\) and \(xx^{-1} = 1\) imply \(x = x^{-1}\) by Corollary 2.32. Hence for all \(a,b \in G\text{,}\) \((ab)(ab) = 1\) implies
\begin{equation*}
(ab)^{-1} = ab = a^{-1}b^{-1}\text{.}
\end{equation*}
and thus \(ab = ba\) by Exercise 2.4.4. Therefore if for all \(x \in G\text{,}\) \(xx = 1\text{,}\) then \(G\) is abelian.
Exercises 2.5 Exercises for Grads
Use the set \(\Q(\sqrt{2}) = \left\{a + b\sqrt{2} \;\middle\vert\; a,b \in \Q\right\}\) to complete the following.
1.
Prove that \(\Q(\sqrt{2})\) is an abelian group under the binary operation
\begin{equation*}
a + b\sqrt{2} + c + d\sqrt{2} = (a + c) + (b + d)\sqrt{2}\text{.}
\end{equation*}
Solution.
First, we observe that for all \(a,b \in \Q\text{,}\) \(a + b\sqrt{2} \in \R\text{.}\) Since \(\Q(\sqrt{2}) \subseteq \R\) is closed under addition, it inherits associativity and commutativity. The identity is precisely the identity element of \(\R\text{,}\) \(0 = 0 + 0\sqrt{2} \in \Q(\sqrt{2})\) and the additive inverse of \(a + b\sqrt{2} \in \Q(\sqrt{2})\) is
\begin{equation*}
-(a + b\sqrt{2}) = (-a) + (-b)\sqrt{2} \in \Q(\sqrt{2})\text{.}
\end{equation*}
Therefore \(\Q(\sqrt{2})\) is an abelian group under addition.
2.
Prove that the non-zero elements of \(\Q(\sqrt{2})\) form an abelian group under the binary operation
\begin{equation*}
(a + b\sqrt{2})(c + d\sqrt{2}) = (ac + 2bd) + (ad + bc)\sqrt{2}\text{.}
\end{equation*}
Hint.
Solution.
Again, we observe that \(\Q(\sqrt{2}) \subseteq \R\) is closed under multiplication, hence it inherits associativity and commutativity. The multiplicative identity is precisely the multiplicative identity element of \(\R\text{,}\) \(1 = 1 + 0\sqrt{2} \in \Q(\sqrt{2})\text{.}\) For every non-zero element, \(a + b\sqrt{2}\text{,}\) we observe that
\begin{equation*}
(a + b\sqrt{2})(a - b\sqrt{2}) = a^2 - 2b^2 \in \Q \setminus\{0\}
\end{equation*}
and thus the multiplicative inverse in \(\R\) is
\begin{align*}
\frac{1}{a + b\sqrt{2}} \amp= \left(\frac{a - b\sqrt{2}}{a - b\sqrt{2}}\right)\frac{1}{a + b\sqrt{2}}\\
\amp= \frac{a - b\sqrt{2}}{a^2 - 2b^2}\\
\amp= \left(\frac{a}{a^2 - 2b^2}\right) + \left(\frac{-b}{a^2 - 2b^2}\right)\sqrt{2} \in \Q(\sqrt{2})
\end{align*}
Therefore \(\Q(\sqrt{2}) \setminus\{0\}\) is an abelian group under multiplication.
