[]
|
Research 
|
Profile 
|
Teaching 
|
Software 
|
Contact 
|

 
 

COMMON SYSTEMS OF

COSET REPRESENTATIVES


ASHAY DHARWADKER

INSTITUTE OF MATHEMATICS
H-501 PALAM VIHAR
DISTRICT  GURGAON
HARYANA  1 2 2 0 1 7
INDIA

ashay@dharwadker.org


ABSTRACT
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.
ACKNOWLEDGEMENTS
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.
Download Adobe PDF Version (47 Kb)
 
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 j0 of J is called a least element of J if  j0  ≤  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 = { xi | i in I }. In this notation we may now state and prove

The Transfinite Induction Principle. Let X = { xi | 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 xj with  j  <  i have property P, then xi 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 xi in X - Y. By the definition of least element and X - Y we must have, for any xj with  j  <  i, that xj has the property P. But then, by hypothesis, xi 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 h1, h2 in H
  • h1h2 is in H
  • h1-1 is in H
From the definition it follows that the identity element 1 = h1h1-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 = { h1xh2 | h1, h2 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 = xh1 = yh2 for some h1, h2 in H, so xHyh2h1-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-1 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 Hg1H and Hg2H. Then x = h'1g1h'2 = h''1g2h''2 for some h'1, h'2, h''1, h''2 in H. Then g1 = h'1-1h''1g2h''2h'2-1 and so, for any h1, h2 in H, we have  h1g1h2 = h1h'1-1h''1g2h''2h'2-1h2 showing that Hg1H is contained in Hg2H. Similarly g2 = h''1-1h'1g1h'2h''2-1 and so, for any h1, h2 in H, we have  h1g2h2 = h1h''1-1h'1g1h'2h''2-1h2 showing that Hg2H is contained in Hg1H. Thus Hg1H = Hg2H. 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 = h1gh2 for some h1, h2 in H, so x = h1gh2h-1. Thus, for any h' in H, xh' = h1gh2h-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 = yh1= zh2 for some h1, h2 in H, so zyh1h2-1 shows that yH = zH. Also, every h1gh2 in HgH belongs to some left coset contained in HgH, namely h1gH. 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 = h1gh2 for some h1, h2 in H, so x = h-1h1gh2. Thus, for any h' in H, h'x = h'h-1h1gh2 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 = h1y = h2z for some h1, h2 in H, so zh2-1h1y shows that Hy = Hz. Also, every h1gh2 in HgH belongs to some right coset contained in HgH, namely Hgh2. 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 { Li | 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 { hi in H | i in I } such that { Li | i in I } = { higH | 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 higH = high'iH and Hgh'i = Hhigh'i for all i in I. Thus, the element high'i is a common representative for the left coset higH and the right coset Hgh'i for all i in I. It follows that the set { high'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 { gj in G | j in J } such that { HgjH | 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 { Sj | j in J } where Sj is a set of representatives for the left cosets of H in G that are contained in HgjH such that distinct representatives belong to distinct right cosets of H in G that are contained in HgjH. Form the union S of all the sets in { Sj | 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 = S3 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 = y2x. Let H be the subgroup generated by y. Then H = { yn | n is any integer } is an infinite subgroup. Using the relation inductively, it is easy to see that for any integer n, xynx-1 = y2n. Thus the subgroup xHx-1= { y2n | 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.


 
REFERENCES
[1] Elliott Mendelson, Introduction to Mathematical Logic, Wadsworth Inc., 1987.
[2] Nathan Jacobson, Basic Algebra I, W. H. Freeman & Co., 1974.


ISBN 1466265302

Copyright © 2005 by Ashay Dharwadker. All rights reserved.