Cosets and Lagrange's Theorem
Cosets
It's a bit difficult to explain exactly why cosets are so important without working with them for a while first. But as you'll hopefully start to understand within my next few posts, cosets pop up everywhere and are a necessary tool to get anything done in the world of algebra. Let's dig in, shall we?
Definition. Let $H$ denote a subgoup of a group $G$. For any fixed element $x\in G$, the right coset of $H$ with respect to $x$ is the set $Hx=\{hx\in G\mid h\in H\}$.
Definition. Let $H$ denote a subgoup of a group $G$. For any fixed element $x\in G$, the left coset of $H$ with respect to $x$ is the set $xH=\{xh\in G\mid h\in H\}$.
Note. For abelian groups with additive notation, right and left cosets are instead denoted by $H+x$ and $x+H$, respectively.
So basically a coset is a set obtained by taking the elements of a subgroup and adding a particular element to all of them. Note that a coset does need not be a subgroup! To get a feeling for what cosets really are and how they behave, let's look at an example.
Example. Take $G=\Z$, the additive group of integers, and $H=2\Z$, the set of even integers. Certainly $2\Z$ is a subgroup of $Z$ because it contains the identity $0$, the sum of two even integers is even, and every even integer has an even inverse — its negative.
Let's look at a few cosets of $2\Z$. How about the right cosets with respect to $0,1,2$ and $3$? Notice that because $\Z$ is an additive group, these cosets will be written $2\Z+0$, $2\Z+1$, $2\Z+2$ and $2\Z+3$.
Directly from the definition of a right coset, we see that
$$\begin{align}
2\Z+0 &= \{x+0\in\Z\mid x\in 2\Z\} \\
&= \{x\in\Z\mid x\in 2\Z\} \\
&= 2\Z.
\end{align}$$So in this case, the coset with respect to $0$ is just the subgroup $2\Z$. This actually always happens, as you can easily see. Adding the identity to all elements of a subgroup will of course just yield that subgroup again!
Next, let's look at $2\Z+1$. This is the set $\{x+1\in\Z\mid x\in 2\Z\}$, which consists of things like $\ldots,-3,-1,1,3,5,\ldots$. This is really just the set of odd integers! It's definitely not a subgroup of $\Z$ though, since it doesn't contain $0$.
The coset $2\Z+2$ is the set $\{x+2\in\Z\mid z\in 2\Z\}$, which contains elements like $\ldots,-4,-2,0,2,4,\ldots$. But this is the set of even integers again! That means $2\Z+2=2\Z$.
Lastly, let's look at $2\Z+2$. This is the set $\{x+3\in\Z\mid z\in 2\Z\}$, which contains things like $\ldots,-3,-1,1,3,5,\ldots$. We've already seen that somewhere before. It's just the set of odd integers again. That is, $2\Z+3=2\Z+1$.
It looks like there might actually only be two distinct cosets of $2\Z$. They are $2\Z$ itself and $2\Z+1$. Furthermore, every element of $\Z$ is in either one coset or the other, but never both (because an integer is either even or odd). So these cosets actually partition $\Z$, which is a very important point. But let's not get too far ahead of ourselves.
The first thing I'd like to prove about cosets is fairly simple — if we are working in an abelian group, left and right cosets are the same!
Theorem. If $H$ is a subgroup of an abelian group $G$, then $H+x=x+H$ for every $x\in G$.
Proof. We will proceed by demonstrating that each side is a subset of the other.
We show first that $H+x\subseteq x+H$. Choose $g\in H+x$, so that $g=h+x$ for some $h\in H$. Since $G$ is abelian, $h+x=x+h$ and thus $g=x+h\in x+H$. It follows that $H+x\subseteq x+H$.
The proof that $x+H\subseteq H+x$ is completely analogous to the above, so we won't bother with it. We can thus conclude that $H+x=x+H$.
This implies, for instance, that we could instead write $1+2\Z$ to denote the odd integers, but to me this doesn't look right for some reason and so I usually don't. In fact, for most of our purposes we really only need to consider one variety of coset. I tend to favor right cosets.
Now it's time to prove my suspicion from the above example. This is important, so pay close attention. If you don't remember what a partition is, I advise you to read my earlier post about them.
Theorem. If $H$ is a subgroup of a group $G$, then the (left/right) cosets of $H$ partition $G$.
Proof. We will prove the result for right cosets, since the proof for left cosets is practically identical.
It is clear that every coset $Hx$ is nonempty because the identity element $e$ is in $H$ by virtue of it being a subgroup, and thus $x=ex\in Hx$.
The next thing we need to show is that cosets cover all of $G$. But is clear that $$\bigcup_{x\in G}x=G\subseteq\bigcup_{x\in G}Hx,$$
and similarly that $$\bigcup_{x\in G}Hx\subseteq G=\bigcup_{x\in G}x,$$
because $Hx\subseteq G$ for every $x\in G$. Thus, $G=\bigcup_{x\in G}Hx$.
The last thing we need to show is that for any $x,y\in G$, if $Hx\ne Hy$ then $Hx\cap Hy=\varnothing$. That is, either cosets are the same or they are disjoint. We will argue the contrapositve, supposing that $Hx\cap Hy$ is nonempty. Then there exists some element $a\in Hx\cap Hy$. That is, $a\in Hx$ and $a\in Hy$, so $a=h_1x$ and $a=h_2y$ for some elements $h_1,h_2\in H$. It follows that $h_1x=h_2y$, and multiplication on the left by $h_1^{-1}$ show that $x=h_1^{-1}h_2y\in Hy$ because $h_1^{-1}h_2\in H$. Thus $Hx=Hy$, completing the proof.
This is pretty exciting! It means that we can form an equivalence relation $\sim$ on any group $G$, where elements are equivalent if they are in the same coset of $H$. Moreover, we can form the quotient set $G\quotient{\sim}$, whose elements are precisely the cosets of $H$. For simplicity, we generally write $G/H$ instead of to denote this quotient set, since it is so very important that we are talking about the set of cosets of $H$. We'll revisit this special type of quotient set in my next post.
Lagrange's Theorem
We're actually very close to proving this famous theorem already. We just need one lemma first:
Lemma. If $H$ is a subgroup of a group $G$ and $x\in G$, there exists a bijection $f:G\to Hx$.
Proof. We define a function $f:H\to Hx$ by $f(h)=hx$ for every $h\in H$. That is, the function that maps every element of $H$ to its product with $x$. Clearly $f$ is injective because if $f(h_1)=f(h_2)$ then $h_1x=h2_x$ and the right cancellation law yields $h_1=h_2$. Furthermore, $f$ is surjective because for any $y\in Hx$ we have by definition that $y=hx$ for some $h\in H$, and thus $y=f(h)$. It follows that $f$ is bijective, as desired.
Recall that a bijection exists between finite sets only if those sets contain the same number of elements. This fact, along with the lemma above, tells us that all cosets of a subgroup are the same size! We are now ready to prove Lagrange's Theorem, which is actually very easy at this point.
Lagrange's Theorem. If $H$ is a subgroup of a finite group $G$, then $\abs{G}$ is a multiple of $\abs{H}$.
Proof. We have already established that every coset of $H$ contains the same number of elements, $\abs{H}$. Since $G$ is finite, there are a finite number of distinct cosets of $H$, say $n$ of them. Because these cosets partition $G$, it follows that $\abs{G}=n\abs{H}$, completing the proof.
This is probably somewhat surprising unless you're already familiar with groups. But it's just part of the astonishing usefulness of cosets. Lagrange's Theorem is actually incredibly useful because it tells us instantly that certain things cannot be subgroups of other things. For instance, a group of order $12$ cannot ever have subgroups of order $5,7,8,9,10$ or $11$. Without this theorem, you might have guessed that this was the case, but it would have been pretty tricky to prove it conclusively.