2
$\begingroup$

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$.

5 Answers 5

6

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

  • 0
    @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.2012-05-08
3

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.

2

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|$.

  • 0
    @PeteL.Clark, ah, ok, yes, the abelian case has it's own nice proof, probably the one Fermat and Euler used, and certainly the first one I learned in number theory. Yes, we've had this conversation before. I still wish I knew a nice proof in the nonabelian case: http://math.stackexchange.com/questions/28332/is-lagranges-theorem-the-most-basic-result-in-finite-group-theory2012-05-07
2

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.
1

$ 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$.