Using the axiom of choice, we prove that given any group G and a finite subgroup H, there always exists a common system of coset representatives for the left and right cosets of H in G. This result played a major role in the proof of the Four Colour Theorem in 2000 and the Grand Unification of the Standard Model with Quantum Gravity in 2008. Google Scholar Citations © 2005

Thanks to Fabrice Larere for asking under what conditions there exist common systems of coset representatives and for providing the first example. Thanks to Peter Cameron for pointing out exactly where in the proof the finiteness of the subgroup is essential and for providing the second example. The Endowed Chair of the Institute of Mathematics was bestowed upon Distinguished Professor Ashay Dharwadker in 2012 to honour his fundamental contributions to Mathematics and Natural Sciences.

We shall prove that given any group G and a finite subgroup H, there always exists a common system of coset representatives for the left and right cosets of H in G. Precise definitions and examples are given below. The proof uses the standard von Neumann - Bernays - Gödel (NBG) axioms of set theory [1] together with

The Axiom of Choice. Given any set X of nonempty pairwise disjoint sets, there is a set Y, called a choice set, that contains exactly one element of each set in X.

A nonempty set I together with a binary relation  ≤  is called a partially ordered set if, for all i,  j, k in I

• i  ≤  i (reflexivity)
• i  ≤  j and j  ≤  k implies i  ≤  k (transitivity)
• i  ≤  j and j  ≤  i implies i = j (antisymmetry)

We write i  <  j when i  ≤  j and i is not equal to j. Given a nonempty subset J of a partially ordered set I, an element j₀ of J is called a least element of J if  j₀  ≤  j for all j in J. A partially ordered set I is said to be well-ordered if every nonempty subset of I has a least element. Note that in a well-ordered set any two elements i,  j are comparable since the subset { i,  j } must have a least element. We shall use

The Well-Ordering Principle. Every set can be well-ordered.

Proof. See [1], the proof of proposition 4.37. The axiom of choice implies Zorn's lemma. Zorn's lemma implies the well-ordering principle. ☐

In particular, given any set X, we may index the elements of X by a well-ordered index set I and write X = { x_i | i in I }. In this notation we may now state and prove

The Transfinite Induction Principle. Let X = { x_i | i in I } be any set indexed by a well-ordered set I. If P is a property such that, for any i in I, whenever all x_j with  j  <  i have property P, then x_i has property P, then all elements of X have property P.

Proof. Let Y = { x in X  | x has property P }. Suppose X - Y is nonempty, then there is a least element x_i in X - Y. By the definition of least element and X - Y we must have, for any x_j with  j  <  i, that x_j has the property P. But then, by hypothesis, x_i has property P, a contradiction. Therefore, X - Y is empty and X = Y. ☐

A set G together with a binary operation (written here in the usual multiplicative notation) is called a group if

• For all x, y, z in G, x( yz) = (xy)z (associativity)
• There exists an identity element 1 in G such that for all x in G, x1 = x = 1x
• For each x in G, there exists an inverse element x^-1 in G such that xx^-1 = 1 = x^-1x

It is easy to show that the identity element 1 is unique and, for each x in G, the inverse element x^-1 is unique, see [2]. A nonempty subset H of a group G is called a subgroup if, for all h₁, h₂ in H

• h₁h₂ is in H
• h₁^-1 is in H

From the definition it follows that the identity element 1 = h₁h₁^-1 is in H and the subgroup H is itself a group under the induced binary operation of multiplication. For any element x of G, the map g  →  xgx^-1 is a bijection from G to G, called the inner automorphism of G under conjugation by x and this map induces a bijection from H to xHx^-1 which is also a subgroup of G. Given any element x of G, the set xH = { xh | h in H } is called a left coset of H in G, the set Hx = { hx | h in H } is called a right coset of H in G and the set HxH = { h₁xh₂ | h₁, h₂ in H } is called a double coset of H in G. An element of a coset is called a representative for that coset. The maps h  →  xh and h  →  hx induce bijections from H to xH and Hx respectively. Suppose z belongs to the left cosets xH and yH, then z = xh₁ = yh₂ for some h₁, h₂ in H, so xH =  yh₂h₁^-1H = yH. Also, any x in G belongs to a left coset, namely xH. Thus G is the disjoint union of the left cosets of H. Similarly, G is the disjoint union of the right cosets of H and lemma 1 below proves that G is the disjoint union of the double cosets of H. Since (Hx)^-1 = { (hx)^-1 | h in H, x in G } = { x^-1h^-1 | h in H, x in G } = x^-1H  and (yH)^-1 = { (yh)^-1 | h in H, y in G } = { h^-1y^-1 | h in H, y in G } = Hy^-1, there is a bijection between the set of all left cosets and the set of all right cosets of H in G. A set consisting of exactly one representative of each left coset from the set of all left cosets of H in G is called a system of representatives for the left cosets of H in G. Similarly, a set consisting of exactly one representative of each right coset from the set of all right cosets of H in G is called a system of representatives for the right cosets of H in G. By the axiom of choice, a system of representatives for the left cosets of H in G exists and  a system of representatives for the right cosets of H in G exists. A set that is simultaneously a system of representatives for the left cosets of H in G and a system of representatives for the right cosets of H in G is called a common system of representatives for the left and right cosets of H in G.

