Proof of Lemma 1.2.11

We need to show \(\sigma_1(\sigma_2(l)) = \sigma_2(\sigma_1(l))\) for all \(l \in [n]\). If \(l \notin \{i_1, \ldots, i_m, j_1, \dots, j_k\}\), Then \(\sigma_1(l) = l = \sigma_2(l)\), so

If \(l \in \{j_1, \dots, j_k\}\), then \(\sigma_2(l) \in \{j_1, \dots, j_k\}\) and hence, since the subsets are disjoint, \(l\) and \(\sigma_2(l)\) are not in the set \(\{i_1 , i_2 , \dots i_m\}\). It follows that \(\sigma_1\) preserves \(l\) and \(\sigma_2(l)\), and thus

The case when \(l \in \{i_1, \dots, i_m\}\) is analogous.

Proof of Theorem 1.2.12

Fix a permutation \(\sigma\). The key idea is to look at the orbits of \(\sigma\): for each \(x \in [n]\), its orbit by \(\sigma\) is the subset of \([n]\) of the form

Notice that the orbits of two elements \(x\) and \(y\) are either the same orbit, which happens precisely when \(y \in O_x\), or disjoint. Since \([n]\) is a finite set, and \(\sigma\) is a bijection of \(\sigma\), we will eventually have \(\sigma^i(x) = \sigma^j(x)\) for some \(j > i\), but then

Thus we can find the smallest positive integer \(n_x\) such that \(\sigma^{n_x}(x)=x\). Now for each \(x \in [n]\), we consider the cycle

Now let \(S\) be a set of indices for the distinct \(\tau_x\), where note that we are not including the \(\tau_x\) that are \(1\)-cycles. We claim that we can factor \(\sigma\) as

To show this, consider any \(x \in [n]\). It must be of the form \(\sigma^j(i)\) for some \(i \in S\), given that our choice of \(S\) was exhaustive. On the right hand side, only \(\tau_i\) moves \(x\), and indeed by definition of \(\tau_i\) we have

This proves that

As for uniqueness, note that if \(\sigma = \tau_1 \cdots \tau_s\) is a product of disjoint cycles, then each \(x \in [n]\) is moved by at most one of the cycles \(\tau_i\), since the cycles are all disjoint. Fix \(i\) such that \(\tau_i\) moves \(x\). We claim that

This will show that our product of disjoint cycles giving \(\sigma\) is the same (unique) product we constructed above. To do this, note that we do know that there is some integer \(s\) such that \(\tau_x^s(x) = e\), and

Thus we need only to prove that

for all integers \(k \geqslant 1\). Now by the Theorem, disjoint cycles commute, and thus for each integer \(k \geqslant 1\) we have

But \(\tau_j\) fixes \(x\) whenever \(j \neq i\), so

We conclude that the integer \(n_x\) we defined before is the length of the cycle \(\tau_i\), and that

Thus this decomposition of \(\sigma\) as a product of disjoint cycles is the same decomposition we described above.

Proof of Corollary 1.2.18

Given any permutation, we can decompose it as a product of cycles by the Theorem. Thus it suffices to show that each cycle can be written as a product of permutations. For a cycle \((i_1 \, i_2 \, \cdots \, i_p)\), one can show that

which we leave as an exercise.

Proof of Theorem 1.2.22

Suppose that \(\sigma\) is a permutation that can be written as a production of transpositions \(\beta_i\) and \(\lambda_j\) in two ways,

where \(s\) is even and \(t\) is odd. As we noted in Exercise 1.2.21, every transposition is its own inverse, so we conclude that

which is a product of \(s+t\) transpositions. This is an odd number, so it suffices to show that it is not possible to write the identity as a product of an odd number of transpositions.

Suppose the identity can be written as the product \((a_1 b_1) \cdots (a_k b_k)\), where each \(a_i \neq b_i\). A single transposition {cannot} be the identity, and thus \(k \neq 1\). So assume, for the sake of an argument by induction, that for a fixed \(k\), we know that every product of fewer than \(k\) transpositions that equals the identity must use an even number of transpositions. Since \(2\) is even, we might as well assume \(k \geqslant 3\). Now note that since \(k > 1\), and our product is the identity, then some transposition \((a_i b_i)\) with \(i > 1\) must move \(a_1\); otherwise, \(b_1\) would be sent to \(a_1\), and our product would not be the identity.

Of all the possible ways we can write the identity as a product of \(k\) many transpositions \((a_1 b_1) \cdots (a_k b_k)\) with \(a_1 = a\) and \(b_1 = b\) fixed, choose one where the number \(N\) of times that \(a_1\) appears in one of the transpositions is smallest. The two rules in Exercise 1.2.21 allow us to rewrite the overall product without changing the number of transpositions in such a way that the transposition \((a_2 b_2)\) moves \(a_1\), meaning \(a_2 = a_1\) or \(b_2=a_1\). So let us assume that our product of transpositions has already been put in this form. Note also that \((a_i b_i) = (b_i a_i)\), so we might as well assume without loss of generality that \(a_2 = a_1\).

Case 1: When \(b_1 = b_2\), our product is

but \((a_1 b_1) (a_1 b_1)\) is the identity, so we can rewrite our product using only \(k-2\) transpositions. By induction hypothesis, \(k-2\) is even, and thus \(k\) is even.

Case 2: When \(b_1 \neq b_2\), we can use Exercise 1.2.21 to write

Notice here that it matters that \(a_1\), \(b_1\), and \(b_2\) are all distinct, so that we can apply Exercise 1.2.21. So our product, which equals the identity, is

The advantage of this shuffling is that while we have only changed the first two transpositions, we have decreased the number \(N\) of transpositions that move \(a_1\). But this contradicts our choice of \(N\) to be smallest possible.

Proof of Theorem 1.3.12

First, we show that \(D_n\) has order at most \(2n\). Any element \(\sigma \in D_n\) takes the polygon \(P_n\) to itself, and must in particular send vertices to vertices and preserve adjacencies, meaning that any two adjacent vertices remain adjacent after applying \(\sigma\). Fix two adjacent vertices \(A\) and \(B\). By Lemma 1.3.5, the location of every other point \(P\) on the polygon after applying \(\sigma\) is completely determined by the locations of \(\sigma(A)\) and \(\sigma(B)\). There are \(n\) distinct possibilities for \(\sigma(A)\), since it must be one of the \(n\) vertices of the polygon. But once \(\sigma(A)\) is fixed, \(\sigma(B)\) must be a vertex adjacent to \(\sigma(B)\), so there are at most \(2\) possibilities for \(\sigma(B)\). This gives us at most \(2n\) elements in \(D_n\).

Now we need only to present \(2n\) distinct elements in \(D_n\). We have described \(n\) reflections and \(n\) rotations for \(D_n\); we need only to see that they are all distinct. First, note that the only rotation that fixes any vertices of \(P_n\) is the identity. Moreover, if we label the vertices of \(P_n\) in order with \(1, 2, \ldots, n\), say by starting in a fixed vertex and going counterclockwise through each adjacent vertex, then the rotation by an angle of \(\frac{2 \pi i}{n}\) sends \(V_{1}\) to \(V_{i+1}\) for each \(i \lt n \), showing these \(n\) rotations are distinct. Now when \(n\) is odd, each of the \(n\) reflections fixes exactly one vertex, and so they are all distinct and disjoint from the rotations. Finally, when \(n\) is even, we have two kinds of reflections to consider. The reflections through a line connecting opposite vertices have exactly two fixed vertices, and are completely determined by which two vertices are fixed; since rotations have no fixed points, none of these matches any of the rotations we have already considered. The other reflections, the ones through the midpoint of two opposite sides, are completely determined by (one of) the two pairs of adjacent vertices that they switch. No rotation switches two adjacent vertices, and thus these give us brand new elements of \(D_n\).

In both cases, we have a total of \(2n\) distinct elements of \(D_n\) given by the \(n\) rotations and the \(n\) reflections.

Proof of Lemma 1.3.16

First, we claim that \(rs\) is a reflection. To see this, observe that \(s(V_1) = V_1\), so

and

This shows that \(rs\) must be a reflection, since it reverses orientation. Reflections have order \(2\), so \(rsrs = (rs)^2 = \mathrm{id}\) and hence \(srs = r^{-1}.\)

Proof of Theorem 1.3.19

Let \(\alpha\) be an arbitrary symmetry of \(P_n\). Note \(\alpha\) must fix the origin, since it is the center of mass of \(P_n\), and it must send each vertex to a vertex because the vertices are the points on \(P_n\) at largest distance from the origin. Thus \(\alpha(V_1) = V_ j\) for some \(1 \leqslant j \leqslant n\) and therefore the element \(r^{-j}\alpha\) fixes \(V_1\) and the origin. The only elements that fix \(V_1\) are the identity and \(s\). Hence either \(r^{-j}\alpha = \mathrm{id}\) or \(r^{-j}\alpha = s\). We conclude that \(\alpha = r^j\) or \(\alpha = r^js\).

Notice that we have shown that \(D_n\) has exactly \(2n\) elements, and that there are \(2n\) distinct expressions of the form \(r^j\) or \(r^js\) for \(0 \leqslant j \leqslant n-1\). Thus each element of \(D_n\) can be written in this form in a unique way.

Proof of Theorem 1.3.22

Theorem 1.3.19 shows that \(\{r,s\}\) is a set of generators for \(D_n\). Moreover, we also know that the relations listed above \(r^n = 1, s^2 = 1, srs^{-1} = r^{-1}\) hold; the first two are easy to check, and the last one is Lemma 1.3.16. The only concern we need to deal with is that we may not have discovered all the relations of \(D_n\); or rather, we need to check that we have found enough relations so that any other valid relation follows as a consequence of the ones listed.

Let

Assume that \(D_n\) has more relations than \(X_{2n}\) does. Then \(D_n\) would be a group of cardinality strictly smaller than \(X_{2n}\), meaning that \(|D_n|<|X_{2n}|\). This will become more clear once we properly define presentations. We will show below that in fact \(|X_{2n}|\leqslant 2n=|D_n|\), thus obtaining a contradiction.

Now we show that \(X_{2n}\) has at most \(2n\) elements using just the information contained in the presentation. By definition, since \(r\) and \(s\) generated \(X_{2n}\) then every element \(x\in X_{2n}\) can be written as

for some \(j\) and (possibly negative) integers \(m_1, \dots, m_j, n_1, \dots, m_j\).Note that, \(m_1\) could be \(0\), so that expressions beginning with a power of \(s\) are included in this list. As a consequence of the last relation, we have

and its not hard to see that this implies

for all \(m\). Thus, we can slide an \(s\) past a power of \(r\), at the cost of changing the sign of the power. Doing this repeatedly gives that we can rewrite \(x\) as

By the first relation, \(r^n = 1\), from which it follows that \(r^a = r^b\) if \(a\) and \(b\) are congruent modulo \(n\). Thus we may assume \(0 \leqslant M \leqslant n-1.\) Likewise, we may assume \(0 \leqslant N \leqslant 1\). This gives a total of at most \(2n\) elements, and we conclude that \(X_{2n}\) must in fact be \(D_n.\)

Proof of Claim 1.4.2

By using the property \(f(xy)=f(x)f(y)\) as well as associativity of multiplication in \(\mathrm{GL}_2(\mathbb{C})\) (marked by \(*\)) we obtain

Since \(f\) is injective and \(f((xy)z)=f(x(yz))\), we deduce \((xy)z=x(yz)\).

Proof of Lemma 1.5.7

By definition, \[ f(e_G)f(e_G) = f(e_Ge_G) = f(e_G). \] Multiplying both sides by \(f(e_G)^{-1}\), we get \[ f(e_G) = e_H. \]

