← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 9

Groups

Taught 22 Aug 2026

Operations and Semigroups

The last chapter produced a set with a multiplication on it. The permutations of a set compose, the composite is again a permutation, the composition is associative, there is an identity, and every element has an inverse. None of those five facts mentions what a permutation is. This chapter keeps the five facts and drops the permutations. Many other sets with an operation satisfy the same five facts, so a result proved from them holds for all of these at once.

Operations

Definition 9.1 (Operation).

Let $S$ be a non-empty set. An operation on $S$ is a function

* \, : \, S \times S \to S.

One writes $a * b$ for the value of $*$ at the ordered pair $(a, b)$ . The pair $(S, *)$ is a set equipped with an operation.

Two things are asked for. The first is that a value is named for every ordered pair of elements, which is what makes $*$ a function on all of $S \times S$ . The second is that the value lands back in $S$ , and one says that $S$ is closed under $*$ . Writing $a * b$ instead of $*\bigl((a,b)\bigr)$ is only notation; the object underneath is still a function, and two operations are equal exactly when they agree at every pair.

Example 9.2 (Operations already in hand).

$(\mathbb{N}_0, +)$ and $(\mathbb{N}_0, \cdot)$ , with addition as built in the chapter on the natural numbers and multiplication as defined in its problems. So are $(\mathbb{N}, +)$ and $(\mathbb{N}, \cdot)$ , since a sum or product of positive numbers is positive.
For a non-empty set $A$ , the Cartesian power $A^A$ , the set of all functions $A \to A$ , carries composition, $(f, g) \mapsto f \circ g$ . Its subset $S_A$ of permutations is closed under the same operation, since composition sends bijections to bijections; that closure is what let us write $\sigma\lambda$ at all.
For any set $X$ , the power set $\mathcal{P}(X)$ carries both $\cup$ and $\cap$ .
On a totally ordered set $M$ , the rule sending $(a, b)$ to whichever of $a$ and $b$ is the larger is an operation, since comparability names one of them and antisymmetry makes the choice unambiguous when they are equal.
On any non-empty $S$ , the rule $a * b \defeq a$ (keep the left factor) is an operation.

Example 9.3 (Two failures of closure).

Call $n \in \mathbb{N}$ prime if $n > 1$ and the only $k \in \mathbb{N}$ dividing $n$ are $1$ and $n$ , in the sense of divisibility. The primes are closed under neither addition nor multiplication: $3 + 5 = 8$ and $3 \cdot 5 = 15$ , and neither is prime. Restricting $+$ or $\cdot$ to the primes therefore does not produce an operation on them, and the restricted function is not a function into the primes at all.

The odd numbers show that the two can differ. They are closed under multiplication, since the remainder classes write two odd numbers as $2j + 1$ and $2k + 1$ , whose product is $2(2jk + j + k) + 1$ ; they are not closed under addition, since $1 + 1 = 2$ .

Definition 9.4 (Closed subsets).

Let $*$ be an operation on $S$ and let $S' \subset S$ be non-empty. Then $S'$ is closed under $*$ if $a * b \in S'$ for all $a, b \in S'$ . In that case the restriction of $*$ to $S' \times S'$ is an operation on $S'$ , and $(S', *)$ is a substructure of $(S, *)$ .

Closure is all that must be checked. Every named structure below (semigroup, group, subgroup) is this definition with further conditions added, and each further condition is either always inherited or always needs checking.

Example 9.5 (A substructure of the natural numbers).

Fix $\ell \in \mathbb{N}$ and let $\ell\mathbb{N}_0 \defeq \{n \in \mathbb{N}_0 \mid n = \ell k \text{ for some } k \in \mathbb{N}_0\}$ be the multiples of $\ell$ . If $n = \ell k$ and $m = \ell j$ then $n + m = \ell(k + j)$ by distributivity and $n \cdot m = \ell(k \cdot \ell \cdot j)$ , so $\ell\mathbb{N}_0$ is closed under both operations and is a substructure of $(\mathbb{N}_0, +)$ and of $(\mathbb{N}_0, \cdot)$ .

Associativity and Commutativity

Definition 9.6 (Associative and commutative operations).

Let $*$ be an operation on $S$ .

The operation is associative if $(a * b) * c = a * (b * c)$ for all $a, b, c \in S$ . In that case $(S, *)$ is a semigroup.
The operation is commutative if $a * b = b * a$ for all $a, b \in S$ . A commutative semigroup is also called abelian.

Both conditions are equalities required to hold identically, so both are inherited by every substructure: a law true of all elements of $S$ is in particular true of all elements of a subset. We note this once here rather than re-checking it in each example.

Example 9.7 (Which of them associate).

Addition and multiplication on $\mathbb{N}_0$ are associative and commutative by the laws of addition and the corresponding laws of multiplication. Composition on $A^A$ is associative by the theorem on associativity of composition, so $A^A$ and $S_A$ are semigroups under $\circ$ . Union and intersection on $\mathcal{P}(X)$ are associative and commutative by the basic properties of unions and by the algebra of intersection. Taking the larger of two elements of a totally ordered set is associative and commutative, both sides of each law naming the largest of the elements involved.

Keeping the left factor, $a * b \defeq a$ , is associative, since both $(a * b) * c$ and $a * (b * c)$ are $a$ , and is not commutative as soon as $S$ has two distinct points.

Composition shows that the two conditions are independent. It is associative on every $A^A$ , and already in $S_3$ there are permutations with $\sigma\lambda \neq \lambda\sigma$ , as the worked product of the last chapter showed in $S_4$ . Associativity is the more useful of the two, because of the next theorem.

Products of Many Factors

Definition 9.8 (Left-associated product).

Let $(S, *)$ be a set with an operation and let $a_1, \ldots, a_n \in S$ with $n \in \mathbb{N}$ . The left-associated product is defined by the recursion

p(a_1) \defeq a_1, \qquad p(a_1, \ldots, a_{k+1}) \defeq p(a_1, \ldots, a_k) * a_{k+1} \quad (1 \leqslant k < n).

A full bracketing of $a_1 * \cdots * a_n$ is either the single term $a_1$ , when $n = 1$ , or an expression $L * R$ in which $L$ is a full bracketing of $a_1 * \cdots * a_k$ and $R$ is a full bracketing of $a_{k+1} * \cdots * a_n$ , for some $1 \leqslant k < n$ .

Theorem 9.9 (General associativity).

Let $(S, *)$ be a semigroup, let $n \in \mathbb{N}$ and let $a_1, \ldots, a_n \in S$ .

For every $1 \leqslant k < n$ ,

p(a_1, \ldots, a_n) = p(a_1, \ldots, a_k) * p(a_{k+1}, \ldots, a_n).

Every full bracketing of $a_1 * \cdots * a_n$ equals $p(a_1, \ldots, a_n)$ .
If $*$ is commutative and $(b_1, \ldots, b_n)$ is obtained from $(a_1, \ldots, a_n)$ by exchanging two neighbouring entries, then $p(b_1, \ldots, b_n) = p(a_1, \ldots, a_n)$ .

Discussion.

This is the theorem on general associativity and neighbour swaps with $+$ replaced by $*$ , and the earlier proof never mentioned $\mathbb{N}_0$ : it used the associativity of $+$ for the first two parts and its commutativity for the third, and nothing else. So the argument transfers unchanged. We repeat the main step, which is the first part, the splitting identity, which says a left-associated product may be cut anywhere; it is an induction on the length of the second block, with the recursion clause as the base and a single application of associativity in the step. The second part is then an induction on $n$ in which a bracketing $L * R$ is split at its own top-level cut and the two halves identified by the inductive hypothesis. The third puts the exchanged pair in the middle by two applications of the first part, exchanges it by commutativity, and reassembles.

Proof.

For the first part, fix $k$ and induct on the length $m$ of the second block, so that $n = k + m$ . If $m = 1$ the assertion is $p(a_1, \ldots, a_{k+1}) = p(a_1, \ldots, a_k) * a_{k+1}$ , which is the recursion clause. Suppose it holds at $m$ . Then