Lemma 1. Let G be a group and H a subgroup. Then G is the disjoint union of the set of double cosets { HgH | g in G }.

Proof. Suppose x belongs to the double cosets Hg₁H and Hg₂H. Then x = h'₁g₁h'₂ = h''₁g₂h''₂ for some h'₁, h'₂, h''₁, h''₂ in H. Then g₁ = h'₁^-1h''₁g₂h''₂h'₂^-1 and so, for any h₁, h₂ in H, we have  h₁g₁h₂ = h₁h'₁^-1h''₁g₂h''₂h'₂^-1h₂ showing that Hg₁H is contained in Hg₂H. Similarly g₂ = h''₁^-1h'₁g₁h'₂h''₂^-1 and so, for any h₁, h₂ in H, we have  h₁g₂h₂ = h₁h''₁^-1h'₁g₁h'₂h''₂^-1h₂ showing that Hg₂H is contained in Hg₁H. Thus Hg₁H = Hg₂H. This proves that distinct double cosets cannot have any elements in common and must be disjoint. Since every g in G can be written as g = 1g1, every g in G belongs to at least one double coset, namely HgH. This proves that the union of the disjoint double cosets is all of G. ☐

Lemma 2. Let G be a group and H a subgroup. Let HgH be a fixed double coset of H in G. Then

• Every left coset of H in G is either contained in HgH or disjoint from it. Hence HgH is the disjoint union of the left cosets of H in G that are contained in HgH.
• Every right coset of H in G is either contained in HgH or disjoint from it. Hence HgH is the disjoint union of the right cosets of H in G that are contained in HgH.

Proof. Let xH be a left coset of H in G. Suppose xh is an element of xH such that xh belongs to HgH. Then xh = h₁gh₂ for some h₁, h₂ in H, so x = h₁gh₂h^-1. Thus, for any h' in H, xh' = h₁gh₂h^-1h' showing that the left coset xH is contained in HgH. This proves that either the left coset xH is contained in HgH or disjoint from it. Any two left cosets are disjoint because if x is in yH and zH then x = yh₁= zh₂ for some h₁, h₂ in H, so z =  yh₁h₂^-1 shows that yH = zH. Also, every h₁gh₂ in HgH belongs to some left coset contained in HgH, namely h₁gH. This proves that HgH is the disjoint union of the left cosets of H in G that are contained in HgH. Similarly, let Hx be a right coset of H in G. Suppose hx is an element of Hx such that hx belongs to HgH. Then hx = h₁gh₂ for some h₁, h₂ in H, so x = h^-1h₁gh₂. Thus, for any h' in H, h'x = h'h^-1h₁gh₂ showing that the right coset Hx is contained in HgH. This proves that either the right coset Hx is contained in HgH or disjoint from it. Any two right cosets are disjoint because if x is in Hy and Hz then x = h₁y = h₂z for some h₁, h₂ in H, so z =  h₂^-1h₁y shows that Hy = Hz. Also, every h₁gh₂ in HgH belongs to some right coset contained in HgH, namely Hgh₂. This proves that HgH is the disjoint union of the right cosets of H in G that are contained in HgH. ☐

Lemma 3. Let G be a group and H a finite subgroup. Let HgH be a fixed double coset of H in G. Then there exists a system of representatives for the left cosets of H in G that are contained in HgH such that distinct representatives belong to distinct right cosets of H in G that are contained in HgH.

Proof. There are two cases.

