## MaBloWriMo 29: Equivalence classes are cosets

Today will conclude the proof of Lagrange’s Theorem! Recall that we defined subgroups and left cosets, and defined a certain equivalence relation on a group $G$ in terms of a subgroup $H$. Today we’re going to show that the equivalence classes of this equivalence relation are precisely the left cosets of $H$. Since, as we saw yesterday, the equivalence classes of an equivalence relation always partition the entire set, this will mean that the left cosets of a subgroup $H$ partition the entire group $G$. (Did you notice this when working out the cosets of $\{0,4\}$ in $\mathbb{Z}_8$?) But we also know that all the cosets have the same size (namely, the size of the subgroup). This means that the cosets of $H$ carve up $G$ precisely into a bunch of equal-size parts—so the size of the parts, that is, the size of $H$, must evenly divide the size of $G$. Otherwise there would either have to be some elements of $G$ left over, or some of the parts would have to overlap, but those things can’t happen with a partition.

So, let’s show that the left cosets of $H$ are exactly the same as the equivalence classes of the equivalence relation $\sim_H$. Recall that by definition, $x \sim_H y$ if and only if $x = yh$ for some $h \in H$.

Let’s first explicitly note something which was implicit in yesterday’s post: if $\sim$ is an equivalence relation, then $x \sim y$ if and only if $x$ and $y$ are in the same equivalence class. To see this, first, if $x \sim y$, then both are in the equivalence class $[x]$ (which we know is also equal to $[y]$). Conversely, suppose $x$ and $y$ are in the same equivalence class, say, $[z]$. Then $z \sim x$ and $z \sim y$, and by symmetry and transitivity, $x \sim y$.

What this means is that in order to show equivalence classes of $\sim_H$ are the same as left cosets of $H$, we can prove the following:

$x \sim_H y$ if and only if $x$ and $y$ are in the same coset of $H$.

To prove an “if and only if” we have two directions to prove.

• In the forward direction, suppose $x \sim_H y$, so $x = yh$ for some $h \in H$, and thus also $y = xh^{-1}$. We have to prove that $x$ and $y$ are in the same coset of $H$, that is, there is some $a \in G$ such that $x, y \in aH$. Expanding the definition a bit more, this means we have to find $h_1, h_2 \in H$ so that $x = ah_1$ and $y = ah_2$. In fact, $x$ and $y$ are both in the coset $xH$: we can pick $h_1 = e$ and $h_2 = h^{-1}$, since $x = xe$ and $y = xh^{-1}$.
• In the backward direction, suppose $x$ and $y$ are both in the coset $aH$, so there are $h_1$ and $h_2$ such that $x = ah_1$ and $y = ah_2$. Then we have to show $x \sim_H y$, that is, $x = yh$ for some $h$. Well, $x = ah_1 = aeh_1 = a(h_2 h_2^{-1})h_1 = (ah_2)(h_2^{-1}h_1) = y(h_2^{-1} h_1)$, so the $h$ we are looking for is $h_2^{-1} h_1$.

So the cosets of $H$ all have the same size and partition $G$, which means their common size must evenly divide the size of $G$. Thus we have proved Lagrange’s Theorem: if $H \leq G$ then $|H|$ divides $|G|$.

We still haven’t quite proved what we originally set out to prove, namely, that the order of any element $g \in G$ divides $|G|$. If you want to try to prove it yourself before tomorrow, here’s a hint: can you take $g$ and use it to construct a subgroup of $G$, to which we could apply Lagrange’s Theorem? The full proof—and triumphant conclusion of MaBloWriMo—to come tomorrow!