In today's blog, I review the proof for Lagrange's Theorem. The theorem is named after Joseph-Louis Lagrange who first stated it. The first complete proof came 30 years later.
In today's blog, I also use the concept of order, subgroup, and coset. The concept of the coset was first proposed by Evariste Galois. The term "coset" was coined by G. A. Miller in 1910.
The content of today's blog is taken from Joseph A. Gallian's Contemporary Abstract Algebra.
Definition 1: Order of a Group
The number of elements of a group.
NOTE: If you need to review the definition of the group, see here.
Definition 2: Subgroup
If H is a subset of a group G and H is a group itself under the operation of G, then H is a subgroup of G.
Definition 3: Coset of H in G
Let G be a group and H a subgroup of G. For any a ∈ G, the set aH { ah : h ∈ H } is called the left coset of H in G containing a. The set Ha { ha : h ∈ H } is called the right coset of H in G containing a.
NOTE: An important idea behind the coset is that it is a distinct partition of elements (see Lemma 2 below). From the property of closure, we know that if two values are elements of a group, then their product (by this, I mean the result of the group operation) is also an element of the group.
From this, we know that the set of cosets can be divided up as follows: a1H, a2H, ..., arH where r is a positive integer and where for each coset i ≠ j → aiH ∩ ajH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]
Example 1 Coset: Z9
Let G = Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'
NOTE: Z9 is the set of integers modulo 9 [See here for a review of modular arithmetic]
Let H = { 0, 3, 6 } with operation '+'
We can see that H is a subgroup of G
The left coset in this case is a+H (note it would aH is the operation were '*')
Here are the cosets:
0 + H = { 0, 3, 6 } = 3 + H = 6 + H
1 + H = { 1, 4, 7 } = 4 + H = 7 + H
2 + H = {2, 5, 8} = 5 + H = 8 + H
We can see that all cosets are either equal or distinct. I present a proof of this in Lemma 2 below.
Example 2: Even integers
Let Z be the set of integers
Then 2Z is a left coset which includes { ..., 0, 2, 4 , 6, ... }
Lemma 1: aH = H if and only if a ∈ H
Proof:
(1) Assume aH = H
(2) Then, a = ae ∈ aH = H
(3) Assume a ∈ H
(4) aH ⊆ H since h ∈ H → ah ∈ H [By property of closure, see here if needed]
(5) H ⊆ aH since:
(a) Let h be any element of H.
(b) a-1 ∈ H since a ∈ H [By the inverse property, see here if needed]
(c) a-1H ∈ H [By property of closure, see here if needed]
(d) So h = eh = (aa-1)h = a(a-1h) [By identity property, inverse property, and associative property, see here if needed]
(e) But a(a-1h) ∈ aH so that from (#5d), h ∈ aH.
(6) So H = aH since H ⊆ aH and aH ⊆ H.
QED
Lemma 2: if aH, bH are two cosets, then aH = bH or aH ∩ bH = ∅
Proof:
(1) Assume that aH ∩ bH ≠ ∅
(2) Let x ∈ aH ∩ bH since aH ∩ bH ≠ ∅
(3) Then there exists h1, h2 such that:
x = ah1
x= bh2
Since x is found in both aH and bH by assumption.
(4) Thus, a = xh1-1 = (bh2)h1-1
(5) From this, aH = [(bh2)h1-1]H = b(h2h1-1H) = bH [By Lemma 1 above]
QED
Theorem: Lagrange's Theorem
If G is a finite group and H is a subgroup of G, then the order of H divides the order of G.
Proof:
(1) Let a1H, a2H, ..., arH denote the distinct left cosets of H in G. [See Definition 3 above for details on left cosets of H in G.]
NOTE: If two cosets are equal then we only count them once.
(2) For each a ∈ G, we have aH = aiH for some i by our construction in step #1.
(3) a ∈ aH since:
a = ae and ae ∈ aH since H is a subgroup. [See Definition 2 above for details on subgroups]
(4) Thus, each member of G belongs to one of the cosets aiH [from step #2 and step #3.]
(5) G = a1H ∪ a2H ∪ ... ∪ arH [This follows directly from step #4]
(6) From Lemma 2 above, we know aiH = ajH or aiH ∩ ajH = ∅ and since each ai is distinct, we get:
order(G) = order(a1H) + order(a2H) + ... + order(arH)
(7) Since order(aiH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:
order (G) = r*order(H)
QED
