MaBloWriMo 25: Subgroups

So in the remainder of the month, we’ll prove that in any group $G$ , the order of each element $g \in G$ must evenly divide the order (size) of the group. I said in an earlier post that this is called Lagrange’s Theorem; actually, my memory was a tad off and it turns out that Lagrange’s Theorem is slightly more general than this, but implies it as a fairly straightforward corollary.

Today, we need to define the concept of a subgroup. If $G$ is a group, then $H$ is a subgroup of $G$ (written $H \leq G$ ) when

The set of elements of $H$ is a subset of the set of elements of $G$ , and
$H$ is also a group, under the same binary operation as $G$ .

If $H \leq G$ then you can think of $H$ as a group “hiding inside” a bigger group $G$ .

Given some subset $H$ of the elements of $G$ , to see whether $H$ forms a subgroup we need to check just three things:¹

$H$ is nonempty.
$H$ is closed under the binary operation. This is a rather special property: if you pick any old subset of the elements of $G$ , chances are that combining two elements from your subset might result in something outside the subset (though of course it will still be in $G$ ).
The inverse of any element of $H$ is also in $H$ . This is a special property too, for the same reason.

We don’t need to recheck associativity, since $H$ uses the same binary operation as $G$ . Note also that we don’t need to check whether $H$ has an identity element, since this is already implied by (1), (2) and (3): since $H$ is nonempty by (1), choose some $a \in H$ . Then by (3), $a^{-1} \in H$ too, then by (2), $a a^{-1} = e$ is also in $H$ . (Previously I’ve been using $\odot$ to denote the binary operation of a group, but this is going to get tedious fast: from now on I will just omit writing an explicit symbol at all, and write $ab$ instead of $a \odot b$ . This is standard group theory notation.)

Let’s see some examples. Remember the example group $\mathbb{Z}_8$ , which consists of the numbers $0$ through $7$ , with a binary operation of addition $\pmod 8$ . Let’s first consider the subset $\{0,1,2,3\}$ . Is this is a subgroup of $\mathbb{Z}_8$ ? No, it isn’t: it’s not closed under the binary operation. For example, $2 +_8 3 = 5$ which is not in the subset.

$\{0,2,4,6\}$ , on the other hand, is indeed a subgroup of $\mathbb{Z}_8$ . It is obviously nonempty. We can check that combining any two elements of the set according to the binary operation lands us back in the set (adding two even numbers $\pmod 8$ always results in an even number again), and the inverse of each element is in the set ( $0$ and $4$ are their own inverses, and $2$ and $6$ are inverses).

Any group is trivially a subgroup of itself (the “subset” in the definition does not have to be a strict subset). Also, the group with a single element is a subgroup of any group. So we have found three subgroups of $\mathbb{Z}_8$ . There is one more—can you find it?

Now we can state Lagrange’s Theorem: if $H$ is a subgroup of $G$ , then the order of $H$ evenly divides the order of $G$ .

We’ll spend the rest of the month proving this. Here’s an outline for the rest of the proof, one blog post for each item below. (The proof will not actually take quite as long as I thought!) Supposing $H$ is a subgroup of $G$ :

Define some subsets of $G$ called the left cosets of $H$ , and show that they all have the same size as $H$ .
Define (and prove) a certain equivalence relation on elements of $G$ , defined in terms of $H$ .
Show that the equivalence classes of any equivalence relation form a partition.
Show that the equivalence classes for the equivalence relation we defined are exactly the left cosets of $H$ . Conclude that since every coset of $H$ is the same size, and they partition $G$ , their common size (that is, the size of $H$ ) must evenly divide the size of $G$ . This will conclude the proof of Lagrange’s Theorem.
In the final post, we will define the cyclic subgroup generated by an element $g \in G$ and show that the order of this subgroup is the same as the order of $g$ —hence by Lagrange’s Theorem the order of $g$ must divide the order of $G$ .

Onward!

This is usually called the two-step subgroup test (there are, of course, three conditions, but the condition that $H$ be nonempty is usually so trivial that it doesn’t count). There are other ways to check whether some subset is a subgroup, most notably the one-step subgroup test which, besides $H$ being nonempty, requires only that $ab^{-1} \in H$ for every $a, b \in H$ . It is a nice exercise in basic group theory to prove that this is equivalent.↩

About Brent

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

View all posts by Brent →