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.

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$

share|improve this question
    
@Brian ..A is a finite set .I have updated it.I am not sure if my prove is good enough –  Jack welch Jan 7 '13 at 2:42
    
    
No, you don’t necessarily get $f(x_1)=x_0$; you get $x_1=f(x_0)$. –  Brian M. Scott Jan 7 '13 at 2:48

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

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.