Now given any \(x \in G\), we have \[ f(x^{-1}) f(x) = f(x^{-1}x) = f(e) = e, \] and thus \(f(x^{-1}) = f(x)^{-1}\).

Proof of Lemma 1.5.12

First, note that \(e_G \in \ker f\) by Lemma 1.5.7. If \(f\) is injective, then \(e_G\) must be the only element that \(f\) sends to \(e_H\), and thus \(\ker(f) = \{ e_G \}\).

Now suppose \(\ker(f) = \{e_G\}\). If \(f(g) = f(h)\) for some \(g,h \in G\), then \[ f(h^{-1}g) = f(h^{-1})f(g) = f(h)^{-1}f(g) = e_H. \] But then \(h^{-1}g \in \ker(f)\), so we conclude that \(h^{-1}g = e_G\), and thus \(g = h\).

Proof of Lemma 1.5.14

(\(\Rightarrow\)) A function \(f: X \to Y\) between two sets is bijective if and only if it has an inverse, meaning that there is a function \(g: Y \to X\) such that \(f \circ g = \mathrm{id}_Y\) and \(g \circ f = \mathrm{id}_X\). Our definition of group isomorphism implies that this must hold for any isomorphism (and more!), as we noted in Remark 1.5.4.

(\(\Leftarrow\)) If \(f\) is bijective homomorphism, then as a function it has a set-theoretic two-sided inverse \(g\), as remarked in Remark 1.5.4. But we need to show that this inverse \(g\) is actually a homomorphism. For any \(x,y \in H\), we have

Since \(f\) is injective, we must have \(g(xy) = g(x)g(y)\). Thus \(g\) is a homomorphism, and \(f\) is an isomorphism.

Proof of Theorem 1.5.17

Let \(f\!:G\to H\) be any group isomorphism.

1. Since \(f\) is a bijection by Remark 1.5.4, we conclude that \(|G|=|H|\).
2. We wish to show that \(\{|x| \ | \ x\in G\}= \{|y| \ | \ y\in H\}\). (\(\subseteq\)) follows from Exercise 1.5.15: given any \(x\in G\), we have \(|x| = |f(x)|\), which is the order of an element in \(H\). (\(\supseteq\)) follows from the previous statement applied to the group isomorphism \(f^{-1}\): given any \(y\in H\), we have \(f^{-1}(y)\in G\) and \(|y| = |f^{-1}(y)|\) is the order of an element of \(G\).
3. For any \(y_1,y_2\in H\) there exist some \(x_1, x_2\in G\) such that \(f(x_i)=y_i\). Then we have \[ y_1y_2=f(x_1)f(x_2)=f(x_1x_2)\stackrel{*}{=}f(x_2x_1)=f(x_2)f(x_1)=y_2y_1, \] where \(*\) indicates the place where we used that \(G\) is abelian.
4. Exercise. The idea is to show \(f\) induces an isomorphism \(\mathcal{Z}(G)\cong \mathcal{Z}(H)\).
5. Exercise. Show that if \(S\) generates \(G\) then \(f(S)=\{f(s) \ | \ s\in S\}\) generates \(H\).

Proof of Lemma 2.1.3

(1) Assume we are given an action of \(G\) on \(S\). We first need to check that for all \(g\), \(\mu_g\) really is a permutation of \(S\). We will show this by proving that \(\mu_g\) has a two-sided inverse; in fact, that inverse is \(\mu_{g^{-1}}\).

Indeed, we have

thus \(\mu_g \circ \mu_{g^{-1}}=\mathrm{id}_S\), and a similar argument shows that \(\mu_{g^{-1}}\circ \mu_{g}=\mathrm{id}_S\) (exercise!). This shows that \(\mu_g\) has an inverse, and thus it is bijective; it must then be a permutation of \(S\).

Finally, we wish to show that \(\rho\) is a homomorphism of groups, so we need to check that \(\rho(gh)=\rho(g) \circ \rho(h)\). Equivalently, we need to prove that \(\mu_{gh}=\mu_g\circ\mu_{h}\). Now for all \(s\), we have

This proves that \(\rho\) is a homomorphism.

(2) On the other hand, given a homomorphism \(\rho\), the function

and \[ e_G \cdot s = \rho(e_G)(s) = \mathrm{id}(s) = s. \]

Proof of Lemma 2.1.6

Assume \(G\) acts on \(S\).

1. We really need to prove three things: that \(\sim_G\) is reflexive, symmetric, and transitive.
   
   (Reflexive): We have \(x \sim_G x\) for all \(x \in S\) since \(x = e_G \cdot x\).
   
   (Symmetric): If \(x \sim_G y\), then \(y = g \cdot x\) for some \(g \in G\), and thus \[ g^{-1} \cdot y = g^{-1} \cdot (g \cdot x) = (g^{-1}g) \cdot x = e \cdot x = x, \] which shows that \(y \sim_G x\).
   
   (Transitive): If \(x \sim_G y\) and \(y \sim_G z\), then \(y = g \cdot x\) and \(z = h \cdot y\) for some \(g, h \in G\) and hence \[ z = h \cdot (g \cdot x) = (hg) \cdot x, \] which gives \(x \sim_G z\).

Parts (b) and (c) are formal properties of the equivalence classes for any equivalence relation.

Proof of Corollary 2.1.7

This is an immediate corollary of the fact that the orbits form a partition of \(S\).

Proof of Lemma 3.1.7

We prove the One-step test first. Assume \(H\) is nonempty and for all \(x,y \in H\) we have \(xy^{-1} \in H\). Since \(H\) is nonempty, there is some \(h \in H\), and hence \(e_G = hh^{-1} \in H\). Since \(e_Gx=x=xe_G\) for any \(x\in G\), and hence for any \(x \in H\), then \(e_G\) is an identity element for \(H\). For any \(h \in H\), we have that \(h^{-1} = eh^{-1} \in H\), and since in \(G\) we have \(h^{-1}h = e = hh^{-1} \in H\) and this calculation does not change when we restrict to \(H\), we can conclude that every element of \(H\) has an inverse inside \(H\). For every \(x,y \in H\) we must have \(y^{-1} \in H\) and thus

so \(H\) is closed under the multiplication operation. This means that the restriction of the group operation of \(G\) to \(H\) is a well-defined group operation. This operation is associative by the axioms for the group \(G\). The axioms of a group have now been established for \((H, \cdot)\).

Now we prove the Two-step test. Assume \(H\) is nonempty and closed under multiplication and taking inverses. Then for all \(x,y\in H\) we must have \(y^{-1}\in H\) and thus \(xy^{-1}\in H\). Since the hypothesis of the One-step test is satisfied, we conclude that \(H\) is a subgroup of \(G\).

Proof of Lemma 3.1.8

1. By definition, \(K\) is a group under the multiplication in \(H\), and the multiplication in \(H\) is the same as that in \(G\), so \(K\) is a subgroup of \(G\).
2. First, note that \(H\) is nonempty since \(e_G \in H_\alpha\) for all \(\alpha\in J\). Moreover, given \(x,y\in H\), for each \(\alpha\) we have \(x,y \in H_\alpha\) and hence \(xy^{-1} \in H_\alpha\). It follows that \(xy^{-1} \in H\). By the Two-Step test, \(H\) is a subgroup of \(G\).
3. Since \(G\) is nonempty, then \(\mathrm{im}(f)\) must also be nonemtpy; for example, it contains \(f(e_G) = e_H\). If \(x,y \in \mathrm{im}(f)\), then \(x = f(a)\) and \(y = f(b)\) for some \(a,b \in G\), and hence \[ xy^{-1} =f(a)f(b)^{-1} = f(ab^{-1}) \in \mathrm{im}(f). \] By the Two-Step Test, \(\mathrm{im}(f)\) is a subgroup of \(H\).
4. The restriction \(g\!: K \to H\) of \(f\) to \(K\) is still a group homomorphism, and thus \(f(K) = \mathrm{im}(g)\) is a subgroup of \(H\).
5. Using the One-step test, note that if \(x, y \in \ker(f)\), meaning \(f(x)=f(y)=e_G\), then \[ f(xy^{-1})=f(x)f(y)^{-1}=e_G. \] This shows that if \(x,y\in \ker(f)\) then \(xy^{-1}\in \ker(f)\), so \(\ker(f)\) is closed for taking inverses. By the Two-Step test, \(\ker(f)\) is a subgroup of \(G\).
6. The center \(\mathrm{Z}(G)\) is the kernel of the permutation representation \(G\to \mathrm{Perm}(G)\) for the conjugation action, so \(\mathrm{Z}(G)\) is a subgroup of \(G\) since the kernel of a homomorphism is a subgroup.

Proof of Lemma 3.1.16

Let

Since \(\langle X \rangle\) is a subgroup that contains \(X\), it is closed under products and inverses, and thus must contain all elements of \(S\). Thus \(X \supseteq S\).

To show \(X \subseteq S\), we will prove that the set \(S\) is a subgroup of \(G\) using the One-step test:

• \(S \neq \emptyset\) since we allow \(m = 0\) and declare the empty product to be \(e_G\).
• Let \(a\) and \(b\) be elements of \(S\), so that they can be written as \(a = x_1^{j_1} \cdots x_m^{j_m}\) and \(b= y_1^{i_1} \cdots y_n^{i_n}\). Then
  \[ ab^{-1} = x_1^{j_1} \cdots x_m^{j_m}(y_1^{i_1} \cdots y_n^{i_m})^{-1}= x_1^{j_1} \cdots x_m^{j_m} y_n^{-i_n} \cdots y_1^{-i_1} \in S. \]

Therefore, \(S\leq G\) and \(X\subseteq S\) (by taking \(m=1\) and \(j_1=1\)) and by the minimality of \(\langle X \rangle\) we conclude that \(\langle X \rangle\subseteq S\).

Proof of Theorem 3.1.20

Suppose \(G\) is a finite group of order \(n\) and label the group elements of \(G\) from \(1\) to \(n\) in any way you like. The left regular action of \(G\) on itself determines a permutation representation \(\rho\!:G\to \mathrm{Perm}(G)\), which is injective. Note that since \(G\) has \(n\) elements, \(\mathrm{Perm}(G)\) is the group of permutations on \(n\) elements, and thus \(\mathrm{Perm}(G) \cong S_n\). By Lemma 3.1.8, \(\mathrm{im}(\rho)\) is a subgroup of \(S_n\). If we restrict \(\rho\) to its image, we get an isomorphism \(\rho\!: G \to \mathrm{im}(\rho)\). Hence \(G\cong \mathrm{im}(\rho)\), which is a subgroup of \(S_n\).

Proof

1. By the Lemma, we know \(G=\{x^i \mid i \in \mathbb{Z}\}\). Now we claim that the elements $$e = x^0, x^1, \dots, x^{n-1}$$ are all distinct. Indeed, if \(x^i=x^j\) for some \(0\leqslant i<j<n\), then \(x^{j-i}=e\) and \(1 \leqslant j-i<n\), contradicting the minimality of the order \(n\) of \(x\). In particular, this shows that \(|G| \geqslant n\).

   Now take any \(m \in \mathbb{Z}\). By the Division Algorithm, we can write \(m = qn+r\) for some integers \(q, r\) with \(0 \le r < n\). Then $$x^m=x^{nq+r}=(x^n)^q x^r=x^r.$$ This shows that every element in \(G\) can be written in the form \(x^r\) with \(0 \leqslant r < n\), so $$G = \{x^0, x^1, \dots, x^{n-1}\} \qquad \textrm{and} \qquad |G| = n.$$

2. This is part of the Homework.

