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_{0} of
J
is called a
least element of J if
j_{0
} ≤
j
for all
j in
J. A partially ordered set
I is said
to be
wellordered if every nonempty subset of
I has a least
element. Note that in a wellordered set any two elements
i,
j are comparable since the subset {
i,
j } must
have a least element. We shall use
The WellOrdering Principle. Every set can be wellordered.
Proof. See [1], the proof of proposition
4.37. The axiom of choice implies Zorn's lemma. Zorn's lemma implies the
wellordering principle. ☐
In particular, given any set X, we may index the elements of
X
by a wellordered 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 wellordered 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^{1}x
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_{1},
h_{2} in
H

h_{1}h_{2} is in H

h_{1}^{1} is in H
From the definition it follows that the identity element 1 =
h_{1}h_{1}^{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_{1}xh_{2}

h_{1},
h_{2} 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_{1}
=
yh_{2} for some
h_{1},
h_{2}
in
H, so
xH =
yh_{2}h_{1}^{1}H
=
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^{1}h^{1}

h in
H,
x in
G } =
x^{1}H
and (
yH)
^{1} = { (
yh)
^{1} 
h in
H,
y
in
G } = {
h^{1}y^{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_{1}H
and Hg_{2}H. Then x = h'_{1}g_{1}h'_{2}
= h''_{1}g_{2}h''_{2} for
some h'_{1}, h'_{2}, h''_{1},
h''_{2}
in H. Then g_{1} = h'_{1}^{1}h''_{1}g_{2}h''_{2}h'_{2}^{1}
and so, for any h_{1}, h_{2} in H,
we have h_{1}g_{1}h_{2}
= h_{1}h'_{1}^{1}h''_{1}g_{2}h''_{2}h'_{2}^{1}h_{2}
showing that Hg_{1}H is contained in Hg_{2}H.
Similarly g_{2} = h''_{1}^{1}h'_{1}g_{1}h'_{2}h''_{2}^{1}
and so, for any h_{1}, h_{2} in H,
we have h_{1}g_{2}h_{2}
= h_{1}h''_{1}^{1}h'_{1}g_{1}h'_{2}h''_{2}^{1}h_{2}
showing that Hg_{2}H is contained in Hg_{1}H.
Thus Hg_{1}H = Hg_{2}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_{1}gh_{2} for some
h_{1},
h_{2}
in
H, so
x =
h_{1}gh_{2}h^{1}.
Thus, for any
h' in
H,
xh' =
h_{1}gh_{2}h^{1}h'
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_{1}=
zh_{2}
for some
h_{1},
h_{2} in
H, so
z
=
yh_{1}h_{2}^{1} shows that
yH
=
zH. Also, every
h_{1}gh_{2} in
HgH
belongs to some left coset contained in
HgH, namely
h_{1}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_{1}gh_{2} for some
h_{1},
h_{2}
in
H, so
x =
h^{1}h_{1}gh_{2}.
Thus, for any
h' in
H,
h'
x =
h'
h^{1}h_{1}gh_{2}
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_{1}y
=
h_{2}z for some
h_{1},
h_{2}
in
H, so
z =
h_{2}^{1}h_{1}y
shows that
Hy =
Hz. Also, every
h_{1}gh_{2}
in
HgH belongs to some right coset contained in
HgH, namely
Hgh_{2}.
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 wellordering 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 wellordered 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_{i}gH
 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''_{j}gh'_{j}
= h'''_{j}gh. That is, for each h in H,
there exist h'_{j},
h''_{j},
h'''_{j}
in H such that h'''_{j}^{1}h''_{j}g
= 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_{i}gH = h_{i}gh'_{i}H
and
Hgh'_{i} = Hh_{i}gh'_{i}
for all i in I. Thus, the element h_{i}gh'_{i}
is a common representative for the left coset h_{i}gH and
the right coset Hgh'_{i} for all i in I.
It follows that the set { h_{i}gh'_{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_{j}H
 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_{j}H
such that distinct representatives belong to distinct right cosets of H
in G that are contained in Hg_{j}H. 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_{3}
denote the symmetric group on three letters consisting of all permutations
of the set {1, 2, 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


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^{2}x.
Let H be the subgroup generated by y. Then H = { y^{n}
 n is any integer } is an infinite subgroup. Using the relation
inductively, it is easy to see that for any integer n, xy^{n}x^{1}
= y^{2n}. Thus the subgroup xHx^{1}=
{ y^{2n}  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.