Lecture 14: Lagrange's Theorem, Order Theorem & Equivalence Relations
Last time, we studied Lagrange’s Theorem which stated that given a finite group \(G\) and a subgroup \(H\) of \(G\), then \(|H|\) divides \(|G|\). Moreover, \(|H| / |G|\) is the number of \(H-\) left cosets in \(G\). In fact, this number was defined to be the index of a group \([G : H]\). So
As a consequence, this led to the Order Theorem which stated that if \(G\) was a finite group, then for any \(g \in G\), \(o(g)\) divides \(|G|\).
But now as we see, both theorems are stated for finite groups \(G\) and we know from last lecture that the index of a group can be still defined even if \(G\) is infinite. So this led to the generalized version of Lagrange Theorem as follows:
Note here that if \(K\) is the trivial subgroup so \(K = \{e\}\), then \([H:\{e\}] = |H|\). The cosets of the trivial subgroups have size 1 so we’re dividing \(H\) isto subsets of size 1 and therefore we get back the earlier Lagrange’s Theorem
Example
Suppose we have \(\mathbf{Z} \geq \mathbf{Z_3} \geq \mathbf{Z}_{12}\) where \(G = \mathbf{Z}\), \(H = \mathbf{Z}_{3}\) and \(K = \mathbf{Z}_{12}\). We know that \([\mathbf{Z} : \mathbf{Z}_{12}] = 12\) and \([\mathbf{Z} : \mathbf{Z}_{3}] = 3\) so
From this we can deduce that the index of \(\mathbf{Z}_{12}\) inside \(\mathbf{Z}_3\) is 4.
Proof of Generalized Lagrange
\([H: K]\) is the number of left \(K\)-cosets inside \(H\). So \(aK \subseteq H\). Observe that for any \(aH\), the number of left \(K\)-cosets in \(aH\) is equal to \([H : K]\). Consider the bijection
Then \(hk\) under this bijection will be \(ahK\).
Example
Let \(D_4 = \{e, r, r^2, r^3, j, rj, r^2j, r^3j\}\). Consider:
Then the index \([G : H] = \frac{|H|}{|G|} = 2\) which is the number of \(H\)-left cosets in \(G\). Similarly, \([H : K] = 2\) which is the number of \(K-\) left cosets in \(H\). For example
If you look at \(eH\), observe that it contains both \(K\)-cosets and if you look at \(rH\), you’ll see that it also contains both of the \(K\) cosets.
Order Theorem
Back to the Order Theorem. For example, for \(|G| = 12\), the order of the elements inside \(G\) are \(o(g) \in \{1,2,3,4,6,12\}\). The question is do we know if there must be a subgroup of order 6? 4? what about 2? For 2, if the order of the group is even, then we must have an element with order 2. To see why, we have the Even Order Theorem as follows:
Proof
Observe that if \(a \in G\), then \(a^2 = 2\) if and only if \(a^{-1} = a\). In this case, the order must either be 1 or 2 so \(o(a) \in \{1,2\}\). Now, let \(a \in G\). For each \(a\), produce a subset \(C\) such that \(C = \{a, a^{-1}\}\). This is a subset of \(G\) of order 1 or 2 depending on whether \(a = a^{-1}\).
Claim: For \(\{a, a^{-1}\}\) and \(C' = \{b, b^{-1}\}\). Either \(C = C'\) or \(C \cap C' = \emptyset\). Moreover
The union of all these subsets is \(G\). So we get a partition of the set \(G\) into pairwise disjoint subsets of size 1 or 2. So \(n = |G| = r + 2s\). where \(r\) is the number of subsets \(\{a, a^{-1}\}\) of size 1 and \(s\) is the number of subsets \(\{a, a^{-1}\}\) of size \(2\). Notice here that \(r\) is counting all the elements such that each element is its own inverse. So \(r = |\{a \in G \ | \ a^2 = e\}|\). In fact, \(r\) is the number of elements in \(G\) of order 1 or 2.
So we showed that \(n = |G| = r + 2s\) but by assumption, \(n\) is even and since it’s even then 2 divides \(n\). So 2 must divide \(r + 2s\). Therefore, \(2\) must divide \(r\). So \(r\) is even. We also know that \(r\) is at least 1 because the identity element has order 1. Therefore, there must exist at least another element whose order is 2. So there exists a \(g \in G\) such that \(o(g) = 2\). \(\ \blacksquare\).
There is a generalization of this theorem that we’ll prove later. But if \(p\) is prime and it divides \(|G|\), then there exists an element of order \(p\).
Equivalence Relations
Review of equivalence relations
For example, let \(X = \mathbf{Z}\), then examples of relations are \(=, >, \geq, \leq, < ...\), “coprime”, \(\equiv \bmod n\) and so on.
- Reflexive: \(a \sim a \ \forall a \in X\).
- Symmetric: \(a \sim b \implies b \sim a \ \forall a, b \in X\).
- Transitive: \(a \sim b, b \sim c \implies a \sim c \ \forall a, b, c \in X\).
Given a set \(X\) with an equivalence relation \(\sim\), we have an equivalence class which is a subset of \(X\) of the form
Fact: Either \([a] = [b]\) or \([a] \cap [b] = \emptyset\) so \([a] = [b] \implies a \sim b\).
So this equivalence relations gives us a way to partition a given set \(X\) into pairwise disjoint nonempty subsets. In fact we have a bijection between the equivalence relation on \(X\) and the partitions of \(X\). What does this mean? It means that we can go either direction, if we have an equivalence relation, we can get a partition of \(X\) into subsets. And if we have a set of disjoint subsets that partitions \(X\), then we can get an equivalence relation from that. How? any two elements will be in the same equivalence class if they’re in the same subset. So we’re kind of talking about the same thing here.
So now let \((X, \sim)\) be a set with equivalence relation. Define \(Y\) as the set of equivalence classes of \(\sim\). We sometimes denotes \(Y\) with \(X / \sim\) “quotient set of equivalence relation”. Define
\(\pi\) is quotient function. \(\pi\) is surjective. Every equivalence class, has an element \(a\) that is in the set \(X\) by definition. So now given \(\pi\), we can recover the equivalence relation.
References
- MATH417 by Charles Rezk
- Algebra: Abstract and Concrete by Frederick M. Goodman