# Changes

## Left cosets partition a group

, 00:07, 4 July 2011
Proof in form (4)
# The left cosets of $H$, namely $gH, g \in G$, form a partition of the group $G$. In other words, $G$ is a disjoint union of left cosets of $H$.
# The relation $a \sim b \iff a \in bH$ is an equivalence relation on $G$
# For every $g \in G$, there is ''exactly'' one left coset of $H$ in $G$ containing $g$.
# If $aH$ and $bH$ are left cosets of $H$ in $G$, then either $aH = bH$ or $aH \cap bH$ is empty.
==Equivalence of statements==
These statements are equivalent because of the following general fact about sets and equivalence relations. If $S$ is a set, and $\sim$ is an equivalence relation on $S$, then we can partition $S$ as a disjoint union of ''equivalence classes'' under $\! \sim$. Two elements $a$ and $b$ are defined to be in the same equivalence class under $\! \sim$ if $\! a \sim b$.
Conversely, if $S$ is partitioned as a disjoint union of subsets, then the relation of being in the same subset is an equivalence relation on $S$.
Let $G$ be a group, $H$ be a subgroup.
For $a,b \in G$, we say that $a$ is in the left coset of $b$ with respect to $H$ if there exists $h \in H$ such that $a = bh$.<section end=beginner/><section begin=revisit/> ==Related facts== ===Converse=== A partial converse to this result is true. If $H$ is a subset of $G$ ''containing the identity element'' with the property that the set of all left translates of $H$, i.e. the set of subsets $gH</matH>, form a partition of [itex]G$, then $H$ is a subgroup of $G$. {{further|[[Subset containing identity whose left translates partition the group is a subgroup]]}} ===Analogues in other algebraic structures=== The proof that the left cosets of a subgroup partition the group uses all the properties of groups: the existence of identity element is used to prove reflexivity, the existence of inverses (along with associativity and the identity element) was used to prove symmetry, and associativity is 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. {| class="wikitable" border="1"! Statement !! Analogue of [[group]] !! Analogue of subgroup !! Comment|-| [[Left cosets of a subgroup partition a monoid]] || [[monoid]] (associative, identity element, not necessarily any inverses) || submonoid that is in fact a group || 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).|} ===Relation with right cosets and normal subgroups=== * [[Right cosets partition a group]]: The proof of this is analogous to that for left cosets.* [[Left cosets are in bijection via left multiplication]]: In particular, any two left cosets of a subgroup have the same size as the subgroup.* [[Equivalence of definitions of coset]]: A subset of a group occurs as the left coset of a subgroup if and only if it occurs as the right coset of a subgroup.* For a [[normal subgroup]], the set of left cosets coincides with the set of right cosets, and this set can be given the structure of a group called the [[quotient group]]. Any homomorphism of groups is obtained by composing the quotient map to a quotient group with an injection: see [[normal subgroup equals kernel of homomorphism]] and [[first isomorphism theorem]]. ===Other related facts=== * [[Lattice of subgroups embeds in partition lattice]]: As we see here, every subgroup gives rise to a partition of the group (namely, the partition into left cosets). This gives a function from the [[lattice of subgroups]] of a group to the partition lattice of the group. It turns out that this map is a lattice embedding, i.e., it preserves the lattice operations. <section end=revisit/><section begin=beginner/>
==Proof in form (2)==
===Reflexivity===
'''To prove''': For any $a \in G$, $\! a \sim a$.
'''Proof''': Clearly $e \in H$ (since $H$ is a subgroup). Hence, for any $a \in G$, $a = ae$, so $\! a \sim a$: $a$ is in its own left coset.
===Symmetry===
'''To prove''': For any $a,b \in G$ such that $\! a \sim b$, we have $\! b \sim a$.
'''Proof''': If $a = bh$, for some $h \in H$, then $b = ah^{-1}$. Since $h \in H$ and $H$ is a subgroup, $h^{-1} \in H$. Thus, if $a$ is in the left coset of $b$, then $b$ is in the left coset of $a$. In symbols, $a \sim b \implies b \sim a$.
===Transitivity===
'''To prove''': If $a,b,c \in G$ are such that $\! a \sim b$, and $\! b \sim c$, then $a \sim c$
'''Proof''': If $a = bh$, and $b = ck$, for $h, k \in H$, and $a = ckh$. Since $H$ is a subgroup, $h,k \in H \implies kh \in H$, so $a$ is in the left coset of $c$.
For this, suppose $c \in aH \cap bH$. Then, there exist $h_1,h_2$ such that $ah_1 = bh_2 = c$. Thus, $b = ah_1h_2^{-1} \in aH$ and $a = bh_2h_1^{-1} \in bH$.
Now, for any element $ah \in aH$, we have $ah = bh_2h_1^{-1}h \in bH$, and similarly, for every element $bh \in bH$, we have $bh = ah_1h_2^{-21}h \in aH$. Thus, $aH \subset subseteq bH$ and $bH \subset subseteq aH$, so $aH = bH$.
<section end=beginner/>
<section begin=revisit/>

==Converse==

A partial converse to this result is true. If $H$ is a subset of $G$ ''containing the identity element'' with the property that the set of all left translates of $H$, i.e. the set of subsets $gH</matH>, form a partition of [itex]G$, then $H$ is a subgroup of $G$.

{{further|[[Subset containing identity whose left translates partition the group is a subgroup]]}}
==Other proofs==
The only left congruences on a group are those that arise as partitions in terms of left cosets of a subgroup.
<section end=revisit/>
==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 (along with associativity and the identity element) 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/>
==References==
===Textbook references===
* {{booklink-proved|DummitFoote}}, Proposition 4, Page 80