Group Theory: Lagrange's Theorem

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: a₁H, a₂H, ..., a_rH where r is a positive integer and where for each coset i ≠ j → a_iH ∩ a_jH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]

Example 1 Coset: Z₉

Let G = Z₉ = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'

NOTE: Z₉ 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 h₁, h₂ such that:

x = ah₁
x= bh₂

Since x is found in both aH and bH by assumption.

(4) Thus, a = xh₁^-1 = (bh₂)h₁^-1

(5) From this, aH = [(bh₂)h₁^-1]H = b(h₂h₁^-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 a₁H, a₂H, ..., a_rH 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 = a_iH 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 a_iH [from step #2 and step #3.]

(5) G = a₁H ∪ a₂H ∪ ... ∪ a_rH [This follows directly from step #4]

(6) From Lemma 2 above, we know a_iH = a_jH or a_iH ∩ a_jH = ∅ and since each a_i is distinct, we get:

order(G) = order(a₁H) + order(a₂H) + ... + order(a_rH)

(7) Since order(a_iH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:

order (G) = r*order(H)

QED