Let \(S \subseteq G\). The subgroup generated by \(S\) is
\[ \langle S \rangle = \bigcap \{H \le G : S \subseteq H\}. \]The collection over which intersection is being taken is nonempty because \(G\) itself contains \(S\). Therefore the intersection is a subgroup. It contains \(S\), and if \(K \le G\) contains \(S\), then \(\langle S \rangle \subseteq K\). Thus \(\langle S \rangle\) is the unique smallest subgroup of \(G\) containing \(S\).
If \(X = \{1, \dots, n\}\), the group \(\text{Sym}(X)\) of bijections from \(X\) to \(X\) is denoted by \(S_{n}\).
Each element of \(S_{n}\) is a permutation and is determined by the ordered list of its \(n\) distinct values. There are \(n\) choices for \(\sigma(1)\), then \(n-1\) for \(\sigma(2)\), and so on. Hence \(|S_{n}| = n!\). We compose permutations as functions: in \(\sigma\tau\), the permutation \(\tau\) acts first.
Let \(\sigma \in S_{n}\) and let \(i \in \{1, \dots, n\}\). We say that \(\sigma\) fixes \(i\) if \(\sigma(i) = i\). In this case, \(i\) is called a fixed point of \(\sigma\). We say that \(\sigma\) moves \(i\) if \(\sigma(i) \ne i\).
Let \(1 \le k \le n\), and let \(i_{1}, i_{2}, \dots, i_{k}\) be distinct elements of \(\{1, \dots, n\}\). A permutation \(\sigma \in S_{n}\) is called a \(k\)-cycle, or a cycle of length \(k\), if
\[ \sigma(i_{1}) = i_{2}, \quad \sigma(i_{2}) = i_{3}, \quad \dots \quad \sigma(i_{k-1}) = i_{k}, \quad \sigma(i_{k}) = i_{1} \]and \(\sigma\) fixes every element of \(\{1, \dots, n\} \setminus \{i_{1}, \dots, i_{k}\}\). We denote this permutation by \(\sigma = (i_{1} \, i_{2} \, \dots \, i_{k})\).
Thus a \(k\)-cycle moves exactly the \(k\) elements \(i_{1}, \dots, i_{k}\) and fixes all the remaining elements of \(\{1, \dots, n\}\). A 2-cycle \((i \, j)\) is called a transposition.
- Let \(\sigma = (1 \, 2)\) and \(\tau = (2 \, 3) \in S_{3}\). Computing the image of each of \(1, 2, 3\) gives \[ \sigma\tau = (1 \, 2 \, 3), \quad \tau\sigma = (1 \, 3 \, 2). \] Since these permutations are different, \(S_{3}\) is nonabelian.
- Consider the permutation \(\sigma = (1 \, 3 \, 5) \in S_{5}\). Then \[ \sigma(1) = 3, \quad \sigma(3) = 5, \quad \sigma(5) = 1, \] while \(\sigma(2) = 2, \, \sigma(4) = 4\). Thus \(\sigma\) moves exactly the elements \(1, 3, 5\) and fixes \(2\) and \(4\). Hence \(\sigma\) is a \(3\)-cycle in \(S_{5}\).
- Consider \(\tau = (1 \, 2)(3 \, 4) \in S_{5}\). Then \[ \tau(1) = 2, \quad \tau(2) = 1, \quad \tau(3) = 4, \quad \tau(4) = 3, \quad \tau(5) = 5. \] Thus \(\tau\) moves the four elements \(1, 2, 3, 4\), but it does not move them in a single cycle: the elements \(1, 2\) are permuted among themselves, and the elements \(3, 4\) are permuted among themselves. Therefore \(\tau\) is not a cycle.
A map \(T : \mathbb{R}^{2} \longrightarrow \mathbb{R}^{2}\) is called a Euclidean isometry if it preserves Euclidean distances; that is,
\[ ||T(x) - T(y)|| = ||x - y|| \]for all \(x, y \in \mathbb{R}^{2}\).
For \(n \ge 3\), the dihedral group \(D_{n}\) is the group of Euclidean isometries of the plane that map a fixed regular \(n\)-gon onto itself, with composition as the operation. We use the convention
\[ |D_{n}| = 2n. \]Because the composite of two symmetries is a symmetry, the identity is a symmetry, and the inverse of a symmetry is again a symmetry, the set is a group under composition; associativity is inherited from function composition.
Let \(r\) be counterclockwise rotation through \(2\pi/n\), and let \(s\) be a reflection in a fixed symmetry axis. A symmetry is determined by the image of one chosen vertex and by the choice of which adjacent vertex follows it in the positive or negative orientation. There are \(n\) choices for the first image and two choices of orientation, hence exactly \(2n\) symmetries. They are
The basic relations are
\[ r^{n} = e, \quad s^{2} = e, \quad srs = r^{-1}. \]Multiplying the last equality on the right by \(s\) gives \(sr = r^{-1}s\). This relation says algebraically that reflection reverses the direction of a rotation.
For the square, \(D_{4} = \{e, r, r^{2}, r^{3}, s, sr, sr^{2}, sr^{3}\}\). Since \(r^{-1} = r^{3} \ne r\),
\[ sr = r^{-1}s = r^{3}s \ne rs. \]Thus \(D_{4}\) is nonabelian.
Some authors denote the symmetry group of a regular \(n\)-gon by \(D_{2n}\), recording the order of the group rather than the number of vertices. The convention should therefore always be stated.
Label the vertices of an equilateral triangle by \(1,2,3\). Every symmetry of the triangle permutes the vertices, so define \(\Phi : D_{3} \rightarrow S_{3}\) by letting \(\Phi(T)\) be the permutation induced by the symmetry \(T\). Because applying \(T_{2}\) and then \(T_{1}\) induces the composite permutation, \(\Phi(T_{1}T_{2}) = \Phi(T_{1})\Phi(T_{2})\), so \(\Phi\) is a homomorphism. If two symmetries induce the same permutation of all three vertices, then they agree on three noncollinear points and hence are the same Euclidean isometry; thus \(\Phi\) is injective. Both groups have six elements, so an injective map between them is bijective. Hence \(D_{3} \cong S_{3}\).
- The rotations of a regular \(n\)-gon form the subset \(\langle r \rangle = \{e, r, \dots, r^{n-1}\} \subseteq D_{n}\). If \(r^{a}\), \(r^{b}\) are rotations, then \(r^{a}(r^{b})^{-1} = r^{a-b}\) is again a rotation, so this set is a subgroup of \(D_{n}\).
- The dihedral group satisfies \(D_{n} = \langle r, s \rangle\). The relation \(sr = r^{-1}s\) implies by induction that \(sr^{k} = r^{-k}s\) for every integer \(k\). Hence any word in \(r^{\pm 1}\) and \(s\) can be moved into one of the normal forms \(r^{k}\) or \(sr^{k}\). Reducing \(k\) modulo \(n\) gives exactly the \(2n\) elements listed earlier.
Consider the square with vertices \(v_{1} = (1,1)\), \(v_{2} = (-1,1)\), \(v_{3} = (-1,-1)\), \(v_{4} = (1,-1)\) labelled cyclically. The dihedral group \(D_{4}\) consists of the Euclidean isometries of \(\mathbb{R}^{2}\) that map this square onto itself. Every such isometry permutes the four vertices, and hence determines an element of \(S_{4}\). Thus we may regard \(D_{4}\) as a subgroup of \(S_{4}\). Consider the transposition \(\sigma = (1 \, 2) \in S_{4}\). Suppose, for contradiction, that \(\sigma\) is induced by an element \(T \in D_{4}\). Then
\[ T(v_{1}) = v_{2}, \quad T(v_{2}) = v_{1}, \quad T(v_{3}) = v_{3}, \quad T(v_{4}) = v_{4}. \]Since \(T\) is a Euclidean isometry, it must preserve the distance between \(v_{1}\) and \(v_{3}\). We have
\[ ||v_{1} - v_{3}|| = \sqrt{(1-(-1))^{2} + (1-(-1))^{2}} = 2\sqrt{2}. \]On the other hand,
\[ ||T(v_{1}) - T(v_{3})|| = ||v_{2} - v_{3}|| = \sqrt{((-1)-(-1))^{2} + (1-(-1))^{2}} = 2. \]Therefore \(||T(v_{1}) - T(v_{3})|| \ne ||v_{1} - v_{3}||\), contradicting the fact that \(T\) is a Euclidean isometry. Hence no Euclidean isometry of the square induces the permutation \((1 \, 2)\). Therefore \((1 \, 2) \notin D_{4}\).
Every nonempty subset of \(\mathbb{Z}_{>0}\) has a least element.
Let \(G = \langle g \rangle\) be a cyclic group. Then every subgroup \(H \le G\) is cyclic.
Proof: Let \(H \le G\). If \(H = \{e\}\), then \(H = \langle e \rangle\), so \(H\) is cyclic. Now suppose that \(H \ne \{e\}\). Since \(G = \langle g \rangle\), every element of \(G\) is of the form \(g^{m}\) for some \(m \in \mathbb{Z}\). Hence \(H\) contains some nonidentity element \(g^{m}\) where \(m \ne 0\).
If \(m < 0\), then \(g^{-m} = (g^{m})^{-1} \in H\), and \(-m > 0\). Therefore the set
is nonempty. By the well-ordering principle, \(S\) has a least element. Let \(d = \min S\). Thus \(d > 0\) and \(g^{d} \in H\).
We claim that \(H = \langle g^{d} \rangle\). Since \(g^{d} \in H\) and \(H\) is a subgroup, \(H\) contains every integral power of \(g^{d}\). Hence \(\langle g^{d} \rangle \subseteq H\).
Conversely, let \(h \in H\). Since \(G = \langle g \rangle\), there exists \(m \in \mathbb{Z}\) such that \(h = g^{m}\). By the division algorithm, there exist integers \(q\) and \(r\) such that
Since \(g^{m} \in H\) and \(g^{d} \in H\), we have \((g^{d})^{-q} \in H\). Therefore
\[ g^{r} = g^{m - qd} = g^{m}(g^{d})^{-q} \in H. \]If \(r > 0\), then \(r \in S\), but \(0 < r < d\), contradicting the minimality of \(d\). Hence \(r = 0\). Thus \(m = qd\), and therefore
\[ h = g^{m} = g^{qd} = (g^{d})^{q} \in \langle g^{d} \rangle. \]Since \(h \in H\) was arbitrary, \(H \subseteq \langle g^{d} \rangle\). Consequently, \(H = \langle g^{d} \rangle\), and hence \(H\) is cyclic. ∎
Every subgroup of \((\mathbb{Z}, +)\) has the form \(d\mathbb{Z}\) for a unique integer \(d \ge 0\).