\begin{aligned} p(a_1, \ldots, a_{n+1}) &= p(a_1, \ldots, a_n) * a_{n+1} \\ &= \bigl(p(a_1, \ldots, a_k) * p(a_{k+1}, \ldots, a_n)\bigr) * a_{n+1} \\ &= p(a_1, \ldots, a_k) * \bigl(p(a_{k+1}, \ldots, a_n) * a_{n+1}\bigr) \\ &= p(a_1, \ldots, a_k) * p(a_{k+1}, \ldots, a_{n+1}), \end{aligned}

by the recursion clause, the inductive hypothesis, associativity, and the recursion clause again.

The second and third parts are the two parts of the earlier theorem, whose proof used only the binary laws just used here; substituting $*$ for $+$ throughout gives the argument verbatim, with the first part standing in for the splitting identity recorded there.

The second part allows us to write $a_1 * a_2 * \cdots * a_n$ with no brackets at all in a semigroup, and we do so from here on. The third part allows exchanging neighbours when the operation commutes, and neighbours are enough, because the last chapter proved that every rearrangement is a string of neighbour exchanges.

Corollary 9.10 (Rearranging a product).

Let $(S, *)$ be an abelian semigroup, let $a_1, \ldots, a_n \in S$ and let $\sigma \in S_n$ . Then

a_{\sigma(1)} * a_{\sigma(2)} * \cdots * a_{\sigma(n)} = a_1 * a_2 * \cdots * a_n.

Proof.

The proposition that neighbour swaps suffice writes $\sigma$ as a product $\pi_1 \pi_2 \cdots \pi_m$ of transpositions of neighbouring points. Applying the third part of the theorem once for each $\pi_i$ carries the list $(a_{\sigma(1)}, \ldots, a_{\sigma(n)})$ to $(a_1, \ldots, a_n)$ without changing the left-associated product, and the second part identifies that product with the bracket-free expression on either side.

Remark.

The corollary uses results from three chapters. The bracketing was settled for sums in the chapter on sequences, the reduction of an arbitrary rearrangement to neighbour exchanges was set as a problem there and proved in the chapter on permutations, and the assembly is one line. Nothing about $\mathbb{N}_0$ was used, so the statement holds for unions, for intersections, for the larger-of-two operation, and for every abelian semigroup yet to be met.

Problem 9.1.

On $S = \{a, b, c\}$ define an operation by the table

\begin{array}{c|ccc} * & a & b & c \\ \hline a & a & b & c \\ b & b & c & a \\ c & c & a & b \end{array}

the entry in row $x$ and column $y$ being $x * y$ . Decide whether $*$ is associative and whether it is commutative.

Problem 9.2.

Let $S$ be non-empty and define $a * b \defeq b$ , keeping the right factor. Decide whether $*$ is associative and whether it is commutative, and compare with the left-factor rule.

Problem 9.3.

Let $(S, *)$ be an abelian semigroup and let $a_{j,k} \in S$ for $j \in \langle m \rangle$ and $k \in \langle n \rangle$ . Show that forming the products along the rows and then combining, and forming them along the columns and then combining, give the same element of $S$ .

Identity, Inverses and Groups

A semigroup asks one law of its operation. Two further conditions, an identity element and an inverse for each element, give a group. We look at each condition separately first.

The Identity

Definition 9.11 (Identity element).

Let $(S, *)$ be a set with an operation. An element $e \in S$ is an identity for $*$ if

e * a = a * e = a \qquad \text{for every } a \in S.

A semigroup with an identity is called a monoid.

An operation written additively usually has its identity written $0$ , and one written multiplicatively usually has it written $1$ . The choice is only notation. The definition asks for the law on both sides, and the next section shows why one side alone is weaker.

Proposition 9.12 (Uniqueness of the identity).

An operation has at most one identity.

Discussion.

The claim is a uniqueness statement, so we suppose two identities $e$ and $e'$ and derive $e = e'$ . We evaluate one product in two ways: reading $e * e'$ with the left factor as the identity gives $e'$ , reading it with the right factor as the identity gives $e$ , so the two are equal. No associativity is needed, which is why the proposition is stated for an operation and not for a semigroup.

Proof.

Let $e$ and $e'$ be identities for $*$ . Since $e$ is an identity, $e * e' = e'$ . Since $e'$ is an identity, $e * e' = e$ . Hence $e = e'$ .

Example 9.13 (Identities in the running examples).

The identity for $+$ on $\mathbb{N}_0$ is $0$ , and the identity for $\cdot$ on $\mathbb{N}_0$ and on $\mathbb{N}$ is $1$ . Composition on $A^A$ has the identity map $\mathrm{id}_A$ as its identity, by the identity laws, and the same map serves for $S_A$ . On $\mathcal{P}(X)$ the identity for $\cup$ is $\emptyset$ and the identity for $\cap$ is $X$ . Taking the larger of two elements of a totally ordered set has an identity exactly when the set has a minimum, which is then the identity.

Two of the examples have none. Keeping the left factor has no identity once $S$ has two distinct points: an identity $e$ would satisfy $e * a = a$ for every $a$ , whereas $e * a = e$ , forcing every $a$ to equal $e$ . And $(\mathbb{N}, +)$ has no identity, not because no element behaves like one but because the element that would, namely $0$ , is not in the set.

Inverses

Definition 9.14 (Inverse element).

Let $(S, *)$ be a set with an operation and with identity $e$ , and let $a \in S$ . An element $b \in S$ is an inverse of $a$ if

a * b = b * a = e.

If $a$ has an inverse, $a$ is invertible.

Multiplicative notation writes $a^{-1}$ for the inverse and additive notation writes $-a$ . The two-sided demand is the same shape as the one made of inverse functions, and for the same reason: a one-sided inverse is weaker unless associativity lets us combine the two sides, as in the next proposition.

Proposition 9.15 (Uniqueness of inverses).

Let $(S, *)$ be a monoid and let $a \in S$ be invertible. Then $a$ has exactly one inverse.

Discussion.

Uniqueness again, so we take two inverses $b$ and $c$ of the same $a$ and show they agree. We form one expression that can be read as either: put $a$ between them, as $b * a * c$ , and bracket it the two available ways. Bracketing to the right uses that $c$ is an inverse and leaves $b$ ; bracketing to the left uses that $b$ is one and leaves $c$ . The re-bracketing uses associativity, and without it the argument fails.

Proof.

Let $b$ and $c$ be inverses of $a$ . Then

\begin{aligned} b &= b * e && \text{($e$ is the identity)} \\ &= b * (a * c) && \text{($c$ is an inverse of $a$)} \\ &= (b * a) * c && \text{(associativity)} \\ &= e * c && \text{($b$ is an inverse of $a$)} \\ &= c && \text{($e$ is the identity)}. \end{aligned}

So one may speak of the inverse of an invertible element, and write $a^{-1}$ for it. Two consequences follow at once. First, $e$ is invertible with $e^{-1} = e$ , since $e * e = e$ . Second, $(a^{-1})^{-1} = a$ : the defining equations $a * a^{-1} = a^{-1} * a = e$ are unchanged when $a$ and $a^{-1}$ are exchanged, so $a$ is an inverse of $a^{-1}$ , and uniqueness makes it the inverse.

Proposition 9.16 (Inverse of a product).

Let $(S, *)$ be a monoid and let $a, b \in S$ be invertible. Then $a * b$ is invertible and

(a * b)^{-1} = b^{-1} * a^{-1}.

Discussion.

There are two assertions, an existence claim and a formula, and one calculation settles both: if the element named on the right multiplies with $a * b$ to give $e$ on both sides, then $a * b$ is invertible and, by the uniqueness just proved, that element is the inverse. The check is a product of four factors, which general associativity lets us write without brackets; cancelling the inner pair $a^{-1} * a$ leaves $b^{-1} * b$ , and cancelling that leaves $e$ . The order is reversed so that the inner pair is adjacent.

Proof.

Using general associativity to drop brackets,

