So in the remainder of the month, we’ll prove that in any group , the order of each element
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 is a group, then
is a subgroup of
(written
) when
- The set of elements of
is a subset of the set of elements of
, and
is also a group, under the same binary operation as
.
If then you can think of
as a group “hiding inside” a bigger group
.
Given some subset of the elements of
, to see whether
forms a subgroup we need to check just three things:1
is nonempty.
is closed under the binary operation. This is a rather special property: if you pick any old subset of the elements of
, chances are that combining two elements from your subset might result in something outside the subset (though of course it will still be in
).
- The inverse of any element of
is also in
. This is a special property too, for the same reason.
We don’t need to recheck associativity, since uses the same binary operation as
. Note also that we don’t need to check whether
has an identity element, since this is already implied by (1), (2) and (3): since
is nonempty by (1), choose some
. Then by (3),
too, then by (2),
is also in
. (Previously I’ve been using
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
instead of
. This is standard group theory notation.)
Let’s see some examples. Remember the example group , which consists of the numbers
through
, with a binary operation of addition
. Let’s first consider the subset
. Is this is a subgroup of
? No, it isn’t: it’s not closed under the binary operation. For example,
which is not in the subset.
, on the other hand, is indeed a subgroup of
. 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
always results in an even number again), and the inverse of each element is in the set (
and
are their own inverses, and
and
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 . There is one more—can you find it?
Now we can state Lagrange’s Theorem: if is a subgroup of
, then the order of
evenly divides the order of
.
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 is a subgroup of
:
- Define some subsets of
called the left cosets of
, and show that they all have the same size as
.
- Define (and prove) a certain equivalence relation on elements of
, defined in terms of
.
- 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
. Conclude that since every coset of
is the same size, and they partition
, their common size (that is, the size of
) must evenly divide the size of
. This will conclude the proof of Lagrange’s Theorem.
- In the final post, we will define the cyclic subgroup generated by an element
and show that the order of this subgroup is the same as the order of
—hence by Lagrange’s Theorem the order of
must divide the order of
.
Onward!
-
This is usually called the two-step subgroup test (there are, of course, three conditions, but the condition that
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
being nonempty, requires only that
for every
. It is a nice exercise in basic group theory to prove that this is equivalent.↩
Pingback: MaBloWriMo 29: Equivalence classes are cosets | The Math Less Traveled