## MaBloWriMo 13: Elements of finite groups have an order

Recall from yesterday that if $G$ is a group and $g \in G$ is some element of the group, the order of $g$ is defined as the smallest number of copies of $g$ which combine to yield the identity element. I forgot to mention it yesterday, but we usually write $|g|$ to denote the order of $g$ (and likewise $|G|$ denotes the order (aka size) of the group $G$). Today we are going to answer the question:

1. 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 $g \in G$ such that combining $g$ with itself will never yield the identity element; in other words, as long as $G$ is finite, if you keep combining more and more copies of $g$ 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 $g^2$ for $g$ combined with itself, $g^3$ for $g$ 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 $g^n$ with a specific group where the operation is some sort of addition, such as $\mathbb{Z}_n$ (for example you end up with monstrosities like $3^2 = 3 +_8 3 = 6$). To avoid confusion, we’ll only use the notation $g^n$ in a general setting, i.e. when proving things about all groups, not when talking about a specific group. Just remember that $g^n$ does not mean exponentiation, it just means $g \odot \dots \odot g$ with $n$ copies of $g$, where $\odot$ is whatever the group operation happens to be.

Let $G$ be a finite group and suppose $g \in G$. Now consider the infinite sequence of values

$g, g^2, g^3, g^4, \dots$

All the values in this infinite list are elements of the finite set $G$—so the list must have (many!) duplicates. Pick just one such pair of duplicate values, say, $g^j = g^k$ for some $j < k$. Now, according to the laws of a group, $g$ must have some inverse element $g^{-1}$ such that $g^{-1} \odot g = e$ (where $e$ is the identity). Doing the same thing to both sides of an equation results in another valid equation, so we conclude that

$g^{-1} \odot g^j = g^{-1} \odot g^k$

But

$g^{-1} \odot g^j = g^{-1} \odot (g \odot g^{j-1}) = (g^{-1} \odot g) \odot g^{j-1} = e \odot g^{j-1} = g^{j-1}$.

(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 $g^{-1}$ for the inverse of $g$—because it works just like we expect superscript notation to work, like exponents.) Similarly, $g^{-1} \odot g^k = g^{k-1}$. That is, the $g^{-1}$ cancels with one copy of $g$ on each side, leaving us with one fewer. We can keep doing this $j$ times, until all the $g$s on the left side are gone, leaving us with

$e = g^{k-j}$.

But look! This equation says that if you combine $g$ with itself $k-j$ times, you get the identity. $k-j$ might not be the smallest such number, but we can definitely say that the order of $g$ is at most $k-j$—and in particular the order of $g$ has to be finite. In other words, we have shown that the group laws force $e$ to show up somewhere in the list $g, g^2, g^3, g^4, \dots$.

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 $a \odot a = a$, so $a$ does not have a finite order.)

The second question we wanted to answer is:

1. 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 $g$ of a group $G$, it is the case that $|g| \leq |G|$, that is, the order of $g$ is no larger than the size of the group. Can you see why this must be true?