(b^{-1} * a^{-1}) * (a * b) = b^{-1} * (a^{-1} * a) * b = b^{-1} * e * b = b^{-1} * b = e,

and in the same way $(a * b) * (b^{-1} * a^{-1}) = a * (b * b^{-1}) * a^{-1} = a * a^{-1} = e$ . So $b^{-1} * a^{-1}$ is an inverse of $a * b$ , and by uniqueness it is the inverse.

The reversal is not new. It is the inverse of a composition met for functions, and the rule $(\sigma\lambda)^{-1} = \lambda^{-1}\sigma^{-1}$ used without comment for permutations. The proof here covers both, and every other monoid as well.

Proposition 9.17 (The invertible elements).

Let $(S, *)$ be a monoid with identity $e$ and let

G \defeq \{a \in S \mid a \text{ is invertible}\}.

Then $e \in G$ ; if $a, b \in G$ then $a * b \in G$ ; and if $a \in G$ then $a^{-1} \in G$ . So $(G, *)$ is a monoid with identity $e$ , in which every element is invertible.

Discussion.

Three closure claims and then a summary that follows from them. That $e \in G$ was noted above, $e$ being its own inverse. That $G$ is closed under $*$ is the previous proposition, which not only says $a * b$ is invertible but names the inverse, so nothing further is needed. That $G$ is closed under inversion is the remark that $(a^{-1})^{-1} = a$ , which exhibits an inverse for $a^{-1}$ . The summary then needs only that associativity and the identity laws are inherited by a subset, which they are, being laws required of all elements.

Proof.

From $e * e = e$ we get $e \in G$ with $e^{-1} = e$ . If $a, b \in G$ then $a * b$ is invertible by the previous proposition, so $a * b \in G$ , and $G$ is closed under $*$ . If $a \in G$ then $(a^{-1})^{-1} = a$ exhibits $a$ as an inverse of $a^{-1}$ , so $a^{-1} \in G$ .

Hence $G$ is a closed subset containing $e$ , and it inherits associativity and the identity laws from $S$ . Each of its elements is invertible, and its inverse lies in $G$ , so $(G, *)$ is a monoid in which every element is invertible.

Example 9.18 (Who is invertible).

In $(\mathbb{N}_0, +)$ only $0$ is invertible, since $a + b = 0$ forces $a = b = 0$ by the corollary on sums that vanish. In $(\mathbb{N}_0, \cdot)$ only $1$ is invertible. In $\mathcal{P}(X)$ under $\cup$ only $\emptyset$ is invertible, and under $\cap$ only $X$ .

The main example is composition. In the monoid $A^A$ the invertible elements are exactly the bijections $A \to A$ , by the theorem on invertibility and bijections; that is to say, they are exactly the permutations, and the set they form is $S_A$ . The previous proposition, applied to $A^A$ , is therefore the statement that $S_A$ is closed under composition and under inversion. We proved this twice already, once for functions and once for permutations; here it follows from a proposition about monoids.

Problem 9.4.

Let $*$ be an operation on $S$ with a left identity $\ell$ , meaning $\ell * a = a$ for every $a$ , and a right identity $r$ , meaning $a * r = a$ for every $a$ . Show that $\ell = r$ , and that it is then an identity. No associativity is needed.

Problem 9.5.

Show that under the left-factor rule $a * b \defeq a$ every element of $S$ is a right identity, and that under the right-factor rule $a * b \defeq b$ every element is a left identity. So a one-sided identity need be neither unique nor accompanied by one on the other side, and neither rule has an identity once $S$ has two distinct points.

Problem 9.6.

Let $(S, *)$ be a monoid and let $a, b, c \in S$ satisfy $a * b = e$ and $b * c = e$ . Show that $a = c$ , so that $b$ is a two-sided inverse of $a$ . Which hypothesis fails if $S$ is only a set with an operation?

Groups

Definition 9.19 (Group).

A group is a monoid in which every element is invertible: a set $G$ with an associative operation, an identity $e$ , and an inverse for each of its elements. A group whose operation is commutative is abelian, in the sense already fixed for semigroups.

The proposition on invertible elements now reads: the invertible elements of any monoid form a group. Applied to $A^A$ under composition it says that $S_A$ is a group, without using anything about permutations.

Example 9.20 (Groups already met).

For any non-empty set $A$ , the symmetric group $S_A$ under composition. For $A = \langle n \rangle$ this is $S_n$ , with $\#S_n = n!$ by the count of bijections.
The dihedral group $D_n \subset S_n$ . That it is closed under products and inverses was a problem of the last chapter, and the identity permutation is a symmetry of every polygon, so $D_n$ is a group with $\#D_n = 2n$ .
The even permutations in $S_n$ , closed under products and inverses by another problem there. For $n \geqslant 2$ this group is written $A_n$ and called the alternating group on $n$ letters.
The one-element set $\{e\}$ with the only operation available to it. It is a group, called the trivial group, and it is the smallest group, since a group must contain an identity.
$S_2 = \{\mathrm{id}, \tau_{1,2}\}$ , the smallest group with more than one element. Its whole multiplication is $\tau_{1,2} * \tau_{1,2} = \mathrm{id}$ , which is the proposition that a transposition is its own inverse.

None of $(\mathbb{N}_0, +)$ , $(\mathbb{N}, +)$ and $(\mathbb{N}_0, \cdot)$ is a group. The first is a monoid in which only $0$ is invertible; the second has no identity at all; the third is a monoid in which only $1$ is invertible.

Remark (The groups not yet available).

The familiar first examples of groups are the integers under addition and the non-zero rationals or reals under multiplication. We do not have them: the integers are the subject of the next chapter, and they are built by adding to $(\mathbb{N}_0, +)$ the inverses it lacks. The examples above are the ones already constructed, and they are enough to prove everything in this chapter; the arithmetic ones become further examples once they are built.

The definition asks for a two-sided identity and two-sided inverses, four conditions in all. The two left-handed ones already imply the others.

Theorem 9.21 (A left identity with left inverses is enough).

Let $(G, *)$ be a semigroup. Suppose there is $\ell \in G$ with $\ell * a = a$ for every $a \in G$ , and suppose that for every $a \in G$ there is $b \in G$ with $b * a = \ell$ . Then $\ell$ is an identity, every such $b$ is an inverse of $a$ , and $(G, *)$ is a group.

Discussion.

The statement is an implication from a shortened list of axioms to the full one, so we assume the two left-handed conditions and must produce the two right-handed ones. We apply the hypotheses repeatedly and re-bracket, in a particular order: the right-inverse law must come first, because the right-identity law is proved from it.

To get $a * b = \ell$ , take a left inverse $b$ of $a$ and then a left inverse $c$ of $b$ . Insert $\ell$ in front of $a * b$ using the left identity, replace that $\ell$ by $c * b$ , and re-bracket so that $b * a$ becomes adjacent; that inner pair becomes $\ell$ , which the left identity removes, leaving $c * b = \ell$ . Once $a * b = \ell$ is known, $a * \ell$ can be written as $a * (b * a)$ , re-bracketed to $(a * b) * a = \ell * a = a$ , which is the right-identity law. No appeal to uniqueness is needed anywhere; the calculation gives the two-sided laws directly.

Proof.

Fix $a \in G$ , choose $b \in G$ with $b * a = \ell$ , and choose $c \in G$ with $c * b = \ell$ . Then

\begin{aligned} a * b &= \ell * (a * b) = (c * b) * (a * b) \\ &= c * \bigl((b * a) * b\bigr) = c * (\ell * b) = c * b = \ell, \end{aligned}

using the left identity, the choice of $c$ , associativity, the choice of $b$ , and the left identity again. So $b$ is a right inverse of $a$ as well as a left one.

Consequently

a * \ell = a * (b * a) = (a * b) * a = \ell * a = a,

so $\ell$ is a right identity as well as a left one. Hence $\ell$ is an identity, each $a$ has the two-sided inverse $b$ , and $(G, *)$ is a group.

Remark (Right axioms, mixed axioms).