3. Consider any subgroup \(H\) of \(G\) with \(H \neq \{ e \}\), and set $$k := \min \{i \in \mathbb{Z} \mid i>0 \ \textrm{and}\ g^i\in H\}.$$ On the one hand, \(H \supseteq \langle g^k \rangle\), since \(H \ni g^k\) and \(H\) is closed for products. Moreover, given any other positive integer \(i\) with \(g^i\in H\), we can again write \(i = kq+r\) for some integers \(q, r\) with \(0 \leqslant r < k\), and $$g^r = g^{i-kq} = g^i (g^{k})^{-q} \in H,$$ so by minimality of \(k\) we conclude that \(r = 0\). Therefore, \(k \mid i\), and thus we conclude that $$H = \langle g^k \rangle.$$ Now to show that \(\Psi\) is a bijection, we only need to prove that \(\Phi\) is a well-defined function and a two-sided inverse for \(\Psi\), and this we leave as an exercise. \( \)

Proof

The subgroup \(\langle x \rangle\) of \(G\) generated by \(x\) is a cyclic group, and since \(G\) is finite so is \(\langle x \rangle\). By Theorem 3.3.6 above, \(|x| = |\langle x \rangle|\), and by Lagrange's Theorem, the order of \(\langle x \rangle\) divides the order of \(G\).

Proof

Let \(A\) and \(B\) be subgroups of \(G\). We need to prove that \(A\) and \(B\) have an infimum and a supremum. We claim that \(A \cap B\) is the infimum and \(\langle A, B \rangle\) is the supremum. First, these are both subgroups of \(G\), by Lemma 3.1.18 in the case \(A \cap B\) and by definition for the other. Moreover, \(A \cap B\) is a lower bound for \(A\) and \(B\) and \(\langle A, B \rangle\) is an upper bound by definition. Finally, if \(H \leq A\) and \(H \leq B\), then every element of \(h\) is in both \(A\) and \(B\), and thus it must be in \(A \cap B\), so \(H \leq A \cap B\). Similarly, if \(A \leq H\) and \(B \leq H\), then \(\langle A, B \rangle \subseteq H\).

Proof

Recall that either \(G = \{e,x,x^2, \dots, x^{n-1}\}\) has exactly \(n\) elements if \(|x| = n\) or \(G = \{ x^i \mid i \in \mathbb{Z} \}\) with no repetitions if \(|x| = \infty\).

Uniqueness: We have already noted that any homomorphism is uniquely determined by the images of the generators of the domain in Remark 1.5.8, and that \(f\) must then be given by \(f(x^i) =f(x)^i = y^i\).

Existence: In either case, define \(f(x^i) = y^i\). We must show this function is a well-defined group homomorphism. To see that \(f\) is well-defined, suppose \(x^i=x^j\) for some \(i,j\in \mathbb{Z}\). Then, since \(x^{i-j}=e_G\), using Lemma 3.3.5 we have $$\begin{cases} n\mid i-j & \text{ if } |x|=n\\[2pt] i-j=0 & \text{ if } |x|=\infty \end{cases} \ \Rightarrow\ \begin{cases} y^{\,i-j}=y^{nk} & \text{ if } |x|=n\\[2pt] y^{\,i-j}=y^0 & \text{ if } |x|=\infty \end{cases} \ \Rightarrow\ y^{\,i-j}=e_H \ \Rightarrow\ y^ i=y^j.$$ Thus, if \(x^i=x^j\) then \(f(x^i)=y^i=y^j=f(x^j)\). In particular, if \(x^k = e\), then \(f(x^k) = e\), and \(f\) is well-defined.

The fact that \(f\) is a homomorphism is immediate: $$f(x^ix^j)=f(x^{i+j})=y^{i+j}=y^iy^j=f(x^i)f(x^j). $$

Proof

Suppose \(G = \langle x \rangle\) with \(|x| = n\) or \(|x| = \infty\), and set $$H=\begin{cases} C_n & \textrm{if } |x| = n \\ C_\infty & \textrm{if } |x| = \infty. \end{cases}$$ By the Universal Mapping Property for cyclic groups, there are homomorphisms \(f\!: G \to H\) and \(g\!: G \to H\) such that \(f(x) = a\) and \(g(a) =x\). Now \(g \circ f\) is an endomorphisms of \(G\) mapping \(x\) to \(x\). But the identity map also has this property, and so the uniqueness clause in the Universal Mapping Property for cyclic groups gives us \(g \circ f = \mathrm{id}_G\). Similarly, \(f \circ g = \mathrm{id}_H\). We conclude that \(f\) and \(g\) are isomorphisms.

Proof of Lemma 4.1.2

To say that the rule \([x] \cdot [y] = [xy]\) is well-defined is to say that for all \(x, x', y, y' \in G\) we have

So \([xy]=[x'y']\) if and only if whenever \(x\sim x'\) and \(y\sim y'\), then \(xy\sim x'y'\).

Assume \(\sim\) is compatible with multiplication. Then \(x\sim x'\) implies \(xy\sim x'y\) and \(y\sim y'\) implies \(x'y\sim x'y'\), hence by transitivity \(xy\sim x'y'\). Thus \([x] \cdot [y] = [xy]\) is well-defined.

Conversely, assume the rule \([x] \cdot [y] = [xy]\) is well-defined, so that

