| Related sites for http://www.geocities.com/dharwadker/coset.html |
| International_Society_for_Group_Theory_in_Cognitive_Science Group theory in: Robotics, Problem-Solving, Planning, Learning, Language, Perception, Art, Design, Engineering, Manufacturing, | | Introduction_to_Group_Theory A fairly easy to understand tutorial. Fourteen sections, including groups, Cayley tables, subgroups, cosets, Lagrange's theorem, cyclic groups and subgroups, permutations, and Rubik's cube. | | The_Lie_algebras_su(N),_an_introduction Publication: An Introduction to the Lie Algebras su(N). By Walter Pfeifer, Switzerland. A free copy can be ordered. | | Mod-2_Cohomology_of_2-Groups Computer calculation of the mod-2 cohomology of groups of order 8, 16, 32 and 64. | | The_Moonshine_Page Bibliography, meetings. | | New_York_Group_Theory_Cooperative Software (Magnus), preprints, meetings, links. Magnus - a graphically-oriented system for computational group theory - allows one to explore and experiment with abstract groups without the need for l | | Open_Problems_in_Group_Theory Part of the Magnus project. Contains over 150 problems in group theory, both well known and relatively new. | | PARGAP Parallel GAP/MPI (ParGAP/MPI), a share package for GAP. UNIX (or Cygwin/Windows). Download source and documentation by FTP. | | Permutation_Group_Problems Compiled by Peter Cameron. | | Permutation_Groups_Resources Web-based resources for permutation groups and related areas in group theory and combinatorics. | | Semigroup_Theory Directory of home pages and conferences maintained at Southampton University. | | Symmetric_Presentations Some presentations of groups (symmetric or otherwise). | | Symmetry The main point group symmetries of interest to defect physics by operation (reflection, rotations etc) and classification (trigonal, and cubic). Most point groups also have the associated character | | Symmetry_Groups_in_Maple_V A worksheet by W.D. Joyner. | | Topological_Methods_in_Group_Theory Table of contents only; draft chapters can be downloaded by arrangement. | | Trinomials_with_Interesting_Galois_Groups Parametrisation of trinomials with Galois groups contained in the simple group G168. | | The_World_of_Groups Part of the World Wide Algebra project. Open problems in combinatorial group theory, a list of personal web pages, conferences and seminars, and useful links. | | Caribbean_African_Ancestry_Project A population genetic study with goal of identifying ethnic groups that contributed to the Caribbean population. Features research background, photos and information on methodology. | | Accumet_Materials High temperature labware, made of refractory materials. | | Agilent_Educator\'s_Corner Offers a variety of general purpose test and measurement equipment for engineering education labs. | | All_World_Scientifics__Wine_Testing_Supplies A full-line scientific supplier offering laboratory equipment with a focus on wine testing. | | Alpkem_Technicon_AutoAnalyzer_Instruments A source for instrumentation used in soil, water, and air analysis. International distributor and manufacturer of peristaltic pump tubing. | | APS_Labware Specializes in design, manufacturing and service organisation of platinum alloy products, including crucibles and evaporating dishes. | | Arrington_Research Eye movement measurement and analysis software and hardware systems. Eye tracking: ViewPoint Eye Tracker software and hardware. | | Astell_Scientific Manufacturers of autoclaves and sterilizers for laboratory and medical applications. | | Asylum_Research Supplier of innovative instrumentation for nano-science and technology. The focus of the site is on Atomic Force Microscopy instruments and supplies. | | ASYS_Hitech Manufactures microplate readers, washers, dispensers and shaker/incubators for microplate applications. Includes company profile, product specifications, and documentation downloads. | | Atago_Co_,_Ltd_ Manufactures refractometers and polarimeters for use in the food and beverage industry, research labs, industrial facilities, universities and clinics. | | Automated_Fusion_Technology Sample preparation for (XRF) and (ICP-AE) spectrometric analysis and platinum ware. | | Axyos Australian manufacturer of laboratory and scientific equipment to ISO 9001 specifications. Product line includes a range of cell culture and incubation products. | | Bellingham_and_Stanley_Ltd Manufactures refractometers and polarimeters. | | Big-Dipper_Technochem_Institute Offers chemical analyzers, and meters for moisture, humidity, pH and conductivity, in China. | | Biochrom Manufacturer of amino acid analysers, UV/visible spectrophotometers, microplate readers, low volume liquid dispensers and gel electrophoresis equipment. Product information, company profile, news and | | Bioscreen_C_MBR_homepage A proven precision incubator and a culture growth monitoring instrument (OD reader) for up to 200 samples. Also the source for consumables and information regarding the instrument. | | Boeckeler_Instruments Manufacturer of precision video measuring devices for the industrial, biomedical, and presentation markets. | | Brookhaven_Instruments Instruments for particle sizing, laser light scattering, zeta potential and polymer and particle characterisation. Also sells microspheres and certified standard particles. | | Brüel_and_Kjaer Manufactures transducers, instruments and software for sound, acceleration, and vibration measurement and analysis. | | Burkard Manufacturer of a range of instruments, equipment and systems, standard and novel developments for entomological, environmental and agricultural research. | | Caldon,_Inc Specializes in advanced measurements based on the movement of sound waves through fluids. | | The_CAL2k_Calorimeter_System The CAL2k Calorimeter System is the most advanced calorimeter system available today. The system was designed and manufactured by DDS. |
|
Common Systems of Coset Representatives - Ashay Dharwadker
A:link {color:#664400}
A:visited {color:#664400}
A:hover {color:#997700}
A {text-decoration:none}
td.large {font-size: 280%;}
td.extralarge {font-size: 560%;}
.menu div {font-family: verdana, arial, helvetica, sans-serif; font-size: 12px;}
.menu td {font-family: verdana, arial, helvetica, sans-serif; font-size: 12px;}
.menu a:link { color:#888888 }
.menu a:visited { color:#888888 }
.menu a:hover { color:#000000 }
.menu @media all {h1, h2, p { margin:0 0 .8em 0 }}
#container { position:relative; width:430px; height:12px; z-index:100 }
#lyr0 { position:absolute; visibility:visible; background-color:#FEFEFE; left:0; top:0; z-index:1 }
#lyr1 { position:absolute; visibility:hidden; background-color:#FEFEFE; left:9; top:0; width:412; height:220; z-index:1 }
#lyr2 { position:absolute; visibility:hidden; background-color:#FEFEFE; left:104; top:0; z-index:1 }
#lyr3 { position:absolute; visibility:hidden; background-color:#FEFEFE; left:180; top:0; z-index:1 }
#lyr4 { position:absolute; visibility:hidden; background-color:#FEFEFE; left:264; top:0; z-index:1 }
#lyr5 { position:absolute; visibility:hidden; background-color:#FEFEFE; left:324; top:0; z-index:1 }
var origWidth, origHeight;
if (document.layers) {
origWidth = window.innerWidth; origHeight = window.innerHeight;
window.onresize = function() { if (window.innerWidth != origWidth || window.innerHeight != origHeight) history.go(0); }
}
var cur_lyr;
function swapLayers(id) {
if (cur_lyr) hideLayer(cur_lyr);
showLayer(id);
cur_lyr = id;
}
function showLayer(id) {
var lyr = getElemRefs(id);
if (lyr && lyr.css) lyr.css.visibility = "visible";
}
function hideLayer(id) {
var lyr = getElemRefs(id);
if (lyr && lyr.css) lyr.css.visibility = "hidden";
}
function getElemRefs(id) {
var el = (document.getElementById)? document.getElementById(id): (document.all)? document.all[id]: (document.layers)? getLyrRef(id,document): null;
if (el) el.css = (el.style)? el.style: el;
return el;
}
function getLyrRef(lyr,doc) {
if (document.layers) {
var theLyr;
for (var i=0; i 0)
if ((theLyr = getLyrRef(lyr,theLyr.document)) != null)
return theLyr;
}
return null;
}
}
![[]](http://c10.statcounter.com/counter.php?sc_project=982795&java=0&security=f7603c3b&invisible=1)
|
Research 
|
Profile
|
Teaching
|
Software
|
Contact
|
2000 Four Colour Theorem
2001 The Witt Design & Golay Code
2002 Riemann Surfaces
2003 Heptahedron & Roman Surface
2004 Hamiltonian Circuit Algorithm
2005 Systems of Coset Representatives
2006 The Vertex Cover Algorithm
2006 The Independent Set Algorithm
2006 The Clique Algorithm
2006 The Vertex Coloring Algorithm
2007 Applications of Graph Theory
2008 The Grand Unification
Ashay Dharwadker
Today's Lecture
My Students Database
Calculus 1.0
Statistics 1.0
Get in touch...
COMMON SYSTEMS OF
COSET REPRESENTATIVES
ASHAY DHARWADKER
H-501 PALAM VIHAR
DISTRICT GURGAON
HARYANA 1 2 2 0 1 7
INDIA
dharwadker@yahoo.com
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.
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
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 xH = yh2h1-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 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 z
= yh1h2-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 z = h2-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.
Copyright © 2005 by Ashay
Dharwadker. All rights reserved.
geovisit();
|
|
