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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →