Prove that there exists some positive integer $X_m=X_0$ given that a function is injective

Question

Let $A$ be a finite set. Let $f:A\to A$ be an injective function from the set $A$ to itself and let $x_0$ be an element of $A$. Let $x_n$ be defined for all positive integers $n$ so that $x_n=f(x_{n-1})$ for all positive integers $n$. Prove that there exists some positive integer $m$ such that $x_m=x_0$.

Now a function is said to be injective when there is a one to one mapping. When $f : A \to A$, it means that for any element $x$ in $A$, it maps to a distinct element $y$ in $A$.

Now applying the function $x_n=f(x_{n-1})$ if $n =1$, then the function would give a result $x_0$.

The question is how do i prove this even thou i have show that there exists some positive integer which in this case is $1$

Answer 1

Here’s an outline of the proof.

You start with $x_0\in A$ and keep applying the function $f$ to get $x_1=f(x_0)$, $x_2=f(x_1)=f\big(f(x_0)\big)$, and so on. This generates a sequence $\langle x_0,x_1,x_2,\dots\rangle$ of elements of $A$.

Now prove by induction on $n$ that if $x_0,x_1,x_2,\dots,x_n$ are all distinct elements of $A$, then $$x_{n+1}=f(x_n)\notin\{x_1,\dots,x_n\}\;;$$ use the fact that $f$ is injective. From this you can conclude that either $x_{n+1}=x_0$, in which case you’re done, or $x_0,x_1,x_2,\dots,x_n,x_{n+1}$ are all distinct elements of $A$, and the induction can continue. Since $A$ is finite, it must stop at some point, and at that point you have your desired $m$.