The same argument with left and right exchanged shows that a right identity together with right inverses is equally sufficient. A left identity paired with right inverses is not enough, and a counterexample with two elements exists; producing one is a problem below. So the two halves of the definition may be dropped in matching pairs but not in mismatched ones.

Proposition 9.22 (Cancellation in a group).

Let $(G, *)$ be a group and let $a, x_1, x_2, y_1, y_2 \in G$ . If $a * x_1 = a * x_2$ then $x_1 = x_2$ ; and if $y_1 * a = y_2 * a$ then $y_1 = y_2$ .

Discussion.

Two implications of the same shape, and the second is the mirror image of the first, so only one need be written out. In each the hypothesis is an equation with a common factor on one side, and the way to remove a factor is to introduce its inverse on that same side and re-bracket: the inverse then meets $a$ and the pair becomes $e$ , which the identity law removes. Both the associativity and the existence of $a^{-1}$ are used, and each once.

Proof.

Suppose $a * x_1 = a * x_2$ . Then

\begin{aligned} x_1 &= e * x_1 = (a^{-1} * a) * x_1 = a^{-1} * (a * x_1) \\ &= a^{-1} * (a * x_2) = (a^{-1} * a) * x_2 = e * x_2 = x_2. \end{aligned}

The second implication is the same computation with $a^{-1}$ applied on the right.

Cancellation says exactly that, for each fixed $a$ , the maps $x \mapsto a * x$ and $y \mapsto y * a$ are injective. When $G$ is finite they are therefore bijective, so each of the equations $a * x = b$ and $y * a = b$ has exactly one solution. In fact they are bijective whether or not $G$ is finite, since $x \mapsto a^{-1} * x$ undoes the first; the finite case is worth noting separately, because it uses nothing about inverses and so applies to semigroups that are not groups.

Definition 9.23 (Regular semigroup).

A monoid in which cancellation holds on both sides (that is, $a * x_1 = a * x_2$ implies $x_1 = x_2$ , and $y_1 * a = y_2 * a$ implies $y_1 = y_2$ ) is called regular.

Every group is regular, by the proposition. The converse fails, and our standard examples show it.

Example 9.24 (The natural numbers cancel).

$(\mathbb{N}_0, +)$ is regular, since $x + z = y + z$ implies $x = y$ by the cancellation problem of the chapter on the natural numbers. It is not a group. Multiplication on $\mathbb{N}$ is regular too: if $a \cdot x_1 = a \cdot x_2$ with $a$ positive and, say, $x_1 \leqslant x_2$ , write $x_2 = x_1 + s$ and cancel to get $a \cdot s = 0$ , whence $s = 0$ because a product of positive numbers is positive. It is not a group either.

So regularity is strictly weaker than being a group, and it is the condition we need of a monoid we want to enlarge into a group. That is what the next chapter does to $(\mathbb{N}_0, +)$ .

Problem 9.7.

Construct a semigroup with a left identity in which every element has a right inverse, but which is not a group. Two elements suffice.

Problem 9.8.

Let $(G, *)$ be a finite group and write out its multiplication table, the entry in row $x$ and column $y$ being $x * y$ . Show that every element of $G$ occurs exactly once in each row and exactly once in each column.

Problem 9.9.

Show that $(\mathbb{N}_0, \cdot)$ is not regular, and that $\mathcal{P}(X)$ under $\cup$ is not regular once $X$ is non-empty.

Problem 9.10.

The symmetric difference $A \oplus B \defeq (A \setminus B) \cup (B \setminus A)$ , the set of objects lying in exactly one of $A$ and $B$ , was met in the exercises of the chapter on sets. Show that $\bigl(\mathcal{P}(X), \oplus\bigr)$ is an abelian group, and identify its identity and the inverse of each element.

Subgroups

Definition 9.25 (Subgroup).

Let $(G, *)$ be a group with identity $e$ and let $H \subset G$ be non-empty. Then $H$ is a subgroup of $G$ if $e \in H$ , if $a * b \in H$ for all $a, b \in H$ , and if $a^{-1} \in H$ for all $a \in H$ . A subgroup other than $\{e\}$ and $G$ is called proper.

The three conditions say precisely that $(H, *)$ is itself a group under the restricted operation, and nothing extra is assumed. Suppose $H$ is a closed subset that happens to be a group in its own right, with identity $f \in H$ . Then $f * f = f$ holds in $G$ , and cancelling $f$ there gives $f = e$ : a subset cannot have an identity of its own. Likewise the inverse of $a \in H$ computed inside $H$ is an inverse of $a$ inside $G$ , so uniqueness of inverses makes it $a^{-1}$ . The conditions listed are therefore necessary as well as sufficient, and they may be checked by computing in $G$ .

Proposition 9.26 (One-step subgroup criterion).

Let $(G, *)$ be a group and let $H \subset G$ be non-empty. Then $H$ is a subgroup of $G$ if and only if $a * b^{-1} \in H$ for all $a, b \in H$ .

Discussion.

A biconditional between the three conditions of the definition and a single one, and one direction is much easier than the other. Forwards is immediate: a subgroup contains $b^{-1}$ and is closed, so it contains $a * b^{-1}$ . Backwards, we get the three conditions from the one by choosing $a$ and $b$ suitably. Non-emptiness supplies some $a \in H$ to start from; taking $b = a$ produces $e$ ; taking $a = e$ then produces $b^{-1}$ for every $b \in H$ ; and once inverses are available, the product $a * b$ is $a * (b^{-1})^{-1}$ , which the hypothesis covers. Each step uses the hypothesis once, and the steps must come in this order.

Proof.

Suppose $H$ is a subgroup and let $a, b \in H$ . Then $b^{-1} \in H$ , so $a * b^{-1} \in H$ .

Conversely suppose $a * b^{-1} \in H$ whenever $a, b \in H$ . Since $H$ is non-empty, choose $a \in H$ ; taking $b = a$ gives $e = a * a^{-1} \in H$ . Now let $b \in H$ ; taking the pair $(e, b)$ gives $b^{-1} = e * b^{-1} \in H$ , so $H$ is closed under inverses. Finally let $a, b \in H$ ; then $b^{-1} \in H$ , so taking the pair $(a, b^{-1})$ gives $a * (b^{-1})^{-1} = a * b \in H$ . Hence $H$ satisfies the three conditions.

Example 9.27 (Subgroups already met).

$D_n$ is a subgroup of $S_n$ , and for $n \geqslant 2$ the alternating group $A_n$ is a subgroup of $S_n$ . Inside $S_A$ , the permutations fixing a chosen point $a \in A$ form a subgroup: the identity fixes $a$ , a composite of two maps fixing $a$ fixes $a$ , and if $\sigma(a) = a$ then $\sigma^{-1}(a) = a$ . Every group has the two subgroups $\{e\}$ and $G$ .

For each $\ell \in \mathbb{N}$ the multiples of $\ell$ form a subgroup of the integers under addition, an example we can state properly once the integers are built.

Problem 9.11.

Show that a non-empty finite subset $H$ of a group $G$ that is closed under the operation is already a subgroup. For fixed $a \in H$ the map $x \mapsto a * x$ sends $H$ into $H$ ; use finiteness to make it surjective, and read off $e \in H$ and $a^{-1} \in H$ .

Problem 9.12.

Show that an intersection of subgroups of $G$ is a subgroup of $G$ , for any non-empty indexed family of them. Show by example that a union of two subgroups need not be one.

Problem 9.13.

List every subgroup of $S_3$ , and check each against the one-step criterion.

Homomorphisms and Quotients

A subgroup cuts a group into pieces of equal size, and sometimes the pieces form a group themselves. The last notion of this chapter is a map that respects the operation.

Cosets

Definition 9.28 (Cosets).

Let $H$ be a subgroup of a group $(G, *)$ and let $b \in G$ . The right coset and the left coset of $H$ by $b$ are

H * b \defeq \{h * b \mid h \in H\}, \qquad b * H \defeq \{b * h \mid h \in H\}.

