# Proof that a function is injective with special condition

Condition: A is a finite set, $$f:A \rightarrow A$$,and we know that $$f_i(a)=f(f_{i-1}(a))$$ with $$f_0(a)=a$$.

Proof that if there exist a $$i_0$$ with $$f_{i_0}(a)=f_0(a)$$ then f is injective.

I have no idea what to do. At first I thought that I could begin with $$f(a)=f(b)$$ and write that as $$f(f_0(a))=f(f_{i_0}(a))$$ but I think that's not useful. Could someone give me a hint?

• Since $f_{i_0-1}\circ f=f_{i_0}={\rm id}_A$ is injective, so is $f$. Commented Jul 31 at 20:27
• @AnneBauval Thank you very much! Sorry that I asked such a question Commented Jul 31 at 20:29
• Does the condition hold for all $a$? And if so, does $i_0$ depend on $a$? Commented Jul 31 at 20:31
• @JensSchwaiger Yes for all a and $i_0$ is independent. Commented Jul 31 at 20:32
• @AnneBauval I'm not sure about your solution. Isn't $f\circle\f_{i_0-1}=f_{i_0}$ Could you maybe explain it to me? Thank you for your great help! Commented Jul 31 at 20:43

Consider more generally, as suggested by @JensSchwaiger, for some (possibly infinite) set $$A$$, a function $$f:A\to A$$ such that for every $$a\in A$$, there exists an integer $$n_a\ge1$$ such that $$f_{n_a}(a)=a$$.
Note that by construction, $$f_n=f^n:=f\circ f\circ\dots\circ f$$ ($$n$$ times), the $$n$$-th iterate of $$f$$.
The relation $$\sim$$ on $$A$$ defined by $$x\sim y\iff\exists k\ge0\quad y=f^k(x)$$ is obviously reflexive and transitive. Using the specific hypothesis on $$f$$, one easily shows that $$\sim$$ is also symmetric.
Now, if $$c:=f(a)=f(b)$$ then $$a\sim c\sim b$$, so that $$a$$ and $$b$$ belong to the "orbit of $$c$$", namely to $$O:=\{c,f(c),f^2(c),\dots,f^{n_c-1}(c)\}$$. The restriction $$f_{|O}$$ of $$f$$ to $$O$$ satisfies $$(f_{|O})^{n_c}={\rm id}_O$$. Therefore, $$(f_{|O})^{n_c-1}\circ f_{|O}$$ is injective, hence so is $$f_{|O}$$, whence the desired conclusion: $$a=b$$.