Setting \(y=y'\) gives us

Setting \(x=x'\) gives us

Hence \(\sim\) is compatible with multiplication.

So now assume that the multiplication rule is well-defined, which we have now proved is equivalent to saying that \(\sim\) is compatible with the multiplication in \(G\). We need to prove that \(G/\sim\) really is a group. Indeed, since \(G\) itself is a group then given any \(x,y,z \in G\) we have

Moreover, for all \(x \in G\) we have

so that \([e_G]\) is an identity for \(G/\sim\). Finally,

so that every element in \(G/\sim\) has an inverse; in fact, this shows that \([x]^{-1} = [x^{-1}]\).

Proof of Lemma 4.1.7

We will only prove the statements about left cosets, since the statements about right cosets are analogous.

(1 ⇒ 2). Suppose that \(x\) and \(y\) belong to the same left coset \(gH\) of \(H\) in \(G\). Then \(x=ga\) and \(y=gb\) for some \(a,b \in H\), so \(g=yb^{-1}\) and therefore \(x=yb^{-1}a=ya\) where \(h=b^{-1}a\in H\).

(2 ⇔ 3). We have \(x=yh\) for some \(h \in H\) if and only if \(y = xh^{-1}\) and \(h^{-1} \in H\).

(2 ⇔ 4). We have \(x=yh\) for some \(h \in H\) if and only if \(y^{-1} x=h\in H\).

(4 ⇔ 5). Note that \(y^{-1} x\in H \Leftrightarrow (y^{-1} x)^{-1}\in H \iff x^{-1}y\in H\).

(2 ⇒ 6). Suppose \(x = ya\) for some \(a \in H\). Then by (2 ⇒ 3) we also have \(y = xb\) for some \(b \in H\). Note that for all \(h \in H\), we also have \(ah \in H\) and \(bh \in H\). Then

and

Therefore, \(xH=yH\).

(6 ⇒ 1). Since \(e_G=e_H\in H\), we have \(x=xe_G\in xH\) and \(y=ye_G\in yH\). If \(xH=yH\) then, \(x\) and \(y\) belong to the same left coset.

Proof of Lemma 4.1.9

Since the left (respectively, right) cosets are the equivalence classes for an equivalence relation, the first part of the statement is just a special case of a general fact about equivalence relation.

Let us nevertheless write a proof for the assertions for right cosets.

Every element \(g \in G\) belongs to at least one right coset, since \(e \in H\) gives us \(g \in Hg\). Thus

Now we need to show any two cosets are either identical or disjoint: if \(Hx\) and \(Hy\) share an element, then it follows from (1 ⇒ 6) of Lemma 4.1.7 that \(Hx=Hy\). This proves that the right cosets partition \(G\).

To see that all right cosets have the same cardinality as \(H\), consider the function

This function \(\rho\) is surjective by construction. Moreover, if \(\rho(h) = \rho(h')\) then \(hg = h'g\) and thus \(h = h'\). Thus \(\rho\) is also injective, and therefore a bijection, so \(|Hg| = |H|\).

Proof of Lemma 4.2.4

Note that \(gNg^{-1} = N\) if and only if \(gN = Ng\) and hence (a) \(\iff\) (c).

The implication \((a) \Rightarrow (b)\) is immediate. Conversely, if \(gNg^{-1} \subseteq N\) for all \(g\), then

Thus (b) implies (a).

Finally, \((b)\), \((d)\), and \((e)\) are all equivalent since

and

Proof of Lemma 4.2.12

Consider the sign map \(\operatorname{sign}\!\!: S_n \to \mathbb{Z}/2\) that takes each permutation to its sign, meaning

This a group homomorphism (exercise!), and by construction the kernel of \(\operatorname{sign}\) is \(A_n\). Since kernels of group homomorphisms are normal subgroups, we conclude that \(A_n\) must be a normal subgroup of \(S_n\).

Alternatively, we can prove the Lemma by showing that \(A_n\) is a subgroup of \(S_n\) of index \(2\).

Proof of Lemma 4.2.13

(\(\Rightarrow\)) Suppose \(\sim\) is compatible with multiplication, and set \(N := \{g \in G \mid g \sim e\}\). Then we claim that \(N\trianglelefteq G\) and \(\sim=\sim_N\).

To see that \(N\trianglelefteq G\), first we check that \(N\) is a subgroup of \(G\) using the two-step test. Since \(e\sim e\), \(N\) is nonempty. If \(g \in N\) and \(h\in N\), then \( g\sim e\) and \( h\sim e\), so \( gh \sim ge = g \sim e\), so \(gh\in N\), and \( e = g g^{-1} \sim e g^{-1} = g^{-1}\) so \(g^{-1} \in N\). Thus, \(N \leq G\). Now let \(n\in N\) and \(g\in G\). Since \(n\in N\), then \(n \sim e\), and thus since \(\sim\) is compatible with multiplication we conclude that for all \(g \in G\) we have

This shows that \(gng^{-1} \subseteq N\) for any \(n \in N\) and any \(g\in G\), and thus \(N\) is a normal subgroup of \(G\).

It remains to check that \(\sim=\sim_N\). Given any \(a, b \in G\), since \(\sim\) is compatible with multiplication then

Thus there exists some \(h \in H\) such that

(\(\Leftarrow\)) If \(\sim \,= \,\sim_N\), let \(x,y,z\in G\) such that \(x\sim_N y\). Then \(y=nx\) for some \(n\in N\), so \(yz=nxz\) and

for some \(n'\in N\), where the last equality uses the normal subgroup property. We deduce that \(yz\sim_N xz\) and \(zy\sim_N zx\), so \(\sim_N\) is compatible with multiplication.

Proof of Lemma 4.3.8

Surjectivity is immediate from the definition. Now we claim that \(\pi\) is a group homomorphism:

Finally, by our lemma on costs, we have \[ \ker(\pi)=\{g\in G\mid gN=e_GN\}=N. \]

Proof of Corollary 4.3.11

The kernel of any group homomorphism is a normal subgroup; we have just shown that every normal subgroup can be realized as the kernel of a group homomorphism.

Proof (of Theorem 4.4.1)

Suppose that such a homomorphism \(\overline{f}\) exists. Since \(f=\pi\circ \overline f\), then \(\overline{f}\) has to be given by \[ \overline{f}(gN) = \overline{f}(\pi(g)) = f(g). \] In particular, \(\overline f\) is necessarily unique. To show existence, we just need to show that this formula determines a well-defined homomorphism. Given \(xN = yN\), we have \[ y^{-1}x \in N \subseteq \ker(f) \] and so \[ f(y)^{-1} f(x) = f(y^{-1}x) = e \implies f(y) = f(x). \] This shows that \(\overline{f}\) is well-defined. Moreover, for any \(x,y \in G\), we have \[ \overline{f}((xN)(yN)) = \overline{f}((xy)N) = f(xy) = f(x)f(y) =\overline{f}(xN) \overline{f}(yN). \] Thus \(\overline{f}\) is a group homomorphism.

The fact that \(\mathrm{im} f=\mathrm{im} \overline f\) is immediate from the formula for \(\overline f\) given above, and hence \(f\) is surjective if and only if \(\overline f\) is surjective.

Finally, we have \[ xN \in \ker (\overline{f}) \iff \overline{f}(xN) = e_H \iff f(x) = e_H \iff x \in \ker(f). \] Therefore, if \(xN \in \ker (\overline{f})\) then \(xN \in \ker(f)/N\). On the other hand, if \(xN \in \ker(f)/N\) for some \(x \in G\), then \(xN = yN\) for some \(y \in \ker(f)\) and hence \(x = yz\) for some \(z \in N\). Since \(N \subseteq \ker(f)\), then \(x, y \in \ker(f)\), and thus we conclude that \(x = yz \in \ker(f)\).

Proof (of Corollary 4.4.2)

Let \(\pi\!: G \to G^\textrm{ab} = G/[G,G]\) be the canonical projection. Since \(A\) is abelian, then \[ f([x,y]) = [f(x),f(y)] = e \] for all \(x, y \in G\), and thus \([G,G] \subseteq \ker(f)\). By the Universal Mapping Property for quotient groups, the homomorphism \(f\) must uniquely factor as \[ f\!:G \stackrel{\pi}{\longrightarrow} G/[G,G] \stackrel{\overline{f}}{\longrightarrow} A. \]

Proof (of Theorem 4.4.3)

Let us first restrict the target of \(f\) to \(\mathrm{im}(f)\), so that we can assume without loss of generality that \(f\) is surjective. By the Universal Mapping Property for quotient groups, there exists a (unique) homomorphism \(\overline{f}\) such that \(\overline{f} \circ \pi = f\), where \(\pi\!: G \to G/\ker(f)\) is the canonical projection. Moreover, the kernel \(\ker(f)/\ker(f)\) of \(\overline{f}\) consists of just one element, the coset \(\ker(f)\) of the identity, and so \(\overline{f}\) it injective. Moreover, the Universal Mapping Property for quotient groups also says that the image of \(\overline{f}\) equals the image of \(f\). We conclude that \(\overline{f}\) is an isomorphism.

Proof (of Theorem 4.4.11)

We leave the facts that \(HN \leq G\) and \(N \cap H \trianglelefteq H\) as exercises. Since \(N \trianglelefteq G\), then \(N \trianglelefteq HN\). Let \(\pi\!: HN \to \frac{HN}{N}\) be the canonical projection. Define \[ \begin{aligned} H &\xrightarrow{\ f\ }& HN/N \\ h &\longmapsto & f(h)=hN \end{aligned} \] This is a homomorphism, since it is the composition of homomorphisms \[ f\!: H \subseteq HN \stackrel{\pi}{\longrightarrow} \frac{HN}{N}, \] where the first map is just the inclusion. Moreover, \(f\) is surjective since \[ hnN = hN = f(h) \] for all \(h \in H\) and \(n \in N\). The kernel of \(f\) is \[ \ker(f)=\{h \in H \mid hN = N\} = H \cap N. \] The result now follows from the First Isomorphism Theorem applied to \(f\).

Proof (of Corollary 4.4.12)

By the Diamond Isomorphism Theorem, \[ \frac{H}{N \cap H} \cong \frac{HN}{N}. \] The result now follows from Lagrange's Theorem: \[ \frac{|H|}{|N \cap H|} = \frac{|HN|}{|N|}. \]

Proof (of Theorem 4.4.14)

We showed that the quotient map \(\pi\!:G\to G/N\) is a surjective group homomorphism. It will be useful to rewrite the maps in the statement of the theorem in terms of \(\pi\). Notice that \(\Psi(H)=H/N=\{hN \mid h\in H\}=\pi(H)\). Note that \(\Psi\) does indeed land in the correct codomain, since images of subgroups through group homomorphisms are subgroups, and thus \(\pi(H)\leq G/N\) for each \(H \leq G\). Thus \(\Psi\) is well-defined. We claim \(\Phi\) also lands in the correct codomain. Indeed, preimages of subgroups through group homomorphisms are subgroups, and thus in particular for each \(A \leq G\) we have \(\pi^{-1}(A)\leq G\). Moreover, for any \(A \leq G\) we have \(\{e_GN\} \subseteq A\), hence \[ N = \ker(\pi) = \pi^{-1}(\{e_GN\}) \subseteq \pi^{-1}(A) = \Phi(A). \] Thus \(\Psi\) is well-defined.

To show that \(\Psi\) is bijective, we will show that \(\Phi\) and \(\Psi\) are mutual inverses. First, note that since \(\pi\) is surjective, then \(\pi(\pi^{-1}(A))=A\) for all subgroups \(A\) of \(G/N\), and thus \[ (\Psi\circ\Phi)(A)=\pi(\pi^{-1}(A))=A. \] Moreover, \[ \begin{aligned} x\in \pi^{-1}(H/N) &\iff \pi(x)\in H/N \\ & \iff xN=hN & \text{ for some } h\in H \\ & \iff x\in hN & \text{ for some } h\in H \\ & \iff x\in H & \text{since } N\subseteq H. \end{aligned} \] Thus \[ (\Phi\circ\Psi)(H)=\pi^{-1}(\pi(H))=\pi^{-1}(H/N)=H. \] Thus, \(\Psi\) and \(\Phi\) are well-defined and inverse to each other. Since \(\pi\) and \(\pi^{-1}\) both preserve containments, each of \(\Psi\), \(\Psi^{-1}\) preserves containments as well.

Again, images and preimages of subgroups by group homomorphisms are subgroups, which proves (1). Moreover, if \(N \leq H \leq G\) and \(H \trianglelefteq G\), then \(ghg^{-1} \in H\) for all \(g \in G\) and all \(h \in G\), and thus \[ (gN)(hN)(gN)^{-1}= (ghg^{-1})N \in H/N. \] Therefore, if \(N \leq H \trianglelefteq G\), then \(H/N \trianglelefteq G/N\). Finally, the preimage of a normal subgroup is normal. We have now shown (2).

We leave (3) as an exercise, and (4) is a consequence of the more general fact that lattice isomorphisms preserve suprema and infima.

Proof (of Theorem 4.4.16)

Since \(M\) is a normal subgroup of \(G\), then it is also a normal subgroup of \(N\). Similarly, the fact that \(N\) is normal in \(G\) implies that it is normal in \(G/M\) by the Lattice Isomorphism Theorem.

The kernel of the canonical map \(\pi: G \twoheadrightarrow G/N\) contains \(M\), and so by the Universal Mapping Property of quotient groups we get an induced homomorphism \[ \phi\!: G/M \to G/N \] with \(\phi(gM) = \pi(g) = gN\). Moreover, we know \[ \ker(\phi) = \ker(\pi)/M = N/M. \] Finally, apply the First Isomorphism Theorem to \(\phi\).

Proof (of Corollary 4.4.17)

By the Cancelling Isomorphism Theorem, \[ G/H \cong \frac{(G/N)}{(H/N)} \] and thus their orders are the same; in particular, \[ [G:H] = |G/H| = \left| \frac{(G/N)}{(H/N)} \right| = [G/N: H/N]=[G/N : H/N]. \]

Proof (of Theorem 4.5.3)

Let \(f\!:F(A) \to H\) be given by \[ f(a_1^{i_1}a_2^{i_2}\cdots a_m^{i_m})=g(a_1)^{i_1}g(a_2)^{i_2}\cdots g(a_m)^{a_m} \] for any \( m\geqslant 0\), \(a_j \in A\), and \(i_j\in\{-1,1\}\). To check that this is a well-defined function, note that \[ f(a_1^{i_1}a_2^{i_2}\cdots aa^{-1}\cdots a_m^{i_m})=g(a_1)^{i_1}g(a_2)^{i_2}\cdots g(a)g(a)^{-1}\cdots g(a_m)^{a_m}=f(a_1^{i_1}a_2^{i_2}\cdots a_m^{i_m}) \] for any \(a\in G\) and similarly for inserting \(a^{-1}a\). The fact that \(f\) is a group homomorphism and its uniqueness are left as an exercise.

Proof (of Theorem 4.5.8)

By the universal mapping property free groups, there is a unique group homomorphism \(\tilde f:F(A)\to H\) such that \(f(a)=g(a)\) for all \(a\in A\). Then for \[ r = a_1^{i_1} \cdots a_m^{i_m} \in R \] we have \[ f(r)=(g(a_1))^{i_1} \cdots (g(a_m))^{i_m} = e_H, \] showing that \(R\subseteq \ker(f)\). Since \(\ker(f)\trianglelefteq F(A)\) and \(\langle R\rangle ^N\) is the smallest normal subgroup containing \(R\), it follows that \(\langle R\rangle^N\subseteq \ker(f)\). By the UMP for quotient groups, \(f\) induces a group homomorphism \(\overline{f}: G/\langle R\rangle ^N\to H\). Moreover, for each \(a\in A\) we have \[ g(a)=f(a)=\overline f(a\langle R\rangle ^N). \]

Proof (of Lemma 5.1.4)

By definition of group action, \(e \cdot s = s\), so \(e \in \mathrm{Stab}_G(e)\). If \(x,y \in \mathrm{Stab}_G(s)\), then \((xy)s = x(ys) = xs = s\) and thus \(xy \in \mathrm{Stab}_G(s)\). If \(x \in \mathrm{Stab}_G(s)\), then

\[ xs = s \Rightarrow s = x^{-1}xs = x^{-1}s \Rightarrow x^{-1} \in \mathrm{Stab}_G(s). \]

Proof (of Theorem 5.1.5)

Let \(\mathcal{L}\) be the collection of left cosets of \(\mathrm{Stab}_G(s)\) in \(G\). Let \(\alpha: \mathcal{L} \to \mathrm{Orb}_G(s)\) be given by

\[ \alpha(x \mathrm{Stab}_G(s)) = x \cdot s. \]

This function is well-defined and injective:

\[ x \mathrm{Stab}_G(s) = y \mathrm{Stab}_G(s)\iff x^{-1}y \in \mathrm{Stab}_G(s) \iff x^{-1}y \cdot s = s \iff y \cdot s = x \cdot s. \]

The function \(\alpha\) is surjective by definition of \(\mathrm{Orb}_G(s)\), and thus it is a bijection. Finally, we can now conclude that

\[ [G: \mathrm{Stab}_G(s)] = |\mathcal{L}| = |\mathrm{Orb}_G(s)|. \]

Proof (of Corollary 5.1.6)

This is a direct consequence of the Orbit-Stabilizer Theorem, since by Lagrange's Theorem

\[ [G: \mathrm{Stab}_G(s)]=|G|/|\mathrm{Stab}_G(s)|. \]

Proof (of Theorem 5.2.4)

Consider two conjugate elements of \(S_n\), say \(\alpha\) and \(\beta = \sigma\alpha \sigma^{-1}\). By earlier work, we may write \(\alpha\) as a product of disjoint cycles \(\alpha = \alpha_1 \cdots \alpha_m\). Then \[ \beta = \sigma\alpha \sigma^{-1} = (\sigma\alpha_1 \sigma^{-1}) \cdots (\sigma\alpha_m \sigma^{-1}). \] Since \(\alpha_1, \ldots, \alpha_m\) are disjoint cycles, the elements \((\sigma\alpha_1 \sigma^{-1}), \cdots, (\sigma\alpha_m \sigma^{-1})\) are also disjoint cycles, and \(\sigma\alpha_i \sigma^{-1}\) has the same length as \(\alpha_i\). We conclude that \(\alpha\) and \(\beta\) must have the same cycle type.

Conversely, consider two elements \(\alpha\) and \(\beta\) with the same cycle type. More precisely, assume \(\alpha = \alpha_1 \cdots \alpha_k\) and \(\beta = \beta_1 \cdots \beta_k\) are decompositions into disjoint cycles and that \(\alpha_i, \beta_i\) both have length \(p_i \geqslant 2\) for each \(i\). We need to prove that \(\alpha\) and \(\beta\) are conjugate. Let us start with the case \(k = 1\). Given two cycles of the same length, \[ \alpha = (i_1 \, \dots \, i_p) \quad \text{ and } \quad \beta = (j_1 \, \dots \, j_p). \] Any permutation \(\sigma\) such that \(\sigma(i_m) = j_m\) for all \(1 \leqslant m \leqslant p\) must satisfy \(\sigma\alpha \sigma^{-1} = \beta\).

Note that such \(\sigma\) has no restrictions on what it does to the set \(\{1, \dots, n\} \setminus \{i_1 \, \dots \, i_p\}\): it can map \(\{1, \dots, n\} \setminus \{i_1 \, \dots \, i_p\}\) bijectively to \(\{1, \dots, \} \setminus \{j_1 \, \dots \, j_p\}\) in any way possible. From this observation, the general case follows: since the cycles are disjoint, we can find a single permutation \(\sigma\) such that \(\sigma\alpha_i \sigma^{-1} = \beta_i\) for all \(i\).

Proof (of Lemma 5.2.11)

Let \(G\) be a group and \(S \subseteq G\). If \(x \in C_G(S)\), then for all \(s \in S\) we have \[ xs=sx \implies xsx^{-1} = s \in S \textrm{ and } x^{-1}sx = s. \] Thus \(xSx^{-1} \subseteq S\) and \(x^{-1}Sx \subseteq S\). Now for any \(s \in S\) we have \(x^{-1}sx \in S\) and \(s\) can be written as \[ s = x(x^{-1}sx)x^{-1} \in xSx^{-1}. \] This shows that \(S \subseteq xSx^{-1}\). Thus \(xSx^{-1} = S\), and therefore \(x \in N_G(S)\).

Proof (of Lemma 5.2.16)

The first statement is the definition of the conjugacy class of \(g\): \(\mathrm{Orb}_G(g) = [g]_c\). Moreover, by simply following the definitions we see that \[ h \in \mathrm{Stab}_G(g) \iff h \cdot g = g \iff hgh^{-1} = g \iff hg = gh \iff h \in C_G(G). \] Thus, \(\mathrm{Stab}_G(g)=C_G(G)\), and by the Orbit-Stabilizer Theorem, \[ |[g]_c| = |\mathrm{Orb}_G(g)| = [G : C_G(g)]. \]

Proof (of Corollary 5.2.18)

Let \(g \in G\). The order of the conjugacy class of \(g\) is the index of the centralizer: \[ |[g]_c| = [G : C_G(g)] \] By Lagrange's Theorem, the index of any subgroup must divide \(|G|\), and thus in particular \(|[g]_c|\) divides \(|G|\).

Proof (of Lemma 5.2.19)

\((\Leftarrow)\) Suppose that \(g \in \mathrm{Z}(G)\). Then for all \(h \in G\), \(g\) commutes with \(h\), and thus \[ hgh^{-1} = (hg)h^{-1} = g(hh^{-1}) = g. \] Thus \(g\) is conjugate to only itself, meaning it is a fixed point for the conjugation action.

\((\Rightarrow)\) Conversely, suppose that \(g\) is a fixed point for the conjugation action. Then for all \(h \in G\), \[ hgh^{-1} = h \cdot g = g \implies hg=gh. \] Thus \(g \in \mathrm{Z}(G)\).

Proof (of Theorem 5.2.20)

The elements of \(\mathrm{Z}(G)\) are precisely the fixed points of the conjugation action. In particular, \(|\mathrm{Z}(G)|\) counts the number of orbits that have only one element. Because the orbits of the conjugation action partition \(G\), and the conjugacy classes are the orbits, then as noted in the orbit equation, \[ |G| = |\mathrm{Z}(G)| + \sum_i^r [g_i]_c. \] By the Orbit-Stabilizer Theorem, the index of the stabilizer is the order of the conjugacy class. Thus for each \(g_i\) as in the statement we have \[ [g_i]_c = [G: C_G(g_i)]. \] The class equation follows from substituting this into the equation above: \[ |G| = |\mathrm{Z}(G)| + \sum_i^r |G : C_G(g_i)|. \]

Proof (of Corollary 5.2.23)

Let \(g_1,\ldots g_r \in G\) be a list of unique representatives of all of the conjugacy classes of \(G\) of size greater than 1, as in the class equation. By construction, each \(g_i\) is not a fixed point of the action, and thus \(\mathrm{Stab}_G(g_i) \neq G\). We have \(C_G(g_i) = \mathrm{Stab}_G(g_i)\), so \(C_G(g_i) \neq G\). In particular, \([G:C_G(g_i)]\neq 1\). Since \(1\neq [G:C_G(g_i)]\) and \([G:C_G(g_i)]\) divides \(|G|=p^m\), we conclude that \(p\) divides \([G:C_G(g_i)]\) for each \(i\). From the class equation, we can now conclude that \(p\) divides \(|\mathrm{Z}(G)|\), and in particular \(|\mathrm{Z}(G)|\neq 1\).

Proof (of Lemma 5.2.25)

Define the conjugation action of \(G\) on \(N\) by \(g\cdot n=gng^{-1}\) for all \(g\in G\) and \(n\in N\). Since \(N\trianglelefteq G\), this always gives us back an element of \(N\), and thus the action is well-defined. We can think of this action as a restriction of the action of \(G\) on itself by conjugation, and thus the two properties in the definition of an action hold for the action of \(G\) by conjugation on \(N\). Therefore, this is indeed an action. The orbits of elements \(n\in N\) under this action are the conjugacy classes \([n]_c\), and we have just shown that for all \(n \in N\), \([n]_c \subseteq N\). But every element in \(N\) belongs to some conjugacy class, thus the conjugacy classes of the elements of \(N\) partition \(N\).

Proof (of Lemma 5.3.2)

Recall from earlier that, \[ (i_1 \, i_2 \, \cdots \, i_m) = (i_1 \, i_m) (i_1 \, i_{m-1}) (i_1 \, i_3) (i_1 \, i_2) \] is a product of \(m-1\) transpositions. Thus \(\sigma\) is even if and only if \(m-1\) is even.

Proof (of Lemma 5.3.3)

By the work above, the cycle types of elements of \(A_5\) are

• five cycles, of which there are \(4! = 24\),
• three cycles, of which there are \({5 \choose 3} 2 = 20\),
• products of two disjoint transpositions, of which there are \(5 \cdot 3 = 15\), and
• the unique \(1\)-cycle \(e\), and indeed \([e]_c = \{e\}\).

By our computation of conjugacy classes on in \(S_n\), we know that two permutations are conjugate in \(S_5\) if and only if they have the same cycle type. It follows that the conjugacy classes in \(A_5\) form a subset of the cycles types. The statement we are trying to prove asserts that the set of five cycles breaks apart into two conjugacy classes in \(A_5\), whereas in all the other cases, the conjugacy classes remain whole.

Claim: Fix a \(5\)-cycle \(\sigma\). The conjugacy class of \(\sigma\) in \(A_5\) has \(12\) elements.

By Lagrange's Theorem, \[ |C_{S_5}(\sigma)| = \frac{|S_5|}{[S_5 : C_{S_5}(\sigma)]}. \] Thus, \[ [S_5 : C_{S_5}(\sigma)] = |[\sigma]_c|. \] By our computation of conjugacy classes on in \(S_n\), this is the number of \(5\)-cycles in \(S_5\), which is \(4!\). Thus \[ |C_{S_5}(\sigma)| = \frac{5!}{4!} = 5. \] Since every power of \(\sigma\) commutes with \(\sigma\), and there are \(5\) such elements, we conclude that \[ C_{S_5}(\sigma) = \{e, \sigma, \sigma^2, \sigma^3, \sigma^4\}. \] But these are all in \(A_5\), and thus by an earlier lemma we conclude that \[ C_{A_5}(\sigma) = C_{S_5}(\sigma) \cap A_5 = \{e, \sigma, \sigma^2, \sigma^3, \sigma^4\}. \] By the Orbit-Stabilizer Theorem and Lagrange's Theorem, \[ \text{ the size of the conjugacy class of \(\sigma\) in \(A_5\)} = [A_5: C_{A_5}(\sigma)] = \frac{|A_5|}{|C_{A_5}(\sigma)|} = \frac{60}{5} = 12. \] This proves the claim.

We have now shown that the conjugacy class of each \(5\)-cycle has \(12\) elements, and all twenty-four \(5\)-cycles are in \(A_5\). Thus there are two conjugacy classes of \(5\)-cycles in \(A_5\). This shows that \(\sigma\) is only conjugate in \(A_5\) to half of the five cycles. If we pick two \(5\)-cycles \(\sigma\) and \(\tau\) that are not conjugate in \(A_5\), then \(\tau\) is conjugate to exactly \(12\) elements, which must be exactly the other \(5\)-cycles that \(\sigma\) is not conjugate to.

One can see that in fact \((1 \, 2 \, 3 \, 4 \, 5)\) and \((2 \, 1 \, 3 \, 4 \, 5)\) are not conjugate. While they are conjugate in \(S_5\), it is via the element \((1 \,2)\), which is not in \(A_5\). Suppose that \(\alpha \in S_5\) is such that \[ \alpha (2 \, 1 \, 3 \, 4 \, 5) \alpha^{-1} = (1 \, 2 \, 3 \, 4 \, 5). \] Note that \(\tau = \alpha (1 \, 2)\) satisfies \[ \begin{aligned} \tau (1 \, 2 \, 3 \, 4 \, 5) & = \alpha (1 \, 2) (1 \, 2 \, 3 \, 4 \, 5) \\ & = \alpha (2 \, 1 \, 3 \, 4 \, 5) \\ & = (2 \, 1 \, 3 \, 4 \, 5) \alpha \\ & = (1 \, 2 \, 3 \, 4 \, 5) (1 \, 2) \alpha \\ & = (1 \, 2 \, 3 \, 4 \, 5) \tau. \end{aligned} \] Thus \(\alpha (1 \, 2) \in C_{S_5}(1 \, 2 \, 3 \, 4 \, 5)\), or equivalently, \[ \alpha \in (1 \, 2) \cdot C_{S_5}(2 \, 1 \, 3 \, 4 \, 5). \] But note that we just proved that every element in \(C_{S_5}(2 \, 1 \, 3 \, 4 \, 5)\) is in \(A_5\), and thus even; this shows that every element in the coset \[ (1 \, 2) \cdot C_{S_5}(2 \, 1 \, 3 \, 4 \, 5) \] is odd (as we multiplied by one transposition), and thus there are no such \(\alpha\) in \(A_5\). This proves (1) and (2).

Claim: All \(20\) three cycles are conjugate in \(A_5\).

Given two three cycles \((a \, b \, c)\) and \((d \, e \, f)\) in \(S_5\), we already know that they are both in \(A_5\) and that there is a \(\sigma \in S_5\) such that \[ \sigma (a \, b \, c) \sigma^{-1} = (d \, e \, f). \] If \(\sigma \notin A_5\), let \(\{1, \dots, 5\} \setminus \{a,b,c\} = \{ x, y\}\). Then \(\sigma\) is a product of an odd number of transpositions, so \(\sigma \cdot (x \, y) \in A_5\). Moreover, since \((x \, y)\) and \((a \, b \, c)\) are disjoint cycles, so they must commute, so that \[ (x \, y) (a \, b \, c) (x \, y))^{-1} = (a \, b \, c). \] Therefore, \[ (\sigma \cdot (x \, y)) (a \, b \, c) (\sigma \cdot (x \, y))^{-1} = (d \, e \, f), \] so \((a \, b \, c)\) and \((d \, e \, f)\) are still conjugate in \(S_5\). This proves the claim.

Claim: All products of two disjoint transpositions are conjugate in \(A_5\).

Set \(\alpha = (1 \, 2)(3 \, 4)\). The conjugacy class of \(\alpha\) in \(S_5\) consists of all the products of two disjoint two-cycles, and there are \(15\) such elements. By the Orbit-Stabilizer Theorem, \[ 15 = |\text{ the conjugacy class of \(\alpha\) in \(S_5\) }| = [S_5: C_{S_5}(\alpha)]=\frac{120}{\left|C_{S_5}(\alpha)\right|}. \] Thus \[ \left|C_{S_5}(\alpha)\right| = \frac{120}{15} = 8. \] Since \(\alpha\) commutes with \(e\), \(\alpha\), \((1 \, 3)(2 \, 4)\) and \((1 \, 4)(2 \, 3)\) and each of these belongs to \(A_5\), we must have \(|C_{A_5}(\alpha)| \geqslant 4\). Since \[ C_{A_5}(\alpha) = C_{S_5}(\alpha) \cap A_5, \] it follows that \(|C_{A_5}(\alpha)|\) must divide both \(8\) and \(60\), and so must be \(1\), \(2\) or \(4\). We conclude that \(|C_{A_5}(\alpha)| = 4\). Thus \(\alpha\) is conjugate in \(A_5\) to \(60/4 = 15\) elements. Since there are \(15\) products of disjoint two-cycles, they must all be conjugate to \(\alpha\), and thus the conjugacy class of \(\alpha\) in \(A_5\) is still the set of all \(2\)-cycles.

Proof (of Theorem 5.3.6)

Suppose \(N \trianglelefteq A_5\). By Lagrange's Theorem, \(|N|\) divides \[ |A_5| = \frac{5!}{2} = 60. \] Then \(A_5\) has only four nontrivial conjugacy classes, and they have order \(12\), \(12\), \(15\), and \(20\). Since \(N\) is normal, it is a union of conjugacy classes of \(A_5\). Thus \[ |N| = 1 + \text{ the sum of a sublist of the list } 20, 12, 12, 15. \] By checking the relatively small number of cases we see that \(|N| = 1\) or \(|N| = 60\) are the only possibilities, as the remaining options do not divide \(60\).

Proof (of Lemma 5.4.1)

Note that

Thus

Since \(eHe^{-1} = H\), we conclude that \(\ker(g) \subseteq H\).

Proof (of Theorem 5.4.4)

The action of \(G\) on the set of left cosets of \(H\) in \(G\) by left multiplication induces a homomorphism \(\rho\!: G \to S_p\). By the Lemma above, its kernel \(N := \ker(\rho)\) is contained in \(H\). By the First Isomorphism Theorem, \[ [G:N] = |G/N| = |\mathrm{im}(f)|. \] By Lagrange's Theorem, since \(\mathrm{im}(f)\) is a subgroup of \(S_p\) then \([G:N] = |\mathrm{im}(f)|\) divides \(|S_p|=p!\). On the other hand, \([G:N]\) divides \(|G|\) by Lagrange's Theorem. Since \([G:N]\) divides both \(|G|\) and \(p!\), it must divide \(\gcd(|G|,p!)\). Since \(p\) is the smallest prime divisor of \(G\), we must have \[ \gcd(|G|, p!) = p. \] It follows that \([G:N]\) divides \(p\), and hence \([G:N] =1\) or \([G:N] = p\). But \(N \subseteq H\), and \(H\) is a proper subgroup of \(G\), so \(N \neq G\), and thus \([G:N] \neq 1\). Therefore, we conclude that \([G:N] = p\). Since \(N \subseteq H\) and \([G:H] = p = [G : N]\), we conclude that \(H = N\). In particular, \(H\) must be a normal subgroup of \(G\).

Proof (of Lemma 5.4.8)

The number of subgroups of \(G\) that are conjugate to \(H\) is just the size of the orbit of \(H\) under the action of \(G\) by conjugation on the set of subgroups of \(G\). By the Orbit-Stabilizer Theorem, the number of elements in the orbit of \(H\) is the index of the stabilizer. Finally, by above, the stabilizer of \(H\) is \(N_G(H)\).

Proof (of Lemma 5.4.9)

First, suppose that \(H\) is a normal. Then \(H = xHx^{-1}\) for all \(x \in G\), so \[ \bigcup_x xHx^{-1} = H \neq G. \] Now assume that \(H\) is not normal, so that \(N_G(H) \neq G\) and \([G: N_G(H)] \geqslant 2\). By Lemma 5.4.8, we have \(|H| = |xHx^{-1}|\) for all \(x\). Since there are \([G: N_G(H)]\) conjugates of \(H\) by Lemma 5.4.8, and since \(e \in xHx^{-1}\) for all \(x\), we get \[ \left| \, \bigcup_x xHx^{-1} \right| \leqslant [G:N_G(H)] \cdot |H|. \] But in fact, this calculation can be improved, as there are at least two distinct conjugates of \(H\) and \(e\) is an element of all of them. This gives us \[ \left| \, \bigcup_x xHx^{-1} \right| \leqslant [G:N_G(H)] \cdot |H| - 1. \] But \(H \subseteq N_G(H)\) and so \([G: N_G(H)] \leq [G:H]\). We conclude that \[ \left| \, \bigcup_x xHx^{-1} \right| \leqslant [G:H] \cdot |H| - 1 = |G| - 1. \]

Proof (of Theorem 6.1.1)

Let \(S\) denote the set of ordered \(p\)-tuples of elements of \(G\) whose product is \(e\):

Consider

and the map

Given the definition of \(S\), the map \(\phi\) does indeed land in \(S\). Moreover, \(\phi\) is bijective since the map \(\psi\!: S \to G^{p-1}\) given by

is a two-sided inverse of the map above. Therefore, \(|S| = |G^{p-1}| = |G|^{p-1}\).

Let \(C_p\) denote cyclic subgroup of \(S_p\) of order \(p\) generated by the \(p\)-cycle

The following rule gives an action of \(C_p\) on \(S\):

where the indices are taken modulo \(p\). We should check that this is indeed an action. On the one hand, \(\sigma^0\) is the identity map, so

Moreover,

while

Thus

and we have shown that this is indeed an action.

Now let us consider the fixed points of this action. If

then \(x_{i+1}=x_i\) for \(1 \leqslant i \leqslant p\), so it follows that

Thus if \(\sigma \cdot (x_1, \dots, x_p) = (x_1, \dots, x_p)\), then \((x_1, \dots, x_p)\) corresponds to an element \(x\) such that \(x^p = x_1 \cdots x_p = e\). On the other hand, if \(\sigma\) fixes \((x_1, \dots, x_p)\), then so does any element of \(C_p\). Therefore, a fixed point for this action corresponds to an element \(x\) such that \(x^p = e\). The element \((e, e, \dots, e)\) is a fixed point. Any other fixed point, meaning an orbit of size one, corresponds to an element of \(G\) order \(p\), thus we wish to show that there is at least one fixed point besides \((e, \dots, e)\).

By the Orbit-Stabilizer Theorem, the size of every orbit divides \(|C_p| = p\). Since \(p\) is prime, every orbit for this action has size \(1\) or \(p\). By the Orbit Equation,

Since \(p\) divides \(|S|\), we conclude that \(p\) divides the number of fixed points. We already know that there is at least one fixed point, \((e, \dots, e)\). Thus there must be at least one other fixed point; in fact, at least \(p-1\) others, since the number of fixed points must then be at least \(p\).

Proof (of Lemma 6.2.6)

\((\subseteq)\) Since \(P \leq N_G(P)\), then \(Q \cap P \leq Q \cap N_G(P)\).

\((\supseteq)\) Let \(H := Q \cap N_G(P)\). Since \(H \subseteq N_G(P)\), then \(PH=HP\), so we get that \(PH\) is a subgroup of \(G\). By the Diamond Isomorphism Theorem, we have

and since each of \(|P|\), \(|H|\), and \(|P \cap H|\) is a power of \(p\), we conclude that the order of \(PH\) is also a power of \(p\). In particular, \(PH\) is a \(p\)-subgroup of \(G\). On the other hand, \(P \leq PH\) and \(P\) is already a \(p\)-subgroup of the largest possible order, so we must have \(P = PH\). Note that \(H \leq PH\) always holds. We conclude that \(H \leq P\) and thus \(H \leq Q \cap P\).

Proof (of Theorem 6.2.7)

First we will prove \(G\) contains a subgroup of order \(p^e\) by induction on \(|G| = p^em\).

When \(|G| = 1\), \(\{e\}\) is a Sylow \(p\)-subgroup by our convention. In fact, this argument applies for whenever \(e = 0\), so we may thus assume through the rest of the proof that \(p\) does divide \(|G|\). So suppose that \(p\) divides \(|G|\) and every group of order \(n < |G|\) has a Sylow \(p\)-subgroup. We will consider two cases, depending on whether \(p\) divides \(|\mathrm{Z}(G)|\).

If \(p\) divides \(|\mathrm{Z}(G)|\), then by Cauchy’s Theorem there is an element \(z \in \mathrm{Z}(G)\) of order \(p\). Set \(N := \langle z \rangle\). Since \(z \in \mathrm{Z}(G)\), then for all \(g \in G\) we have

and thus \(N \trianglelefteq G\). Since

by induction hypothesis \(G/N\) has a subgroup of order \(p^{e-1}\), which must then have index \(m\). By the Lattice Isomorphism Theorem, this subgroup corresponds to a subgroup of \(G\) of index \(m\), hence of order \(p^e\).

Now assume \(p\) does not divide \(|\mathrm{Z}(G)|\), and consider the class equation for \(G\): \(g_1, \dots, g_k\) are a complete list of noncentral conjugacy class representatives, without repetition of any class, we have

Suppose that \(p\) divides \([G:C_G(g_i)]\) for all \(i\). Since \(p\) also divides \(|G|\), then this would imply that \(p\) divides \(|\mathrm{Z}(G)|\), but we assumed that \(p\) does not divide \(|\mathrm{Z}(G)|\). We conclude that \(p\) does not divide \([G:C_G(g_i)]\) for some \(i\).

Note that \([G:C_G(g_i)]\) divides \(|G|\) by Lagrange’s Theorem, and thus it must divide \(m\). Set

Then

and note that \(p\) does not divide \(d\) since it does not divide \(m\). Since \(g_i\) is not central, then \(e \notin C_G(g_i)\), and in particular \(|C_G(g_i)| < |G|\). By induction hypothesis, \(C_G(g_i)\) contains a subgroup \(S\) of order \(p^e\). But \(S\) is also a subgroup of \(G\), and it has order \(p^e\), as desired. This completes the proof of \((1)\): we have shown that \(G\) contains a subgroup of order \(p^e\).

To prove \((2)\) and \((3)\), let \(P\) be a Sylow \(p\)-subgroup and let \(Q\) be any \(p\)-subgroup. Let \(\mathcal{S}_P\) denote the collection of all conjugates of \(P\):

By definition, \(G\) acts transitively on \(\mathcal{S}_P\) by conjugation. Restricting that action to \(Q\), we get an action of \(Q\) on \(\mathcal{S}_P\), though note that we do now know if that action is transitive. The key to proving parts \((2)\) and \((3)\) of the Sylow Theorem is to analyze the action of \(Q\) on \(\mathcal{S}_P\).

Let \(\mathcal{O}_1, \dots, \mathcal{O}_s\) be the distinct orbits of the action of \(Q\) on \(\mathcal{S}_P\), and for each \(i\) pick a representative \(P_i \in O_i\). Note that

By the Orbit-Stabilizer Theorem, we have \(|\mathcal{O}_i| = [Q: Q \cap P_i]\), and thus, collecting the orbits,

This equation holds for any \(p\)-subgroup \(Q\) of \(G\). In particular, we can take \(Q = P_1\). In this case, the first term in the sum is \([Q: Q \cap P_i] = 1\) and, for all \(i \neq 1\) we have

But \(|Q|\) is a power of \(p\), so \([Q: Q \cap P_i]\) must be divisible by \(p\) for all \(i\). We conclude that

Note, however, that this does not yet prove part \((3)\), since we do not yet know that \(\mathcal{S}_P\) consists of {all} the Sylow \(p\)-subgroups. But we do have all the pieces we need to prove part (2). Suppose, by way of contradiction, that \(Q\) is a \(p\)-subgroup of \(G\) that is not contained in any of the subgroups in \(\mathcal{S}_P\). Then \(Q \cap P_i \neq Q\) for all \(i\), and thus every term on the right-hand side of

is divisible by \(p\), contrary to the equation above. We conclude that \(Q\) must be contained in at least one of the subgroups in \(\mathcal{S}_P\). This proves the first part of \((2)\).

Moreover, if we take \(Q\) to be a Sylow \(p\)-subgroup of \(G\), then \(Q \leq gPg^{-1}\) for some \(g\), but \(Q\) and \(P\) are both Sylow \(p\)-subgroups of \(G\), so

We conclude that \(Q = gPg^{-1}\) is conjugate to \(P\). In particular, the conjugation action of \(G\) on \(\mathrm{Syl}_p(G)\) is transitive, and this finishes the proof of \((2)\).

This proves, in particular, that \(\mathcal{S}_P\) in fact does consist of all Sylow \(p\)-subgroups, we can now also conclude part \((3)\) from \(\eqref{E1030b}\).

Finally, for any \(P \in \mathrm{Syl}_p(G)\), the stabilizer of \(P\) for the action of \(G\) on \(\mathrm{Syl}_p(G)\) by conjugation is \(N_G(P)\). Since we now know the action is transitive, the Orbit-Stabilizer Theorem says that

Moreover, since \(P \leq N_G(P)\) and \(|P| = p^e\), it follows that \(p\) divides \(|N_G(P)|\), so

for some \(d\) that divides \(m\). We conclude that

so \([G: N_G(P)]\) divides \(m\).

Proof (of Lemma 7.1.7)

By the exercise above, \[ |(1,1)|=\operatorname{lcm}(m,n)=mn. \] But \(\mathbb{Z}/m\times \mathbb{Z}/n\cong \mathbb{Z}/mn\) has order \(mn\), so \((1,1)\) is a generator for the group, which must then be cyclic. By the structure theory of finite cyclic groups, all cyclic groups of order \(mn\) are isomorphic to \(\mathbb{Z}/mn\), so \[ \mathbb{Z}/m\times \mathbb{Z}/n\cong \mathbb{Z}/mn. \]

Proof (of Theorem 7.1.10)

The hypothesis implies \(HK \leq G\). Moreover, consider any \(h \in H\) and any \(k \in K\). Since \(H\) is a normal subgroup, \[ khk^{-1} \in H, \textrm{ say } \] so also \[ [k,h]=khk^{-1}h^{-1}\in H. \] But \(K\) is also a normal subgroup, so similarly we obtain \[ [k,h]\in K. \] Therefore, \[ [k,h] \in H \cap K = \{ e \}, \] so \([k,h]= e\). We conclude that \[ hk = kh \quad \textrm{ for all } h\in H, k\in K. \]

The function \(\theta\) defined above must then satisfy \[ \begin{aligned} \theta((h_1, k_1) (h_2, k_2)) & = \theta(h_1h_2, k_1k_2) \\ & = (h_1h_2)(k_1k_2) \\ & = h_1(h_2k_1)k_2\\ & = (h_1k_1)(h_2k_2) \\ & = \theta(h_1, k_1) \theta(h_2, k_2) \end{aligned} \] and thus \(\theta\) is a homomorphism. Its kernel is \[ \ker(\theta) = \{(k,h) \mid k = h^{-1} \} = \{ (e,e) \} \] since \(H \cap K = \{e\}\). Moreover, \(\theta\) is surjective, as any element in \(HK\) is of the form \(hk \in HK\), and \[ \theta(h,k) = hk. \] This proves \(\theta\) is an isomorphism. Finally, restricting the codomain to any subgroup \(L\) of \(G\) and the domain to \(\theta^{-1}(L)\) gives an isomorphism between \(L\) and \(\theta^{-1}(L)\), so in particular \[ H \cong \theta^{-1}(H)=\{(h,e)\mid h\in H\}\leq H\times K \] and \[ K\cong \theta^{-1}(K)=\{(e,k)\mid k\in K\}\leq H\times K. \]

Proof (of Theorem 7.2.4)

First, we show that the operation is associative. Indeed, \[ \begin{aligned} (y_1,x_1) \left( (y_2, x_2) (y_3, x_3) \right) & = (y_1,x_1) (y_2\rho(x_2)(y_3), x_2x_3) \\ & = (y_1\rho(x_1)\left(y_2\rho(x_2)(y_3)\right), x_1x_2x_3)\\ & = (y_1\rho(x_1)(y_2)(\rho(x_1)\circ \rho(x_2))(y_3), x_1x_2x_3)\\ & = (y_1\rho(x_1)(y_2)\rho(x_1x_2)(y_3), x_1x_2x_3)\\ & = (y_1 \rho(x_1)(y_2), x_1 x_2) (y_3, x_3) \\ & = \left( (y_1,x_1) (y_2, x_2) \right) (y_3, x_3). \end{aligned} \] To show that \((e,e)\) is a two-sided identity, consider any \(h \in H\) and \(k \in K\). Since \(\rho(k)\) is a homomorphism, then \(\rho(k)(e) = e\), and thus \[ (h,k)(e,e) = (h\rho(k)(e),ke) = (he,ke) = (h,k). \] Moreover, since \(\rho\) is a homomorphism, \(\rho(e) = \mathrm{id}_H\), and thus \(\rho(e)(y) = \mathrm{id}_H(y)=y\) for any \(y \in K\), so that \[ (e,e)(h,k) = (e\rho(e)(h),ek) = (eh,ek)=(h,k). \] Finally, for any \(x \in H\) and \(y \in K\) we have \[ \begin{aligned} (x,y) (\rho(y^{-1})(x^{-1}), y^{-1}) &= (x \, \rho(y)\left(\rho(y^{-1})(x^{-1}) \right), yy^{-1})\\ & = (x (\rho(y) \circ \rho(y^{-1}))(x^{-1}), e) \\ &= (x \rho(e)(x^{-1}), e) & \textrm{since \(\rho\) is a homomorphism} \\ & = (xx^{-1},e) & \text{since } \rho(e) = \mathrm{id}_H\\ & =(e,e), \end{aligned} \] and similarly, \[ \begin{aligned} (\rho(y^{-1})(x^{-1}), y^{-1}) (x,y) &= (\rho(y^{-1})(x^{-1}) \rho(y^{-1})(x),y^{-1}y) \\ & = (\rho(y^{-1})(x^{-1}x), e) & \textrm{since } \rho(y^{-1}) \text{ is a homomorphism} \\ & = (\rho(y^{-1})(e), e) \\ & = (e, e) & \textrm{since } \rho(y^{-1}) \text{ is a homomorphism.} \end{aligned} \] Thus \((x,y)\) has an inverse, given by \[ (x,y)^{-1} = (\rho(y^{-1})(x^{-1}) ,y^{-1}). \] This completes the proof that the semidirect product is a group.

Proof (of Theorem 7.2.6)

Consider the function \(i\!: H \to H \rtimes_\rho K\) given by \[ i(y) = (y, e). \] Then \(i\) is a homomorphism: \[ i(y_1) i(y_2) = (y_1,e)(y_2,e) = (y_1\rho(e)(y_2) , ee) = (y_1 y_2, e) = i(y_1y_2). \] Moreover, \(i\) is injective by construction, and hence its image is isomorphic to \(H\) by the First Isomorphism Theorem. We can describe \(\mathrm{im}(i)\) as the set of all elements whose second component is \(e\). The image \(\mathrm{im}(i)\) is normal since the second component of \[ (h,k) (a, e) (h,k)^{-1} = (h,k) (a, e) (\rho(k^{-1})(h^{-1}), k^{-1}) \] is \[ kek^{-1} = e, \] which shows that any for any \((a,e) \in \mathrm{im}(H)\) and any \((h,k) \in H \rtimes_\rho K\), \[ (h,k) (a, e) (h,k)^{-1} \in \mathrm{im}(i). \] Let us write the image of \(i\), which we now know is a normal subgroup of \(H \rtimes_\rho K\), as \[ H' := \mathrm{im}(i) = \{(y,e) \mid y \in H\} \trianglelefteq H \rtimes_\rho K. \] Similarly, the function \[ j\!: K \to H \rtimes_\rho K \quad \text{given by } j(x) = (e,x) \] is also an injective homomorphism (exercise!), and thus its image \[ K' := \{(e,x) \mid x \in H \} \leq H \rtimes_\rho K \] is isomorphic to \(K\). Finally, given any \((h,k) \in H \rtimes_{\rho} K\), we can write \[ (h,k) = (h\rho(e)(e),k) = (h,e)(e,k) \in H'K', \] so \(H'K'= H \rtimes_\rho K\).

Consider the projection onto the second factor \[ \pi_2\!:H \rtimes_\rho K \to K, \] which is the map given by \[ \pi_2(x,y)=y. \] This is a group homomorphism, since the second component of \((x_1,y_1)(x_2,y_2)\) is \(y_1y_2\), and thus \[ \begin{aligned} \pi_2( (x_1,y_1)(x_2,y_2) ) = y_1y_2 = \pi_2(y_1) \pi_2(y_2). \end{aligned} \] Moreover, \(\pi_2\) is surjective by definition. Finally, \[ \ker(\pi_2)=\{(y,e_K)\mid y\in H\}=H'\cong H. \] By the First Isomorphism Theorem, we conclude that \[ (H \rtimes_\rho K )/ H' \cong K. \]

Proof (of Theorem 7.2.16)

First, we show that \(\theta\) is a group homomorphism. Indeed, \[ \begin{aligned} \theta((y_1, x_1) (y_2, x_2)) & = \theta(y_1 \rho(x_1)(y_2), x_1 x_2) \\ & = y_1(x_1y_2x_1^{-1}) x_1 x_2 \\ & = y_1x_1y_2x_2 \\ & = \theta(y_1, x_1) \theta(y_2, x_2). \end{aligned} \] Since \(H \cap K = \{e\}\), the kernel of \(\theta\) is \[ \ker(\theta) = \{(y,x) \in H \rtimes_{\rho} K \mid y = x^{-1} \} = \{ e \}. \] By construction, the image of \(\theta\) is \(HK\). Therefore, \(\theta\) induces an isomorphism onto \(HK\). Finally, \[ \theta^{-1}(H) = \{(h,e)\mid h\in H\} \quad \text{ and } \quad \theta^{-1}(K) = \{(e,k)\mid k\in K\}. \]

Proof (of Theorem 7.4.2)

Let \(G\) be a group of order \(pq\) and let \(n_q = |\mathrm{Syl}_q(G)|\). Since \(n_q \equiv 1 \pmod{q}\), \(n_q \mid p\), \(p\) is prime, and \(q > p\), we must have \(n_q = 1\). Thus, the unique Sylow \(q\)-subgroup \(H\) is a normal subgroup.¹

Now let \(K\) be a Sylow subgroup of order \(p\). Since \(H\) is normal, we know that \(HK\) is a subgroup of \(G\). By Lagrange's Theorem, \(|H\cap K|\) divides \(|H|\) and \(|H\cap K|\) divides \(|K|\). Therefore, \(H\cap K=\{e_G\}\). By an earlier exercise, \[ |HK| = \frac{|H||K|}{|H\cap K|} = \frac{q\cdot p}{1} = pq = |G| \] and so \(HK=G\). The recognition theorem for semidirect products thus yields that \[ G \cong H \rtimes_\rho K \] for some homomorphism \(\rho\!: K \longrightarrow \mathrm{Aut}(H)\). Note that \(H\) and \(K\) are cyclic, since they have prime order. Let us identify \(H\) with \(C_q = \langle x \mid x^q \rangle\) and \(K\) with \(C_p = \langle y \mid y^p \rangle\). Then \[ G \cong C_q \rtimes_\rho C_p \qquad \text{ for some homomorphism \(\rho: C_p \to \mathrm{Aut}(C_q)\).} \] We just need to classify all such semidirect products up to isomorphism. By the UMP of cyclic groups, the homomorphism \(\rho\!: C_p \longrightarrow \mathrm{Aut}(C_q)\) is uniquely determined by the image of the generator \(x\), which must be an element \(\alpha \in \mathrm{Aut}(C_q)\) with \(\alpha^p = \mathrm{id}\). Given such an \(\alpha\), we have \(\rho(y) = \alpha\) and more generally \(\rho(y^i) = \alpha^{i}\).

\(\mathrm{Aut}(C_q)\) is cyclic of order \(q-1\). On the other hand, \(\mathrm{im}(\rho)\) is a subgroup of both \(C_p\) and \(\mathrm{Aut}(C_q)\), so its order must divide both \(p\) and \(q-1\). In particular, there is a nontrivial automorphism \(\rho\) if and only if \(p \mid q-1\).

If \(p\) does not divide \(q-1\), then \(\rho\) is trivial, and by an earlier Lemma and the CRT we have \[ G \cong C_q \times C_q \cong C_{pq}. \]

If \(p\) does divide \(q-1\), there is at least one nontrivial \(\rho\). We still have \(G \cong C_{pq}\) if \(\rho\) is trivial. When \(\rho\) is nontrivial, \(G\) is not abelian, giving us at least two isomorphism classes. It remains to show that if \(\rho_1\) and \(\rho_2\) are any two nontrivial homomorphisms from \(C_p\) to \(\mathrm{Aut}(C_q)\), then the resulting semidirect products are isomorphic.

Since \(\mathrm{Aut}(C_q)\) is a cyclic group and \(p\) divides its order, it has a unique subgroup of order \(p\). Thus, we conclude that \(\mathrm{im}(\rho_1) = \mathrm{im}(\rho_2)\), so we have \[ C_q \rtimes_{\rho_1} C_p \cong C_q \rtimes_{\rho_2} C_p. \]

¹ Alternatively, \(H\) is normal since \([G:H]=p\) is the smallest prime that divides \(|G|\).

Proof of Lemma 8.1.6

1. Note that \[ a \cdot 0 = a \cdot (0+0) = a \cdot 0 + a \cdot 0. \] By subtracting \(a \cdot 0\) on both sides, we conclude that \[ a \cdot 0 = a \cdot (0+0) = 0. \] Analogously, \(0 \cdot a = 0\).

2. By distributivity, \[ ab + ({-}a)b = (a-a)b = 0 \cdot b = 0. \] Thus \(({-}a)b = -ab\). Analogously, \(a({-}b) = -ab\).

3. Applying the previous property twice, and noting that \(-(-x)=x\) by properties of group operations, we get \[ ({-}a)({-}b) = -(a({-}b)) = -(-ab) = ab. \]

4. Note that \((R, \cdot)\) is a monoid, and thus the identity \(1\) is unique, as is the case for groups.

5. We have \(({-}1)a = - 1 \cdot a = -a\).

Proof (of Lemma 8.2.10)

Suppose that \(a\) is both a zerodivisor and a unit. Then there exists \(b \neq 0\) such that \(ab=0\) or \(ba=0\). Multiplying either of these equations by \(a^{-1}\) gives \(b=0\), which is a contradiction.

Proof (of Corollary 8.2.14)

If \(R\) is a field, then every nonzero \(r \in R\) is a unit, and thus by Lemma 8.2.10 \(r\) is not a zerodivisor. Thus \(R\) has no zerodivisors, and must be a domain.

Proof (of Lemma 8.3.12)

We leave it as an exercise to prove that \(\mathbb{Q}(\sqrt{d})\) and \(\mathbb{Z}[\sqrt{d}]\) are closed under subtraction and products and contain \(1\), and thus are subrings of \(\mathbb{C}\) by the Subring Test (Exercise 8.3.2).

It remains to show that \(\mathbb{Q}(\sqrt{d})\) is a field, which amounts to the claim that it is closed under taking inverses of nonzero elements. Suppose \(r + q\sqrt{d} \neq 0\). Then its inverse in \(\mathbb{C}\) is \[ (r + q\sqrt{d})^{-1} = \frac{r - q\sqrt{d}}{r^2 - dq^2} \in \mathbb{Q}(\sqrt{d}). \] To see that this expression makes sense, note that if \(r^2 - dq^2 = 0\), then either \(r=q=0\) or \(d=(r/q)^2\). But \(r=q=0\) contradicts the assumption that \(r + q\sqrt{d} eq 0\), and \(d=(r/q)^2\) would make \(d\) a perfect square, contradicting that \(d\) is squarefree.

Proof (of Lemma 8.5.9)

By definition, \(f\) is a homomorphism of additive groups, and thus \(f(0_R) = 0_S\) and \(f(-x) = -f(x)\).

The fact that units are sent to units follows since \(f(1_R)=1_S\):

Hence \(f(u^{-1}) = f(u)^{-1}\).

To show that \(\mathrm{im}(f)\) is a subring, note \(1_S=f(1_R)\in\mathrm{im}(f)\). For \(a=f(x)\) and \(b=f(y)\) we have

Thus, by the Subring Test, \(\mathrm{im}(f)\) is a subring of \(S\).

The kernel \(\ker(f)\) is a subgroup under \(+\) and is closed under multiplication by all elements of \(R\): if \(a\in\ker(f)\) and \(r\in R\), then \(f(ra)=f(r)f(a)=f(r)\cdot0=0\), so \(ra\in\ker(f)\), and likewise \(ar\in\ker(f)\).

Finally, \(f\) is injective iff \(\ker(f)=\{0\}\) by the standard group-homomorphism argument.

Proof (of Theorem 8.6.1)

The main point is the well-definedness of the operation. Suppose \(r+I = r'+I\) and \(s+I = s'+I\). Then \(r = r' + a\) and \(s = s' + b\) for some \(a,b\in I\), and hence

Since \(I\) is a two-sided ideal, \(r'b\), \(as'\), and \(ab\) all belong to \(I\), and so does their sum. It follows that \(rs + I = r's' + I\), proving that the operation is well-defined.

To show that \(R/I\) is a ring, note that it is already an abelian group under addition. Associativity of multiplication follows from that in \(R\). Moreover, \(1+I\) acts as a multiplicative identity since \(1\) does in \(R\), and the distributive laws descend directly from those in \(R\).

Finally, \(\pi(1)=1+I\) by definition, and \(\pi\) preserves products by construction, hence \(\pi\) is a ring homomorphism.

Proof (of Theorem 8.7.1)

Ignoring the multiplication operation, we already know from \Cref{UMP quotient group} that there is a unique group homomorphism \(\overline{f}\) of abelian groups from \((R/I, +)\) to \((S, +)\) such that \(\overline{f} \circ \pi = f\). It remains only to check that \(\overline{f}\) preserves multiplication and sends \(1\) to \(1\). Given elements \(r + I, s + I \in R/I\), we have

since \(f\) preserves multiplication. Finally,

since \(f\) sends \(1_R\) to \(1_S\).

Proof (of Theorem 8.7.2)

Taking \(I = \ker(f)\) in the UMP for quotient rings, we have a ring homomorphism \(\overline{f}: R/\ker(f) \to S\). By the formula for \(\overline{f}\) we immediately get that \(\mathrm{im}(\overline{f}) = \mathrm{im}(f)\). Its kernel is

and hence \(\overline{f}\) is injective. The result follows.

Proof (of Theorem 8.7.6)

The first two facts are the exercise above. The map \(f\!: S+I \to \frac{S}{S\cap I}\) sending \(s+i\) to \(s+i+I = s+I\) is a homomorphism of rings since it is the composition of a subring inclusion with the canonical quotient map. It is surjective by definition, and the kernel is

The result now follows from the First Isomorphism Theorem for rings.

Proof (of Theorem 8.7.7)

If we ignore multiplication, we know that \((J/I,+)\) is a subgroup of \((R/I,+)\) and that there is an isomorphism of abelian groups

given by

One just needs to check that \(J/I\) is a two-sided ideal of \(R/I\) and the indicated bijection preserves multiplication, which we leave as an elementary exercise.

Proof (of Theorem 8.7.11)

By the Lattice Isomorphism Theorem, we know that there is a bijection of subgroups (under \(+\)) of \(R\) that contain \(I\) and subgroups of \(R/I\), given by these formulas. It remains to pprove that this correspondence preserves the property of being an ideal, which we leave as an exercise.

Proof (of Theorem 8.8.4)

By the Lattice Isomorphism Theorem, the ideals of \(R/Q\) are of the form \(I/Q\), where \(I\) is an ideal in \(R\) containing \(Q\).

By earlier work, \(R/Q\) is a field if and only if \(R/Q\) has only two ideals, \(\{ 0 \} = Q/Q\) and \(R/Q\). Thus \(R/Q\) is a field if and only if the only ideals that contain \(Q\) are \(Q\) and \(R\).

Now suppose \(Q\) is prime. If \[ (r + I)(r' + I) = 0 + I, \] then \(rr' \in I\) and hence either \(r \in I\) or \(r' \in I\), so that either \[ r + I = 0 \quad \text{or} \quad r'+ I = 0. \] Since \(R\) is commutative, then \(R/I\) is also commutative, and since \(Q\) is a proper, then \(R/I\) is not the zero ring. This proves that \(R/Q\) is a domain.

Conversely, suppose that \(R/Q\) is a domain. Since \(R/Q\) is not the zero ring, \(Q\) is proper. If \(x,y \in R\) satisfy \(xy \in I\), then \[ (x + I)(y + I) = 0 \] in \(R/Q\), and hence either \(x+ Q = 0\) or \(y + Q = 0\). It follows \(x \in Q\) or \(y \in Q\). This proves that \(Q\) is prime.

If \(Q\) is maximal, then \(R/Q\) is a field, which in particular implies that \(R/Q\) is a domain, and thus \(Q\) is prime.