Took me a long time to figure out what you meant by o(f), but I believe you mean the order. I've always see order denoted as |f|.
This is an incredibly useful theorem if you ever deal with computational group theory!
So, consider f^r. That is, (x1,x2,...,xr)(x1,x2,...,xr)...(x1,x2,..… r times.
This is really a composition of mappings. In other words, f: x1 -> x2.
For the first function, we get f: x1 -> x2.
For the second, we get f: x2 -> x3.
We repeat this process. We see that the kth application of the function maps xk to x(k+1) (if need be, you can prove this by induction)
The rth application would then take xr -> x(r+1), but there is no x(r+1), so it loops around from xr to x1.
Therefore, an rth application will map x1 -> x1, x2 -> x2, etc.
Thus, we know that f^r = e. So, we know that r is a multiple of the order of f.
Suppose h is a natural number such that h < r and f^h = e, the identity element.
This would apply h applications of the function f to x1, for instance.
Therefore f^h: x1 -> x(h+1)
But since there are r elements in (x1,x2,...,xr) and h < r, the only way for h + 1 < r +1, but r + 1 leads us to 1.
Therefore, f^h cannot be e.
Since f^r = e, and there is no h < r such that f^h = e, we know that r is the order of f.
This is an incredibly useful theorem if you ever deal with computational group theory!
So, consider f^r. That is, (x1,x2,...,xr)(x1,x2,...,xr)...(x1,x2,..… r times.
This is really a composition of mappings. In other words, f: x1 -> x2.
For the first function, we get f: x1 -> x2.
For the second, we get f: x2 -> x3.
We repeat this process. We see that the kth application of the function maps xk to x(k+1) (if need be, you can prove this by induction)
The rth application would then take xr -> x(r+1), but there is no x(r+1), so it loops around from xr to x1.
Therefore, an rth application will map x1 -> x1, x2 -> x2, etc.
Thus, we know that f^r = e. So, we know that r is a multiple of the order of f.
Suppose h is a natural number such that h < r and f^h = e, the identity element.
This would apply h applications of the function f to x1, for instance.
Therefore f^h: x1 -> x(h+1)
But since there are r elements in (x1,x2,...,xr) and h < r, the only way for h + 1 < r +1, but r + 1 leads us to 1.
Therefore, f^h cannot be e.
Since f^r = e, and there is no h < r such that f^h = e, we know that r is the order of f.
-
Join the physicist team. When we read advanced math books (abstract algebra, analysis, etc), we read the theorems and skip the proofs