# Bijection proof

I got this on an exam and struggled to complete it, could anyone offer a proof? Thanks!

Let $X$ be a finite set. Let $f: X \longrightarrow X$ be a bijection. For $n \in \mathbb{Z}^+$, set $$f^n = \underbrace{f \circ f \circ \cdots \circ f}_{n \text{ times}}.$$

Prove that there exists $m \in \mathbb{Z}^+$ such that $f^m = \mathrm{Id}_X$.

There are finitely many bijections, so you must have $f_j=f_k$ for some $j\lt k$. Then consider $f_{k-j}$.

• Wouldn't it be better to use superscripts, $f^j$ instead of $f_j$ for the $j$-fold iteration of a function? – Michael Hardy May 7 '12 at 18:28
• @Michael, yes. When I answered the question, it had not been posted in TeX, and it had fm and fn. On that shaky basis, I thought OP would be more comfortable with $f_m$ than with $f^m$. Perhaps I should have used $f^m$ anyway. If it bothers you, feel free to edit. – Gerry Myerson May 8 '12 at 3:33

Hint: If you wanted to prove that there exists $m\in\mathbb{N}$ such that $f^m (x)=x$ for just one $x\in X$, how would you do it (remember that $X$ is finite)? Next, repeat the argument with $f^m$ taking the place of $f$ (remember that $(f^m)^n=f^{mn}$). An easy induction on the number of elements in $X$. For me, this is the easiest way to see it.

HINT:

1. For each $n$, $f^n=\underbrace{f\circ f\circ\ldots \circ f}_{n}$ is a bijection from $X$ to $X$.
2. Are there infinitely many bijections from a finite set to itself?
3. Pigeonhole principle.

A simple proof is to use Lagrange's theorem: the set of bijections $X\to X$ is a finite group and hence $f^m=\operatorname{id}$ for say $m=n!$, where $n=|X|$.

• Gerry's answer is much more elementary. – lhf May 7 '12 at 0:44
• In my exam i got to the point where i figured out that there was a limited number of bijections n! but how do you skip from there to the fact that f^m=id?? – Katie May 7 '12 at 0:51
• The cyclic subgroup generated by f contains the inverse of f. – Shahab May 7 '12 at 0:57
• @Katie, that's what Pete Clark calls Lagrange's Little Theorem: in a finite group of order N, we have $x^N=1$ for every $x$. – lhf May 7 '12 at 1:01
• @lhf: Thanks for the plug. Actually though I reserve LLT for the case of a finite commutative group, because in this case one really can carry over the argument from the standard proof of Fermat's Little Theorem. So far as I know -- and I think we've had a good discussion of this point on this site -- there is not a similarly easy combinatorial proof in the non-commutative case. (Right?) – Pete L. Clark May 7 '12 at 4:25

$$x, f(x), f(f(x)), f(f(f(x), \ldots$$ This list cannot go on forever, since $X$ is finite. So it must reach one that has appeared in the list earlier. Suppose $$f(f(f(f(f(f(f(x))))))),$$ the seventh one, appeared earlier as the third one. Then $$f(f(f(x))) = f(f(f(f(f(f(f(x))))))).$$ Since $f$ is one-to-one, we can cancel: $$x = f(f(f(f(x)))).$$ But that doesn't mean $f\circ f\circ f\circ f$ is the identity. It only means that if you apply it to this one element, $x$, you get back $x$, NOT that if you apply it to every element $y$, you'll get back $y$.

So suppose $x$ re-appears in four steps $$x \mapsto f(x) \mapsto f(f(x)) \mapsto f(f(f(x))) \mapsto f(f(f(f(x))))$$ and some other element, $w$, re-appears in six steps: $$f(f(f(f(f(f(w)))))) = w.$$ The smallest common multiple of $4$ and $6$ is $12$, so after $12$ steps, both $w$ and $x$ will re-appear simultaneously.

There are finitely many elements of $X$. Find the smallest common multiple of the numbers of steps it takes to get them to re-appear. After that many steps, the all re-appear simultaneously. So $f$ iterated that many times is the identity function on $X$.