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
    Wouldn't it be better to use superscripts, $f^j$ instead of $f_j$ for the $j$-fold iteration of a function?2012-05-07
  • 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|$.

  • 1
    Gerry's answer is much more elementary.2012-05-07
  • 0
    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??2012-05-07
  • 0
    The cyclic subgroup generated by f contains the inverse of f.2012-05-07
  • 0
    @Katie, that's what [Pete Clark](http://math.stackexchange.com/users/299/pete-l-clark) calls *Lagrange's Little Theorem*: in a finite group of order N, we have $x^N=1$ for every $x$.2012-05-07
  • 0
    @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?)2012-05-07
  • 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$.