Let \(X\) be a nonempty set. A partition of \(X\) is a collection \(\mathcal{P}\) of nonempty subsets of \(X\) such that
- \(\bigcup_{A \in \mathcal{P}} A = X\);
- if \(A, B \in \mathcal{P}\) and \(A \ne B\), then \(A \cap B = \emptyset\).
In other words, every element of \(X\) belongs to exactly one subset in \(\mathcal{P}\).
A relation on a set \(X\) is a subset \(R \subseteq X \times X\). We write \(x \sim y\) to mean \((x,y) \in R\).
An equivalence relation on \(X\) is a relation \(\sim\) that is:
- Reflexive: \(x \sim x\) for all \(x \in X\).
- Symmetric: if \(x \sim y\) then \(y \sim x\), for all \(x, y \in X\).
- Transitive: if \(x \sim y\) and \(y \sim z\), then \(x \sim z\), for all \(x, y, z \in X\).
Let \(\sim\) be an equivalence relation on \(X\). For each \(x \in X\), the equivalence class of \(x\) is
\[ [x] = \{y \in X : y \sim x\}. \]Let \(X\) be a nonempty set.
- If \(\sim\) is an equivalence relation on \(X\), then the set of equivalence classes of \(\sim\) forms a partition of \(X\).
- Conversely, if \(\mathcal{P}\) is a partition of \(X\), then the relation \(\sim\) defined by \(x \sim y \Leftrightarrow x\) and \(y\) belong to the same subset in \(\mathcal{P}\) is an equivalence relation on \(X\), and its equivalence classes are exactly the subsets in \(\mathcal{P}\).
Proof of (1): Let \(\mathcal{E} = \{[x] : x \in X\}\). By reflexivity, \(x \in [x]\) for every \(x \in X\). Hence each equivalence class is nonempty and their union is \(X\). We must show that any two equivalence classes are either equal or disjoint. Suppose \([x] \cap [y] \ne \emptyset\). Let \(z \in [x] \cap [y]\). Then \(z \sim x\) and \(z \sim y\). By symmetry, \(x \sim z\). For any \(w \in [x]\), we have \(w \sim x\). By transitivity, \(w \sim x\) and \(x \sim z \Rightarrow w \sim z\). Then \(w \sim z\) and \(z \sim y \Rightarrow w \sim y\), so \(w \in [y]\). Thus \([x] \subseteq [y]\). The reverse inclusion is proved similarly. Hence \([x] = [y]\). ∎
Let \(G\) be a group and \(H \le G\) a subgroup.
Define a relation \(\sim_{L}\) on \(G\) by
\[ x \sim_{L} y \iff x^{-1}y \in H. \]The relation \(\sim_{L}\) is an equivalence relation on \(G\).
Proof:
- Reflexivity: For any \(x \in G\), \(x^{-1}x = e \in H\), so \(x \sim_{L} x\).
- Symmetry: Suppose \(x \sim_{L} y\). Then \(x^{-1}y \in H\). Since \(H\) is a subgroup, it contains the inverse of each of its elements. Thus \((x^{-1}y)^{-1} \in H\). But \((x^{-1}y)^{-1} = y^{-1}(x^{-1})^{-1} = y^{-1}x\). Therefore \(y^{-1}x \in H\), which means \(y \sim_{L} x\).
- Transitivity: Suppose \(x \sim_{L} y\) and \(y \sim_{L} z\). Then \(x^{-1}y \in H\) and \(y^{-1}z \in H\). Since \(H\) is a subgroup, it is closed under multiplication, so \((x^{-1}y)(y^{-1}z) \in H\). But \((x^{-1}y)(y^{-1}z) = x^{-1}(yy^{-1})z = x^{-1}ez = x^{-1}z\). Thus \(x^{-1}z \in H\), so \(x \sim_{L} z\). ∎
For \(x \in G\), define the left coset of \(H\) containing \(x\) to be
\[ xH = \{xh : h \in H\}. \]For each \(x \in G\), the equivalence class of \(x\) under \(\sim_{L}\) is exactly the left coset \(xH\).
Proof: Let \([x]\) denote the equivalence class of \(x\). If \(y \in [x]\), then \(x \sim_{L} y\), which means \(x^{-1}y \in H\). Let \(h = x^{-1}y\). Then \(h \in H\) and \(x(x^{-1}y) = xh\), which simplifies to \(y = xh\). Hence \(y \in xH\). This shows \([x] \subseteq xH\).
Conversely, if \(y \in xH\), then \(y = xh\) for some \(h \in H\). Therefore \(x^{-1}y = x^{-1}(xh) = (x^{-1}x)h = eh = h \in H\). This means \(x \sim_{L} y\), so \(y \in [x]\). This shows \(xH \subseteq [x]\). ∎
Consequently, the left cosets of \(H\) in \(G\) form a partition of \(G\). Two left cosets \(xH\) and \(yH\) are either identical (if \(x^{-1}y \in H\)) or disjoint.
The index of \(H\) in \(G\), denoted by \([G : H]\), is the number of distinct left cosets of \(H\) in \(G\).
For any \(x \in G\), the map \(f : H \rightarrow xH\) defined by \(f(h) = xh\) is a bijection. Consequently, \(|xH| = |H|\).
Proof: The map \(f\) is surjective by the definition of \(xH\). Suppose \(f(h_{1}) = f(h_{2})\). Then \(xh_{1} = xh_{2}\). By left cancellation in \(G\), \(h_{1} = h_{2}\). Thus \(f\) is injective. ∎
Let \(G\) be a finite group and \(H \le G\). Then
\[ |G| = [G : H] \cdot |H|. \]In particular, the order of any subgroup \(H\) divides the order of \(G\).
Proof: The left cosets of \(H\) form a partition of \(G\). There are exactly \([G : H]\) such cosets, and each contains exactly \(|H|\) elements. The total number of elements in \(G\) is therefore \([G : H] \cdot |H|\). ∎
If \(G\) is a finite group and \(x \in G\), then the order of the subgroup \(\langle x \rangle\) divides \(|G|\).
Every group of prime order is cyclic.
Proof: Let \(|G| = p\), a prime. Let \(x \in G\) with \(x \ne e\). The order of the subgroup \(\langle x \rangle\) must divide \(p\). Since \(p\) is prime and \(x \ne e\) implies \(|\langle x \rangle| > 1\), we must have \(|\langle x \rangle| = p\). Therefore \(\langle x \rangle = G\). ∎
For \(x \in G\) and \(H \le G\), define the right coset
\[ Hx = \{hx : h \in H\}. \]In general, a left coset \(xH\) need not equal the right coset \(Hx\).
A subgroup \(N \le G\) is called a normal subgroup if
\[ xNx^{-1} = N \]for all \(x \in G\), where \(xNx^{-1} = \{xnx^{-1} : n \in N\}\). We denote this by \(N \trianglelefteq G\).