Difference between revisions of "Left cosets partition a group"
Line 8: | Line 8: | ||
# The [[left coset]]s of a subgroup in a group partition the group. | # The [[left coset]]s of a subgroup in a group partition the group. | ||
− | # The relation of being in the | + | # The relation of one element being in the left coset of the other, is an equivalence relation. |
# Every element of the group is in exactly one left coset. | # Every element of the group is in exactly one left coset. | ||
# Any two left cosets of a subgroup either do not intersect, or are equal. | # Any two left cosets of a subgroup either do not intersect, or are equal. | ||
+ | |||
+ | ===Statement with symbols=== | ||
+ | |||
+ | Suppose <math>G</math> is a group, and <math>H</math> is a subgroup. Then, the following equivalent statements are true: | ||
+ | |||
+ | # The left cosets of <math>H</math>, namely <math>gH, g \in G</math>, form a partition of the group <math>G</math>. In other words, <math>G</math> is a disjoint union of left cosets of <math>H</math>. | ||
+ | # The relation <math>a \sim b \iff a \in bH</math> is an equivalence relation on <math>G</math> | ||
+ | # For every <math>g \in G</math>, there is ''exactly'' one left coset containing <math>g</math>. | ||
+ | # If <math>aH</math> and <math>bH</math> are left cosets of <math>H</math> in <math>G</math>, then either <math>aH = bH</math> or <math>aH \cap bH</math> is empty. | ||
+ | |||
+ | ==Equivalence of statements== | ||
+ | |||
+ | These statements are equivalent because of the following general fact about sets and equivalence relations. If <math>S</math> is a set, and <math>\sim</math> is an equivalence relation on <math>S</math>, then we can partition <math>S</math> as a disjoint union of ''equivalence classes'' under <math>\sim</math>. Two elements <math>a</math> and <math>b</math> are defined to be in the same equivalence class under <math>\sim</math> if <math>a \sim b</math>. | ||
+ | |||
+ | Conversely, if <math>S</math> is partitioned as a disjoint union of subsets, then the relation of being in the same subset is an equivalence relation on <math>S</math>. | ||
+ | |||
+ | Hence, there is a correspondence between ''equivalence relations'' on a set and ''partitions of the set'' into subsets. This statement about left cosets thus states that the left cosets partition the group, which is ''also'' the same as saying that the relation of one element being in the left coset of another, is an equivalence relation. | ||
+ | |||
+ | Here, we give the proof both in form (2) and form (4). The two proofs are essentially the same, but they are worked out in somewhat different language, and explain how to think both in terms of ''equivalence relations'' and in terms of ''partitions''. | ||
==Definitions used== | ==Definitions used== | ||
Line 19: | Line 38: | ||
==Proof in form (2)== | ==Proof in form (2)== | ||
− | + | '''Given''': A group <math>G</math>, a subgroup <math>H</math> | |
+ | |||
+ | '''To prove''': The relation <math>a \sim b \iff \ \exists \ h \in H</math> such that <math>a = bh</math>, is an equivalence relation on <math>G</math> | ||
===Reflexivity=== | ===Reflexivity=== | ||
− | Clearly <math>e \in H</math> (since <math>H</math> is a subgroup). Hence, for any <math>a \in G</math>, <math>a = ae</math>, so <math>a</math> | + | '''To prove''': For any <math>a \in G</math>, <math>a \sim a</math>. |
+ | |||
+ | '''Proof''': Clearly <math>e \in H</math> (since <math>H</math> is a subgroup). Hence, for any <math>a \in G</math>, <math>a = ae</math>, so <math>a \sim a</math>: <math>a</math> is in its own left coset. | ||
===Symmetry=== | ===Symmetry=== | ||
− | If <math>a = bh</math>, for some <math>h \in H</math>, then <math>b = ah^{-1}</math>. Since <math>h \in H</math> and <math>H</math> is a subgroup, <math>h^{-1} \in H</math>. Thus, if <math>a</math> is in the left coset of <math>b</math>, then <math>b</math> is in the left coset of <math>a</math>. | + | '''To prove''': For any <math>a,b \in G</math> such that <math>a \sim b</math>, we have <math>b \sim a</math>. |
+ | |||
+ | '''Proof''': If <math>a = bh</math>, for some <math>h \in H</math>, then <math>b = ah^{-1}</math>. Since <math>h \in H</math> and <math>H</math> is a subgroup, <math>h^{-1} \in H</math>. Thus, if <math>a</math> is in the left coset of <math>b</math>, then <math>b</math> is in the left coset of <math>a</math>. In symbols, <math>a \sim b \implies b \sim a</math>. | ||
===Transitivity=== | ===Transitivity=== | ||
− | If <math>a = bh</math>, and <math>b = ck</math>, for <math>h, k \in H</math>, and <math>a = ckh</math>. Since <math>H</math> is a subgroup, <math>h,k \in H \implies kh \in H</math>, so <math>a</math> is in the left coset of <math>c</math>. | + | '''To prove''': If <math>a,b,c \in G</math> are such that <math>a \sim b</math>, and <math>b \sim c</math>, then <math>a \sim c</math> |
+ | |||
+ | '''Proof''': If <math>a = bh</math>, and <math>b = ck</math>, for <math>h, k \in H</math>, and <math>a = ckh</math>. Since <math>H</math> is a subgroup, <math>h,k \in H \implies kh \in H</math>, so <math>a</math> is in the left coset of <math>c</math>. | ||
==Proof in form (4)== | ==Proof in form (4)== | ||
− | + | '''Given''': A group <math>G</matH>, a subgroup <math>H</math>, two elements <math>a,b \in G</math> | |
+ | |||
+ | '''To prove''': The left cosets <math>aH</math> and <math>bH</math> are either equal or disjoint (they have empty intersection) | ||
+ | |||
+ | '''Proof''': We'll assume that <math>aH</math> and <math>bH</math> are ''not'' disjoint, and prove that they are equal. | ||
For this, suppose <math>c \in aH \cap bH</math>. Then, there exist <math>h_1,h_2</math> such that <math>ah_1 = bh_2 = c</math>. Thus, <math>b = ah_1h_2^{-1} \in aH</math> and <math>a = bh_2h_1^{-1} \in bH</math>. | For this, suppose <math>c \in aH \cap bH</math>. Then, there exist <math>h_1,h_2</math> such that <math>ah_1 = bh_2 = c</math>. Thus, <math>b = ah_1h_2^{-1} \in aH</math> and <math>a = bh_2h_1^{-1} \in bH</math>. | ||
Line 42: | Line 73: | ||
<section end=beginner/> | <section end=beginner/> | ||
<section begin=revisit/> | <section begin=revisit/> | ||
+ | |||
+ | ==Converse== | ||
+ | |||
+ | A partial converse to this result is true. If <math>H</math> is a subset of <math>G</math> ''containing the identity element'' with the property that the set of all left translates of <math>H</math>, i.e. the set of subsets <math>gH</matH>, form a partition of <math>G</math>, then <math>H</math> is a subgroup of <math>G</math>. | ||
+ | |||
+ | {{further|[[Subset containing identity whose left translates partition the group is a subgroup]]}} | ||
+ | |||
==Other proofs== | ==Other proofs== | ||
Line 55: | Line 93: | ||
The only left congruences on a group are those that arise as partitions in terms of left cosets of a subgroup. | The only left congruences on a group are those that arise as partitions in terms of left cosets of a subgroup. | ||
+ | |||
+ | ==In other algebraic structures== | ||
+ | |||
+ | We observed that the proof that the left cosets of a subgroup partition the group used all the properties of groups: the existence of identity element was used to prove reflexivity, the existence of inverses was used to prove symmetry, and associativity was used to prove transitivity. Hence, extending the result to algebraic structures ''weaker'' than groups is in general hard. There are, however, some ways of extending. | ||
+ | |||
+ | * [[Left cosets of a subgroup partition a monoid]]: We do not require the ''bigger structure'' to be a group. All we need is associativity in the bigger structure. Thus, the left cosets of a ''subgroup'' in a monoid, still partition it. (Note that we still do require ''associativity'' in the bigger structure). | ||
+ | * [[Left cosets of a cyclic subgroup partition an alternative loop]]: An alternative loop is an [[algebra loop]] where any two elements generate a subgroup. It turns out that in an alternative loop, the left cosets of any cyclic subgroup give a partition. | ||
<section end=revisit/> | <section end=revisit/> | ||
==References== | ==References== | ||
===Textbook references=== | ===Textbook references=== | ||
* {{booklink-proved|DummitFoote}}, Proposition 4, Page 80 | * {{booklink-proved|DummitFoote}}, Proposition 4, Page 80 |
Revision as of 14:40, 29 July 2008
DIRECT: The fact or result stated in this article has a trivial/direct/straightforward proof provided we use the correct definitions of the terms involved
View other results with direct proofs
VIEW FACTS USING THIS: directly | directly or indirectly, upto two steps | directly or indirectly, upto three steps|
VIEW: Survey articles about this
Statement
Verbal statement
The following equivalent statements are true:
- The left cosets of a subgroup in a group partition the group.
- The relation of one element being in the left coset of the other, is an equivalence relation.
- Every element of the group is in exactly one left coset.
- Any two left cosets of a subgroup either do not intersect, or are equal.
Statement with symbols
Suppose is a group, and is a subgroup. Then, the following equivalent statements are true:
- The left cosets of , namely , form a partition of the group . In other words, is a disjoint union of left cosets of .
- The relation is an equivalence relation on
- For every , there is exactly one left coset containing .
- If and are left cosets of in , then either or is empty.
Equivalence of statements
These statements are equivalent because of the following general fact about sets and equivalence relations. If is a set, and is an equivalence relation on , then we can partition as a disjoint union of equivalence classes under . Two elements and are defined to be in the same equivalence class under if .
Conversely, if is partitioned as a disjoint union of subsets, then the relation of being in the same subset is an equivalence relation on .
Hence, there is a correspondence between equivalence relations on a set and partitions of the set into subsets. This statement about left cosets thus states that the left cosets partition the group, which is also the same as saying that the relation of one element being in the left coset of another, is an equivalence relation.
Here, we give the proof both in form (2) and form (4). The two proofs are essentially the same, but they are worked out in somewhat different language, and explain how to think both in terms of equivalence relations and in terms of partitions.
Definitions used
Let be a group, be a subgroup.
For , we say that is in the left coset of if there exists such that .
Proof in form (2)
Given: A group , a subgroup
To prove: The relation such that , is an equivalence relation on
Reflexivity
To prove: For any , .
Proof: Clearly (since is a subgroup). Hence, for any , , so : is in its own left coset.
Symmetry
To prove: For any such that , we have .
Proof: If , for some , then . Since and is a subgroup, . Thus, if is in the left coset of , then is in the left coset of . In symbols, .
Transitivity
To prove: If are such that , and , then
Proof: If , and , for , and . Since is a subgroup, , so is in the left coset of .
Proof in form (4)
Given: A group , a subgroup , two elements
To prove: The left cosets and are either equal or disjoint (they have empty intersection)
Proof: We'll assume that and are not disjoint, and prove that they are equal.
For this, suppose . Then, there exist such that . Thus, and .
Now, for any element , we have , and similarly, for every element , we have . Thus, and , so .
Converse
A partial converse to this result is true. If is a subset of containing the identity element with the property that the set of all left translates of , i.e. the set of subsets , form a partition of , then is a subgroup of .
Further information: Subset containing identity whose left translates partition the group is a subgroup
Other proofs
Orbits under a group action
One easy way of seeing that the left cosets partition a group is by viewing the left cosets as orbits of the group under the action of the subgroup by right multiplication.
Left congruence
Another way of viewing the partition of a group into left cosets of a subgroup is in terms of a left congruence. A left congruence on a magma is an equivalence relation with the property that:
The only left congruences on a group are those that arise as partitions in terms of left cosets of a subgroup.
In other algebraic structures
We observed that the proof that the left cosets of a subgroup partition the group used all the properties of groups: the existence of identity element was used to prove reflexivity, the existence of inverses was used to prove symmetry, and associativity was used to prove transitivity. Hence, extending the result to algebraic structures weaker than groups is in general hard. There are, however, some ways of extending.
- Left cosets of a subgroup partition a monoid: We do not require the bigger structure to be a group. All we need is associativity in the bigger structure. Thus, the left cosets of a subgroup in a monoid, still partition it. (Note that we still do require associativity in the bigger structure).
- Left cosets of a cyclic subgroup partition an alternative loop: An alternative loop is an algebra loop where any two elements generate a subgroup. It turns out that in an alternative loop, the left cosets of any cyclic subgroup give a partition.
References
Textbook references
- Abstract Algebra by David S. Dummit and Richard M. Foote, 10-digit ISBN 0471433349, 13-digit ISBN 978-0471433347, ^{More info}, Proposition 4, Page 80