Proposition 9.29 (The right cosets partition the group).

Let $H$ be a subgroup of a group $(G, *)$ and define $a_1 \sim a_2$ to mean $a_1 * a_2^{-1} \in H$ . Then $\sim$ is an equivalence relation on $G$ whose classes are exactly the right cosets of $H$ . Moreover $\#(H * b) = \#H$ for every $b$ , when $H$ is finite.

Discussion.

Three assertions. The first asks for the three defining properties of an equivalence relation, and each comes from one of the three subgroup conditions: reflexivity is $e \in H$ , symmetry is closure under inverses applied to $a_1 * a_2^{-1}$ , and transitivity is closure under the operation applied to a product that telescopes. The second is an equality of sets, so it is two inclusions, and both come from writing an element of one side in the form the other side demands. The third is a counting claim, and since cardinality classifies finite sets it is enough to produce a bijection $H \to H * b$ ; the map $h \mapsto h * b$ is one, being surjective by the definition of the coset and injective by cancellation.

Proof.

For reflexivity, $a * a^{-1} = e \in H$ , so $a \sim a$ . For symmetry, if $a_1 * a_2^{-1} \in H$ then its inverse $(a_1 * a_2^{-1})^{-1} = a_2 * a_1^{-1}$ lies in $H$ , so $a_2 \sim a_1$ . For transitivity, if $a_1 * a_2^{-1} \in H$ and $a_2 * a_3^{-1} \in H$ then their product

(a_1 * a_2^{-1}) * (a_2 * a_3^{-1}) = a_1 * a_3^{-1}

lies in $H$ , so $a_1 \sim a_3$ .

For the classes, fix $b$ . If $a \sim b$ then $h \defeq a * b^{-1} \in H$ and $a = h * b \in H * b$ . Conversely if $a = h * b$ with $h \in H$ then $a * b^{-1} = h \in H$ , so $a \sim b$ . Hence $[b] = H * b$ .

For the count, the map $h \mapsto h * b$ from $H$ to $H * b$ is surjective by the definition of $H * b$ and injective by cancellation, hence a bijection, so the two sets have the same cardinality.

Since the classes of an equivalence relation partition the set, the right cosets partition $G$ into pieces all of the same size as $H$ . The left cosets do the same, by the mirror argument with $a_1^{-1} * a_2 \in H$ .

Problem 9.14.

Let $G$ be a finite group and $H$ a subgroup. Show that $\#G$ is the product of $\#H$ with the number of right cosets of $H$ . Deduce that $\#H$ divides $\#G$ .

Problem 9.15.

Show that the left cosets of $H$ partition $G$ as the right cosets do, and that the two partitions have the same number of pieces, by checking that $H * b \mapsto b^{-1} * H$ is a well-defined bijection between them.

Homomorphisms

Definition 9.30 (Homomorphism).

Let $(G_1, *)$ and $(G_2, *)$ be groups. A function $\alpha : G_1 \to G_2$ is a homomorphism if

\alpha(a * b) = \alpha(a) * \alpha(b) \qquad \text{for all } a, b \in G_1.

Its kernel is $\ker \alpha \defeq \alpha^{-1}(\{e_2\})$ , the preimage of the identity of $G_2$ , and its image is $\alpha(G_1)$ . A bijective homomorphism is an isomorphism; groups with an isomorphism between them are isomorphic, written $G_1 \cong G_2$ . An isomorphism from a group to itself is an automorphism. Throughout, $e_1$ and $e_2$ are the identities of $G_1$ and of $G_2$ .

The same symbol $*$ denotes two different operations, one on each side of the equation, and that is deliberate: the condition says that computing in $G_1$ and then transporting gives the same answer as transporting and then computing in $G_2$ .

Proposition 9.31 (Homomorphisms respect the identity and inverses).

Let $\alpha : G_1 \to G_2$ be a homomorphism. Then $\alpha(e_1) = e_2$ and $\alpha(a^{-1}) = \alpha(a)^{-1}$ for every $a \in G_1$ .

Discussion.

Neither conclusion is assumed by the definition, which mentions only products, so both must be derived from the product condition. For the first, $e_1$ is characterised inside $G_1$ by $e_1 * e_1 = e_1$ ; applying $\alpha$ turns that into an equation about $\alpha(e_1)$ alone, and cancellation in $G_2$ finishes it. For the second, apply $\alpha$ to the defining equation $a * a^{-1} = e_1$ and use the first part: the result says $\alpha(a^{-1})$ is an inverse of $\alpha(a)$ , and inverses are unique.

Proof.

From $e_1 * e_1 = e_1$ we get $\alpha(e_1) * \alpha(e_1) = \alpha(e_1) = \alpha(e_1) * e_2$ , and cancelling $\alpha(e_1)$ on the left gives $\alpha(e_1) = e_2$ .

Then $\alpha(a) * \alpha(a^{-1}) = \alpha(a * a^{-1}) = \alpha(e_1) = e_2$ , and likewise $\alpha(a^{-1}) * \alpha(a) = e_2$ . So $\alpha(a^{-1})$ is an inverse of $\alpha(a)$ , hence is $\alpha(a)^{-1}$ by uniqueness.

Proposition 9.32 (Kernel and image).

Let $\alpha : G_1 \to G_2$ be a homomorphism.

$\ker \alpha$ is a subgroup of $G_1$ and $\alpha(G_1)$ is a subgroup of $G_2$ .
$\alpha$ is injective if and only if $\ker \alpha = \{e_1\}$ .
If $\alpha$ is an isomorphism then so is $\alpha^{-1}$ .

Discussion.

Three separate claims. The first two subgroup checks are the one-step criterion, and each is a short computation using the previous proposition to convert $\alpha$ of an inverse into an inverse of $\alpha$ ; non-emptiness comes from $\alpha(e_1) = e_2$ in both cases. The second claim is a biconditional: forwards, an injective map sends at most one point to $e_2$ and $e_1$ is already one; backwards, the way to turn an equality $\alpha(a_1) = \alpha(a_2)$ into a statement about the kernel is to move everything to one side, forming $a_1 * a_2^{-1}$ , which the hypothesis then forces to be $e_1$ . The third is again a matter of transporting a condition: given $a_2, b_2 \in G_2$ , name their preimages, apply the homomorphism condition to those, and read the resulting equation backwards through $\alpha^{-1}$ ; that $\alpha^{-1}$ is bijective is the theorem that the inverse of a bijection is a bijection.

Proof.

For the first, $\alpha(e_1) = e_2$ puts $e_1 \in \ker \alpha$ and $e_2 \in \alpha(G_1)$ , so both are non-empty. If $a, b \in \ker \alpha$ then

\alpha(a * b^{-1}) = \alpha(a) * \alpha(b)^{-1} = e_2 * e_2^{-1} = e_2,

so $a * b^{-1} \in \ker\alpha$ and the one-step criterion applies. If $\alpha(a), \alpha(b) \in \alpha(G_1)$ then $\alpha(a) * \alpha(b)^{-1} = \alpha(a * b^{-1}) \in \alpha(G_1)$ , and the criterion applies again.

For the second, suppose $\alpha$ is injective and $a \in \ker\alpha$ . Then $\alpha(a) = e_2 = \alpha(e_1)$ , so $a = e_1$ . Conversely suppose $\ker\alpha = \{e_1\}$ and $\alpha(a_1) = \alpha(a_2)$ . Then

\alpha(a_1 * a_2^{-1}) = \alpha(a_1) * \alpha(a_2)^{-1} = e_2,

so $a_1 * a_2^{-1} = e_1$ and hence $a_1 = a_2$ .

For the third, let $\alpha$ be an isomorphism and let $a_2, b_2 \in G_2$ have preimages $a_1, b_1$ . Then $\alpha(a_1 * b_1) = a_2 * b_2$ , so $\alpha^{-1}(a_2 * b_2) = a_1 * b_1 = \alpha^{-1}(a_2) * \alpha^{-1}(b_2)$ . And $\alpha^{-1}$ is a bijection, so it is an isomorphism.