• Case 1. Suppose Hg = gH. Then HgH contains exactly one left coset gH = HgH and exactly one right coset Hg = HgH. In this case, select g as a representative for the left coset gH and then g belongs to the unique right coset Hg contained in HgH.
• Case 2. Suppose Hg is not equal to gH. By lemma 2 and the well-ordering principle, let { L_i | i in I } denote the set of left cosets of H in G that are contained in HgH, indexed by a well-ordered set I. Note that any left coset xH contained in HgH can be written as xH = hgH for some h in H. Hence, by the axiom of choice, we can select { h_i in H | i in I } such that { L_i | i in I } = { h_igH | i in I }. We shall now use the principle of transfinite induction. Given i in I, assume that for all j  <  i we have selected h'_j in H such that the right cosets Hgh'_j are all distinct. We claim that we can select h'_i in H such that the right coset Hgh'_i is distinct from all the right cosets Hgh'_j where j  <  i. Suppose not. Then for each h in H there exists a right coset Hgh'_j = Hgh with j  <  i. Thus for each h in H, there exist h'_j, h''_j, h'''_j in H such that h''_jgh'_j = h'''_jgh. That is, for each h in H, there exist h'_j, h''_j, h'''_j in H such that h'''_j^-1h''_jg = ghh'_j^-1. Thus Hg contains gHh'_j^-1 = gH and so H contains gHg^-1. This is the point in the proof where we use the fact that H is finite. Since the inner automorphism under conjugation by g is bijective and H is finite, H = gHg^-1. But then, Hg = gH, a contradiction to the assumption of case 2. Hence, our claim is true: we can select h'_i in H such that the right coset Hgh'_i is distinct from all the right cosets Hgh'_j where j  <  i. By the principle of transfinite induction, we can select distinct right cosets { Hgh'_i | i in I }. Note that h_igH = h_igh'_iH and Hgh'_i = Hh_igh'_i for all i in I. Thus, the element h_igh'_i is a common representative for the left coset h_igH and the right coset Hgh'_i for all i in I. It follows that the set { h_igh'_i | i in I } is a system of representatives for the left cosets of H in G that are contained in HgH such that distinct representatives belong to distinct right cosets of H in G that are contained in HgH. ☐

Proposition. Let G be a group and H a finite subgroup. Then there exists a common system of coset representatives for the left and right cosets of H in G.

Proof. By lemma 1 and the axiom of choice, select a set { g_j in G | j in J } such that { Hg_jH | j in J } is the set of disjoint double cosets whose union is G. By lemma 3 and the axiom of choice, select a set { S_j | j in J } where S_j is a set of representatives for the left cosets of H in G that are contained in Hg_jH such that distinct representatives belong to distinct right cosets of H in G that are contained in Hg_jH. Form the union S of all the sets in { S_j | j in J }. Then S is a system of representatives for all left cosets of H in G such that distinct representatives belong to distinct right cosets of H in G. But, as observed above, there is a bijection between the set of all left cosets of H in G and the set of all right cosets of H in G. Thus each right coset of H in G must have an element in S. It follows that the set S must be a common system of representatives for the left and right cosets of H in G. ☐

Example 1. We first give an example of a group G and subgroup H that satisfy the hypotheses of the proposition. Let G = S₃ denote the symmetric group on three letters consisting of all permutations of the set {1, 2, 3}

1 = (  1   2   3   1   2   3  )	α = (  1   2   3   2  3  1 )	β = (  1   2   3   3  1  2 )
γ = (  1   2   3   1   3   2  )	δ = (  1   2   3   3  2  1 )	ε = (  1   2   3   2  1  3 )

together with the binary operation of permutation multiplication. To facilitate our computation, let us write the multiplication table for the group G explicitly:
 

_______ 1 α β γ δ ε

1 α  β  γ  δ  ε ___ ___ ___ ___ ___ ___ 1 α β γ δ ε α β 1 δ ε γ β 1 α ε γ δ γ ε δ 1 β α δ γ ε α 1 β ε δ γ β α 1

Consider the subgroup H = { 1, ε }. The double cosets of H in G are { 1, ε } and { α, β, γ, δ }. The left cosets of H in G are { 1, ε }, { α, γ } and { β, δ }. The right cosets of H in G are { 1, ε }, { α, δ } and { β, γ }. We may select ε as a common representative for the left coset { 1, ε } and the right coset { 1, ε } contained in the double coset { 1, ε }. We may select γ and δ as common representatives for the left cosets { α, γ }, { β, δ } and right cosets { α, δ }, { β, γ } respectively, contained in the double coset { α, β, γ, δ }. The union of the selected representatives { ε, γ, δ } is a common system of representatives for the left and right cosets of H in G in this example where H is finite.

Example 2. Finally, we give an example of a group G and subgroup H that do not satisfy the hypotheses of the proposition and for which there cannot exist a common system of representatives of the left and right cosets of H in G. Consider the group G generated by x, y subject to the relation xy = y²x. Let H be the subgroup generated by y. Then H = { yⁿ | n is any integer } is an infinite subgroup. Using the relation inductively, it is easy to see that for any integer n, xyⁿx^-1 = y²ⁿ. Thus the subgroup xHx^-1= { y²ⁿ | n is any integer } is properly contained in the subgroup H. This implies that the left coset xH is properly contained in the right coset Hx which is equal to the double coset HxH. But then by lemma 2, the double coset HxH contains at least two left cosets and exactly one right coset. Thus, it is impossible to select representatives for the left cosets of H in HxH that belong to distinct right cosets of H in HxH. By lemma 1 and lemma 2, it follows that it is impossible to select representatives for the left cosets of H in G that belong to distinct right cosets of H in G. Thus, there cannot exist a common system of representatives for the left and right cosets of H in G in this example where H is infinite.