Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

5 Answers 5

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

share|improve this answer
    
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
add comment

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.
share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
1  
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
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.