Example 9.33 (The sign is a homomorphism).

The sign of a permutation takes two values, and the group with two elements is $S_2 = \{\mathrm{id}, \tau_{1,2}\}$ . Define $\mathrm{sg} : S_n \to S_2$ by sending an even permutation to $\mathrm{id}$ and an odd one to $\tau_{1,2}$ . The theorem on the properties of the sign says the sign of a product is the product of the signs, which is exactly the statement that $\mathrm{sg}$ is a homomorphism: the four cases of “even or odd times even or odd” are the four products in $S_2$ .

Its kernel is the set of even permutations, which is $A_n$ . So the fact that the alternating group is a subgroup, checked by hand last chapter, now follows from the proposition on kernels. For $n \geqslant 2$ the map is surjective, since a transposition is odd, so its image is all of $S_2$ .

Theorem 9.34 (Cayley's theorem).

Every group is isomorphic to a subgroup of a symmetric group. Precisely: if $(G, *)$ is a group then $a \mapsto \lambda_a$ , where $\lambda_a(x) \defeq a * x$ , is an injective homomorphism $G \to S_G$ , so $G$ is isomorphic to a subgroup of $S_G$ .

Discussion.

There are three things to check. First, the proposed values must lie where the theorem says: $\lambda_a$ must be a permutation of $G$ , and it is, because $\lambda_{a^{-1}}$ undoes it on both sides, so it is invertible and hence a bijection. Second, the map must be a homomorphism, and since both sides are functions on $G$ the check is an equality of functions, settled by evaluating at an arbitrary $x$ ; associativity is the only thing used, and it is used once. Third, injectivity, which by the previous proposition is the triviality of the kernel: if $\lambda_a$ is the identity permutation then it fixes $e$ in particular, and $\lambda_a(e) = a$ . The isomorphism onto a subgroup is then the image, which the previous proposition already knows to be a subgroup.

Proof.

For each $a \in G$ the maps $\lambda_a$ and $\lambda_{a^{-1}}$ satisfy

\lambda_{a^{-1}}\bigl(\lambda_a(x)\bigr) = a^{-1} * (a * x) = x

and likewise in the other order, so $\lambda_a$ is invertible and hence a permutation of $G$ ; that is, $\lambda_a \in S_G$ .

Let $\Lambda : G \to S_G$ be $a \mapsto \lambda_a$ . For $a, b \in G$ and any $x \in G$ ,

\lambda_{a * b}(x) = (a * b) * x = a * (b * x) = \lambda_a\bigl(\lambda_b(x)\bigr) = (\lambda_a \lambda_b)(x),

so $\Lambda(a * b) = \Lambda(a)\Lambda(b)$ and $\Lambda$ is a homomorphism.

If $a \in \ker\Lambda$ then $\lambda_a = \mathrm{id}_G$ , so $a = a * e = \lambda_a(e) = e$ . Hence $\ker\Lambda = \{e\}$ and $\Lambda$ is injective. Its image is a subgroup of $S_G$ , and $\Lambda$ restricted to that image is a bijective homomorphism, hence an isomorphism.

Remark.

Cayley’s theorem says that every group is a group of permutations, so in that sense the last chapter already covered all groups. The statement is weak, though: $S_G$ has $\#G\,!$ elements when $G$ is finite, so the copy of $G$ inside it is a very small part of a very large group, and locating it is no easier than knowing $G$ already.

Problem 9.16.

Show that $\mathrm{sg} : S_n \to S_2$ of the example above is the only homomorphism $S_n \to S_2$ that is not constant, for $n \geqslant 2$ . Every transposition must go to the same place; say why.

Problem 9.17.

Show that a homomorphism carries a subgroup of $G_1$ to a subgroup of $G_2$ , and that the preimage of a subgroup of $G_2$ is a subgroup of $G_1$ .

Problem 9.18.

Show that $D_3$ and $S_3$ are isomorphic, and that $D_4$ and $S_4$ are not.

Normal Subgroups and Quotients

Kernels satisfy a condition that not every subgroup does, and it is exactly the condition needed to make the cosets into a group.

Definition 9.35 (Normal subgroup).

A subgroup $H$ of a group $(G, *)$ is normal if $b^{-1} * a * b \in H$ for all $a \in H$ and $b \in G$ .

In an abelian group $b^{-1} * a * b = a$ , so every subgroup is normal, and the condition only matters in the non-commutative case.

Proposition 9.36 (Kernels are normal).

The kernel of a homomorphism $\alpha : G_1 \to G_2$ is a normal subgroup of $G_1$ .

Discussion.

That the kernel is a subgroup is already proved, so only the normality condition is left, and it is a membership claim: we must show $\alpha$ sends $b^{-1} * a * b$ to $e_2$ . Applying the homomorphism condition twice turns that element into a product of three values of $\alpha$ , the middle one being $e_2$ because $a$ lies in the kernel; the outer two are inverse to each other by the proposition on how homomorphisms treat inverses, so the product is $e_2$ .

Proof.

Let $a \in \ker\alpha$ and $b \in G_1$ . Then

\begin{aligned} \alpha(b^{-1} * a * b) &= \alpha(b)^{-1} * \alpha(a) * \alpha(b) \\ &= \alpha(b)^{-1} * e_2 * \alpha(b) = \alpha(b)^{-1} * \alpha(b) = e_2, \end{aligned}

so $b^{-1} * a * b \in \ker\alpha$ . With the subgroup property already established, $\ker\alpha$ is normal.

Theorem 9.37 (Normal subgroups are those whose cosets agree).

Let $H$ be a subgroup of a group $(G, *)$ . Then $H$ is normal if and only if $H * b = b * H$ for every $b \in G$ .

Discussion.

A biconditional, and each direction converts one membership statement into another by moving a factor across. Forwards: an element of $H * b$ is $h * b$ , and to exhibit it in $b * H$ we must write it as $b$ times something in $H$ ; inserting $b * b^{-1}$ gives $b * (b^{-1} * h * b)$ , and normality is precisely the statement that the bracketed factor lies in $H$ . The reverse inclusion is the same move with $b^{-1}$ in place of $b$ , which normality also covers. Backwards: given the equality of the two cosets, an element $b^{-1} * a * b$ with $a \in H$ is a member of $b^{-1} * (H * b)$ , which the hypothesis rewrites as $b^{-1} * (b * H) = H$ .

Proof.

Suppose $H$ is normal and let $b \in G$ . If $h \in H$ then $h * b = b * (b^{-1} * h * b)$ and $b^{-1} * h * b \in H$ , so $H * b \subset b * H$ . If $h \in H$ then $b * h = \bigl(b * h * b^{-1}\bigr) * b$ , and $b * h * b^{-1} = (b^{-1})^{-1} * h * b^{-1} \in H$ by normality applied with $b^{-1}$ , so $b * H \subset H * b$ . Hence the two cosets are equal.

Conversely suppose $H * b = b * H$ for every $b$ , and let $a \in H$ and $b \in G$ . Then $a * b \in H * b = b * H$ , so $a * b = b * h$ for some $h \in H$ , and $b^{-1} * a * b = h \in H$ . So $H$ is normal.

When $H$ is normal the two partitions of $G$ coincide and there is just one collection of cosets, which we write $G/H$ — the quotient of $G$ by the equivalence relation of the coset proposition.

Theorem 9.38 (The quotient group).

Let $H$ be a normal subgroup of a group $(G, *)$ . Then

(H * a) * (H * b) \defeq H * (a * b)

is a well-defined operation on $G/H$ , making $G/H$ a group with identity $H = H * e$ and with $(H * a)^{-1} = H * a^{-1}$ . The map $q : G \to G/H$ sending $a$ to $H * a$ is a surjective homomorphism with $\ker q = H$ .

Discussion.

The main difficulty is showing that the operation is well defined. The proposed rule names the answer using $a$ and $b$ , but the arguments of the operation are the cosets, and a coset has many names; so we must show that replacing $a$ by any $a'$ with $H * a' = H * a$ , and $b$ likewise, leaves $H * (a * b)$ unchanged. Written in terms of the equivalence relation, that means $a' * a^{-1} \in H$ and $b' * b^{-1} \in H$ should force $(a' * b') * (a * b)^{-1} \in H$ , and this calculation uses normality: the two known members of $H$ are separated by $a$ , and normality lets us move it past.

The rest follows from the laws in $G$ . Associativity, the identity law and the inverse law each reduce, through the definition of the operation, to the corresponding law in $G$ applied to representatives. That $q$ is a homomorphism is the definition of the operation read backwards, surjectivity is the definition of $G/H$ , and the kernel is the set of $a$ with $H * a = H$ , which is $H$ .

Proof.

For well-definedness, suppose $H * a' = H * a$ and $H * b' = H * b$ , so that $h \defeq a' * a^{-1}$ and $k \defeq b' * b^{-1}$ lie in $H$ . Then $a' = h * a$ and $b' = k * b$ , so

(a' * b') * (a * b)^{-1} = h * a * k * b * b^{-1} * a^{-1} = h * (a * k * a^{-1}),

and $a * k * a^{-1} = (a^{-1})^{-1} * k * a^{-1} \in H$ by normality. So the displayed element is a product of two members of $H$ and lies in $H$ , giving $H * (a' * b') = H * (a * b)$ . The operation is therefore well defined.

Associativity follows from associativity in $G$ :

\begin{aligned} \bigl((H * a) * (H * b)\bigr) * (H * c) &= H * \bigl((a * b) * c\bigr) \\ &= H * \bigl(a * (b * c)\bigr) \\ &= (H * a) * \bigl((H * b) * (H * c)\bigr). \end{aligned}

Also $(H * e) * (H * a) = H * a = (H * a) * (H * e)$ , so $H * e = H$ is an identity, and $(H * a) * (H * a^{-1}) = H * e = (H * a^{-1}) * (H * a)$ , so $H * a^{-1}$ is an inverse of $H * a$ . Hence $G/H$ is a group.

Finally $q(a * b) = H * (a * b) = (H * a) * (H * b) = q(a) * q(b)$ , so $q$ is a homomorphism; it is surjective because every coset is $H * a$ for some $a$ ; and $q(a) = H$ holds exactly when $a * e^{-1} = a \in H$ , so $\ker q = H$ .

Remark.

So normal subgroups and kernels are the same thing: every kernel is normal, by the proposition, and every normal subgroup is the kernel of the map $q$ onto its own quotient. So the question “which subgroups can be quotiented by?” and the question “which subgroups arise as kernels?” have one answer.

Theorem 9.39 (First isomorphism theorem).

Let $\alpha : G_1 \to G_2$ be a homomorphism. Then

G_1/\ker\alpha \;\cong\; \alpha(G_1),

by the isomorphism sending the coset $\ker\alpha * a$ to $\alpha(a)$ .

Discussion.

The statement claims an isomorphism between two groups both of which are already known to exist: the quotient by the previous theorem, since the kernel is normal, and the image by the proposition on kernels and images. So we only need to check four things about the named map. That it is well defined is the same issue as before, since a coset has many names, and it holds because two representatives differ by a member of the kernel, which $\alpha$ sends to the identity. That it is a homomorphism is the definition of the quotient operation together with the homomorphism property of $\alpha$ . Surjectivity onto the image is immediate. Injectivity is the triviality of the kernel of the new map, and it comes out as the statement that $\alpha(a) = e_2$ puts $a$ in $\ker\alpha$ , so the coset is the identity of the quotient.

Proof.

Write $K \defeq \ker\alpha$ , a normal subgroup by the proposition, so that $G_1/K$ is a group. Define $\beta(K * a) \defeq \alpha(a)$ .

Well defined. If $K * a' = K * a$ then $a' * a^{-1} \in K$ , so $\alpha(a') * \alpha(a)^{-1} = \alpha(a' * a^{-1}) = e_2$ and hence $\alpha(a') = \alpha(a)$ .

Homomorphism. $\beta\bigl((K * a) * (K * b)\bigr) = \beta\bigl(K * (a * b)\bigr) = \alpha(a * b) = \alpha(a) * \alpha(b) = \beta(K * a) * \beta(K * b)$ .

Surjective onto $\alpha(G_1)$ . Every element of the image is $\alpha(a) = \beta(K * a)$ for some $a$ .

Injective. If $\beta(K * a) = e_2$ then $\alpha(a) = e_2$ , so $a \in K$ and $K * a = K$ , the identity of $G_1/K$ . So the kernel of $\beta$ is trivial and $\beta$ is injective.

Hence $\beta$ is a bijective homomorphism from $G_1/K$ onto $\alpha(G_1)$ .

Example 9.40 (The sign again).

Take $\alpha = \mathrm{sg} : S_n \to S_2$ with $n \geqslant 2$ . Its kernel is $A_n$ and its image is all of $S_2$ , so the theorem gives

S_n/A_n \;\cong\; S_2 .

The quotient has two elements, the even permutations and the odd ones, and its multiplication is the arithmetic of parity: even times even is even, even times odd is odd, odd times odd is even. Counting the cosets recovers the problem that $\#S_n$ is twice the number of even permutations, this time as a consequence rather than a construction.

Problem 9.19.

Show that a subgroup $H \subset G$ with exactly two right cosets is normal, without computing anything about $H$ itself.

Problem 9.20.

Show that $\{\mathrm{id}, \tau_{1,2}\}$ is a subgroup of $S_3$ that is not normal, and that $A_3$ is a normal subgroup of $S_3$ . Which of the two has a quotient group, and what is it?

Problem 9.21.

Let $\alpha : G_1 \to G_2$ be a homomorphism and let $H$ be a normal subgroup of $G_1$ contained in $\ker\alpha$ . Show that there is exactly one homomorphism $\gamma : G_1/H \to G_2$ with $\alpha = \gamma \circ q$ , where $q : G_1 \to G_1/H$ is the quotient map. The first isomorphism theorem is the case $H = \ker\alpha$ .

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

Every statement of this chapter is made of one group, so the checker is given one and the sheet works inside it. The objects are its elements, and three new pieces of notation carry the structure:

a ∗ b    the product, typed \ast
e        the identity
a⁻¹      the inverse of a, typed \-1

The operation binds like a product, so a ∗ b ∗ c is (a ∗ b) ∗ c and brackets are written where the other reading is wanted. A subgroup is a set, hence an object like any other, and a ∈ H is the membership of the sets chapter.

Five entries carry Definition 9.19 and nothing else is given away:

mul_assoc        (a ∗ b) ∗ c = a ∗ (b ∗ c)
e_mul            e ∗ a = a
mul_e            a ∗ e = a
inv_mul_cancel   a⁻¹ ∗ a = e
mul_inv_cancel   a ∗ a⁻¹ = e

Everything else in the chapter is a consequence, and the sheet asks for the consequences.

Multiplying an equation through

The axioms are equations, so the work is rewriting. What the paper proofs do in one line (multiply both sides by $a^{-1}$ ) the checker needs spelled out, and congrArg says it: from h : x = y it builds f x = f y for any f written out as fun t => …. Once the equation has the factor on it, rw [...] at h cancels.

Example.

The observation that settled the identity of a subgroup, in the discussion after Definition 9.25 . Multiplying by $a^{-1}$ on the left is the whole of it.

Example.

The left half of Proposition 9.22 . It is listed below as mul_left_cancel, so the exercises may lean on it.

Example.

Inverting twice returns the element, noted after Proposition 9.15 . It is listed below as inv_inv.

lean worked

1example (a : Obj) : (a⁻¹)⁻¹ = a := by

2  have h : a⁻¹ ∗ (a⁻¹)⁻¹ = e := mul_inv_cancel a⁻¹3  have h2 : a ∗ (a⁻¹ ∗ (a⁻¹)⁻¹) = a ∗ e := congrArg (fun t => a ∗ t) h4  rw [← mul_assoc, mul_inv_cancel, e_mul, mul_e] at h25  exact h2

verified

goalGoals accomplished.

Exercise 9.12.

The identity is its own inverse.

Exercise 9.13.

Proposition 9.12 , with only the left-hand law assumed.

Exercise 9.14.

The right half of Proposition 9.22 .

Exercise 9.15.

Proposition 9.15 , in the form Problem 9.6 puts it.

Exercise 9.16.

The equation $a * x = b$ has no second solution, as the remark after Proposition 9.22 observes.

Exercise 9.17.

Proposition 9.16 . Show first that $b^{-1} * a^{-1}$ multiplies with $a * b$ to give $e$ .

Exercise 9.18.

The rearrangement that carries a right coset onto a left one in Theorem 9.37 .

Exercise 9.19.

The first step of the backward direction of Proposition 9.26 .

Exercise 9.20.

Its second step.

Exercise 9.21.

And its third, which is where inv_inv earns its place.

Exercise 9.22.

The first half of Proposition 9.31 . A homomorphism is a map with the one property, so it arrives as an arrow together with the equation it satisfies.

Exercise 9.23.

Its second half, with the first half to hand.

Exercise 9.24.

The kernel is closed under the operation, part of Proposition 9.32 . The kernel arrives as a set together with its membership criterion.

Exercise 9.25.

Proposition 9.36 : the kernel is normal. (Harder.)

lean proof

1example (f : Obj → Obj) (K : Obj) (hf : ∀ a b : Obj, f (a ∗ b) = f a ∗ f b) (hfe : f e = e)2    (hinv : ∀ a : Obj, f a⁻¹ = (f a)⁻¹) (hK : ∀ x : Obj, x ∈ K ↔ f x = e)3    (a b : Obj) (ha : a ∈ K) : b⁻¹ ∗ a ∗ b ∈ K := by

4  sorry

goalf : Obj → Obj K : Obj hf : ∀ (a : Obj), ∀ (b : Obj), f (a ∗ b) = f a ∗ f b hfe : f e = e hinv : ∀ (a : Obj), f a⁻¹ = (f a)⁻¹ hK : ∀ (x : Obj), x ∈ K ↔ f x = e a b : Obj ha : a ∈ K ⊢ (b⁻¹ ∗ a) ∗ b ∈ K

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic
induction n with k ih	the fifth Peano condition: prove the goal at 0, then at succ k from ih

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are
Nat.succ_inj	∀ {m n : ℕ}, succ m = succ n → m = n — the third Peano condition: the successor is injective
Nat.succ_ne_zero	∀ (n : ℕ), succ n ≠ 0 — the fourth: zero is nobody's successor
Nat.pred	∀ {n : ℕ}, n ≠ 0 → ∃ m : ℕ, n = succ m — predecessors: everything but zero is a successor
Nat.add_zero	∀ (m : ℕ), m + 0 = m — the first clause of addition
Nat.add_succ	∀ (m n : ℕ), m + succ n = succ (m + n) — the second clause of addition
Nat.zero_add	∀ (n : ℕ), 0 + n = n — addition from the left
Nat.succ_add	∀ (m n : ℕ), succ m + n = succ (m + n) — addition from the left, at a successor
Nat.add_assoc	∀ (m n p : ℕ), (m + n) + p = m + (n + p) — addition is associative
Nat.add_comm	∀ (m n : ℕ), m + n = n + m — addition is commutative
Nat.add_ne_zero	∀ {a : ℕ} (b : ℕ), a ≠ 0 → a + b ≠ 0 — positivity is absorbing
Nat.mul_zero	∀ (m : ℕ), m * 0 = 0 — the first clause of multiplication
Nat.mul_succ	∀ (m n : ℕ), m * succ n = m * n + m — the second clause of multiplication
Nat.zero_mul	∀ (m : ℕ), 0 * m = 0 — multiplication from the left
Nat.succ_mul	∀ (m n : ℕ), succ m * n = m * n + n — multiplication from the left, at a successor
Nat.add_right_cancel	∀ {m n k : ℕ}, m + k = n + k → m = n — cancellation, from the last sheet
Nat.add_eq_zero	∀ {m n : ℕ}, m + n = 0 → m = 0 ∧ n = 0 — a sum is zero only when both parts are, from the last sheet
Nat.mul_comm	∀ (m n : ℕ), m * n = n * m — multiplication is commutative, from the last sheet
Nat.mul_add	∀ (m n p : ℕ), m * (n + p) = m * n + m * p — multiplication distributes over addition, from the last sheet
Nat.mul_assoc	∀ (m n p : ℕ), (m * n) * p = m * (n * p) — multiplication associates, from the problems of the last chapter
Nat.add_mul	∀ (m n p : ℕ), (m + n) * p = m * p + n * p — distributivity on the other side
Nat.add_left_cancel	∀ {a m n : ℕ}, a + m = a + n → m = n — uniqueness of differences
Nat.lt_trichotomy	∀ (m n : ℕ), m < n ∨ m = n ∨ n < m — trichotomy, from the theorem that ℕ is strictly ordered
Nat.lt_irrefl	∀ (n : ℕ), ¬(n < n) — anti-reflexivity, from the last sheet
Nat.lt_trans	∀ {m n p : ℕ}, m < n → n < p → m < p — transitivity of the strict order, from the last sheet
Nat.lt_succ_self	∀ (n : ℕ), n < succ n — every number is below its successor, from the last sheet
Nat.not_lt_zero	∀ {n : ℕ}, ¬(n < 0) — nothing lies below zero
Nat.lt_succ_iff	∀ {m n : ℕ}, m < succ n ↔ m < n ∨ m = n — nothing lies strictly between n and succ n
Num.inj	∀ {m n : ℕ}, ↑m = ↑n → m = n — distinct numbers name distinct objects of ω
swap_apply_left	∀ (a b : Obj), swap a b a = b — the transposition sends a to b
swap_apply_right	∀ (a b : Obj), swap a b b = a — and b to a
swap_apply_of_ne_of_ne	∀ {a b x : Obj}, x ≠ a → x ≠ b → swap a b x = x — and fixes every other point
swap_swap	∀ (a b x : Obj), swap a b (swap a b x) = x — a transposition is its own inverse
Function.iterate_zero_apply	∀ (f : Obj → Obj) (x : Obj), f^[0] x = x — the first clause of the powers of a map
Function.iterate_succ_apply	∀ (f : Obj → Obj) (n : ℕ) (x : Obj), f^[succ n] x = f^[n] (f x) — the second clause: f^[succ n] is f^[n] ∘ f
Function.iterate_add_apply	∀ (f : Obj → Obj) (m n : ℕ) (x : Obj), f^[m + n] x = f^[m] (f^[n] x) — the first law of exponents
Nat.factorial_zero	0 ! = succ 0 — the first clause of the factorial
Nat.factorial_succ	∀ (n : ℕ), (succ n) ! = succ n * n ! — the second clause of the factorial
Nat.choose_zero_right	∀ (n : ℕ), choose n 0 = succ 0 — the empty set is the one 0-subset
Nat.choose_eq_zero_of_lt	∀ {n k : ℕ}, n < k → choose n k = 0 — no subset is larger than the whole
Nat.choose_succ_succ	∀ (n k : ℕ), choose (succ n) (succ k) = choose n k + choose n (succ k) — Pascal's identity
mul_assoc	∀ (a b c : Obj), (a ∗ b) ∗ c = a ∗ (b ∗ c) — the operation associates
e_mul	∀ (a : Obj), e ∗ a = a — the identity on the left
mul_e	∀ (a : Obj), a ∗ e = a — and on the right
inv_mul_cancel	∀ (a : Obj), a⁻¹ ∗ a = e — the inverse on the left
mul_inv_cancel	∀ (a : Obj), a ∗ a⁻¹ = e — and on the right
inv_inv	∀ (a : Obj), (a⁻¹)⁻¹ = a — worked above: inverting twice gives the element back
mul_left_cancel	∀ {a x y : Obj}, a ∗ x = a ∗ y → x = y — worked above: the left half of prop-9-5

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b