Recall from yesterday that if is a group and is some element of the group, the order of is defined as the smallest number of copies of which combine to yield the identity element. I forgot to mention it yesterday, but we usually write to denote the order of (and likewise denotes the order (aka size) of the group ). Today we are going to answer the question:
- Does every element of a finite group have a well-defined, finite order?
It turns out that the answer is yes! It is not possible, in a finite group, to have an element such that combining with itself will never yield the identity element; in other words, as long as is finite, if you keep combining more and more copies of you will eventually get the identity element. The proof is really slick—in fact, for some reason that I can’t quite explain, this is one of my all-time favorite proofs.
First, some notation: write for combined with itself, for combined with itself three times, and so on. This notation works especially well when the group operation is some sort of “multiplication”, but as we have seen, that need not be the case. It can be a little confusing if you combine the notation with a specific group where the operation is some sort of addition, such as (for example you end up with monstrosities like ). To avoid confusion, we’ll only use the notation in a general setting, i.e. when proving things about all groups, not when talking about a specific group. Just remember that does not mean exponentiation, it just means with copies of , where is whatever the group operation happens to be.
Let be a finite group and suppose . Now consider the infinite sequence of values
All the values in this infinite list are elements of the finite set —so the list must have (many!) duplicates. Pick just one such pair of duplicate values, say, for some . Now, according to the laws of a group, must have some inverse element such that (where is the identity). Doing the same thing to both sides of an equation results in another valid equation, so we conclude that
(Notice how we used both the identity law and the associativity law of a group. Notice also that this is why we use the notation for the inverse of —because it works just like we expect superscript notation to work, like exponents.) Similarly, . That is, the cancels with one copy of on each side, leaving us with one fewer. We can keep doing this times, until all the s on the left side are gone, leaving us with
But look! This equation says that if you combine with itself times, you get the identity. might not be the smallest such number, but we can definitely say that the order of is at most —and in particular the order of has to be finite. In other words, we have shown that the group laws force to show up somewhere in the list .
As you can see from the above proof, the thing that really makes this work is the requirement that every element have an inverse—it is really quite a strong requirement. Indeed, if you don’t require inverses, you are left with something called a monoid—just a set with an associative binary operation and an identity—and there are many examples of monoids with elements that have no finite order. (For example, remember how there is only one group with two elements? Well, there are two monoids with two elements—the other one has , so does not have a finite order.)
The second question we wanted to answer is:
- What is the relationship between the order of a group and the orders of its elements?
Using a slightly strengthened version of the above proof, we will show tomorrow that for any element of a group , it is the case that , that is, the order of is no larger than the size of the group. Can you see why this must be true?