In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, if
G is a
groupIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, and
H is a
subgroupIn group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
of
G, and
g is an element of
G, then
- gH = {gh : h an element of H } is a left coset of H in G, and
- Hg = {hg : h an element of H } is a right coset of H in G.
Only when
H is
normalIn abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....
will the right and left cosets of
H coincide, which is one definition of normality of a
subgroupIn group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
.
A
coset is a left or right coset of
some subgroupIn group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
in
G. Since
Hg =
g (
g−1Hg ), the right cosets
Hg (of
H ) and the left cosets
g (
g−1Hg ) (of the
conjugateIn mathematics, especially group theory, the elements of any group may be partitioned into conjugacy classes; members of the same conjugacy class share many properties, and study of conjugacy classes of non-abelian groups reveals many important features of their structure...
subgroup
g−1Hg ) are the same. Hence it is not meaningful to speak of a coset as being left or right unless one first specifies the underlying
subgroupIn group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
. In other words: a right coset of one subgroup equals a left coset of a different (conjugate) subgroup. If the left cosets and right cosets are the same then H is a
normal subgroupIn abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....
and the cosets form a group called the
quotient groupIn mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...
.
The map
gH→(
gH)
−1=
Hg−1 defines a
bijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
between the left cosets and the right cosets of H, so the number of left cosets is equal to the number of right cosets. The common value is called the
indexIn mathematics, specifically group theory, the index of a subgroup H in a group G is the "relative size" of H in G: equivalently, the number of "copies" of H that fill up G. For example, if H has index 2 in G, then intuitively "half" of the elements of G lie in H...
of
H in
G.
For
abelian groupIn abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s, left cosets and right cosets are always the same. If the group operation is written additively then the notation used changes to
g+
H or
H+
g.
Cosets are a basic tool in the study of groups, for example they play a central role in
Lagrange's theoremLagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
.
Examples
Let
G be the additive group of integers
Z = {… , −2, −1, 0, 1, 2, …} and
H the subgroup
mZ = = {…, −2m, −m, 0, m, 2m, …} where m is a positive integer. Then the cosets of H in G are the m sets mZ,
mZ+1, … mZ+(
m−1), where
mZ+a={…, −2m+a, −m+a, a, m+a, 2m+a, …}. The coset mZ+
a is the
congruence classesIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
of
a modulo
m.
Another example of a coset comes from the theory of
vector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
s. The elements (vectors) of a vector space form an
abelian groupIn abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
under vector addition. It is not hard to show that
subspacesThe concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....
of a vector space are subgroups of this group. For a vector space
V, a subspace
W, and a fixed vector
a in
V, the sets
are called affine subspaces, and are cosets (both left and right, since the group is abelian). In terms of
geometricIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
vectors, these affine subspaces are all the "lines" or "planes" parallel to the subspace, which is a line or plane going through the origin.
Definition using equivalence classes
Some authors define the left cosets of H in G to be the
equivalence classes under the
equivalence relationIn mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
on
G given by
x ~
y if and only if
x−1y ∈
H. The relation can also be defined by
x ~
y if and only if
xh=
y for some
h in
H. It can be shown that the relation given is, in fact, an
equivalence relationIn mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
and that the two definitions are equivalent. It follows that any two left cosets of
H in
G are either identical or
disjoint . In other words every element of
G belongs to one and only one left coset and so the left cosets form a
partitionIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of
G. Corresponding statements are true for right cosets.
Double cosets
Given two subgroups,
H and
K of a group
G, the
double coset of
H and
K in
G are sets of the form
HgK = {
hgk :
h an element of
H ,
k an element of
K }. These are the left cosets of
K and right cosets of
H when
H=1 and
K=1 respectively.
General properties
The identity is in precisely one left or right coset, namely
H itself. Thus
H is both a left and right coset of itself.
A
coset representative is a representative in the equivalence class sense. A set of representatives of all the cosets is called a
transversalIn geometry , when two coplanar lines exist such that a third coplanar line passes thru both lines. This third line is named the Transversal....
. There are other types of equivalence relations in a group, such as conjugacy, that form different classes which do not have the properties discussed here. Some books on very applied group theory erroneously identify the conjugacy class as 'the' equivalence class as opposed to a particular type of equivalence class.
Index of a subgroup
All left cosets and all right cosets have the same
orderIn group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....
(number of elements, or
cardinality in the case of an infinite
H), equal to the order of
H (because
H is itself a coset). Furthermore, the number of left cosets is equal to the number of right cosets and is known as the
index of
H in
G, written as [
G :
H ].
Lagrange's theoremLagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
allows us to compute the index in the case where
G and
H are finite, as per the formula:
- |G | = [G : H ] · |H |.
This equation also holds in the case where the groups are infinite, although the meaning may be less clear.
Cosets and normality
If
H is not
normalIn abstract algebra, a normal subgroup is a subgroup which is invariant under conjugation by members of the group. Normal subgroups can be used to construct quotient groups from a given group....
in
G, then its left cosets are different from its right cosets. That is, there is an
a in
G such that no element
b satisfies
aH =
Hb. This means that the partition of
G into the left cosets of
H is a different partition than the partition of
G into right cosets of
H. (It is important to note that
some cosets may coincide. For example, if
a is in the
centerIn abstract algebra, the center of a group G, denoted Z,The notation Z is from German Zentrum, meaning "center". is the set of elements that commute with every element of G. In set-builder notation,...
of
G, then
aH =
Ha.)
On the other hand, the subgroup
N is normal if and only if
gN =
Ng for all
g in
G. In this case, the set of all cosets form a group called the
quotient groupIn mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...
G /
N with the operation ∗ defined by (
aN )∗(
bN ) =
abN. Since every right coset is a left coset, there is no need to differentiate "left cosets" from "right cosets".
Applications
- Cosets of Q in R are used in the construction of Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by . The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vitali sets, and their existence is proven on the assumption of the axiom of...
s, a type of Non-measurable setIn mathematics, a non-measurable set is a set whose structure is so complicated that it cannot be assigned any meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory....
.
- Cosets are central in the definition of the transfer
In mathematics, the transfer in group theory is a group homomorphism defined given a group G and a subgroup of finite index H, which goes from the abelianization of G to that of H.-Formulation:...
.
- Cosets are important in computational group theory. For example Thistlethwaite's algorithm for solving Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
relies heavily on cosets.
- Coset leader
In the field of coding theory, a coset leader is defined as a word of minimum weight in any particular coset - that is, a word with the lowest amount of non-zero entries...
s are used in decoding received data in Linear error-correcting codesIn coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...
.
See also
- Double coset
In mathematics, an double coset in G, where G is a group and H and K are subgroups of G, is an equivalence class for the equivalence relation defined on G by...
- Heap
In abstract algebra, a heap is a mathematical generalisation of a group. Informally speaking, a heap is obtained from a group by "forgetting" which element is the unit, in the same way that an affine space can be viewed as a vector space in which the 0 element has been "forgotten"...
- Lagrange's theorem
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
- Quotient group
In mathematics, specifically group theory, a quotient group is a group obtained by identifying together elements of a larger group using an equivalence relation...
- Coset enumeration
In mathematics, coset enumeration is the problem of counting the cosets of a subgroup H of a group G given in terms of a presentation. As a by-product, one obtains a permutation representation for G on the cosets of H...