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.
This entry was posted in algebra, group theory, proof and tagged , , , , , , . Bookmark the permalink.