Let $f:X \to X$ be an injective function from a set $X$ into itself. Define a sequence of functions $f^0 , f^1, f^2, \dots : X \to X$ by letting $f^0 = \mathrm{id}$, $f^1 = f$ and $f^n = f(f^{n-1}(x))$. Prove that each of these functions is injective. Let $R$ be the subset of $X \times X$ consisting of those pairs $(a,b)$ such that $b = f^k (a)$ for some integer $k$ or $a= f^j (b)$ for some integer $j$. Prove that $R$ is an equivalence relation.
My work:
$f^n$ is injective. Proof by induction over $n$. Clearly, $f^0$ and $f^1$ are injective. Assume $f^{n-1}$ is injective. Then $f^n$ is injective since the composition of injective functions is an injective function.
$R$ is an equivalence relation. Clearly, $x \sim x$ since $x = f^0 (x)$. Also, if $f^k (x) = y$ then $f^{-k}(y) = x$ hence $y \sim x$. Finally, if $f^k(x) = y$ and $f^i(y) = z$ then $f^{i+k}(x) =z$.
Please correct me if I'm wrong. Thank you for correcting me!!
The first half of the proof is correct, and so is the proof of reflexivity.
In the second and third part, there is a problem: The definition of $\sim$ states that $x \sim y$ iff $x = f^{k}(y)$ or $y = f^{j}(x)$, but you only consider the first case. Also, you use the expression $f^{-k}$, which is not defined.
Hint for the symmetry proof: Write down the condition for $x \sim y$ and for $y \sim x$. Then, note that $P \vee Q$ iff $Q \vee P$ for any two propositions $P,Q$.
Hint for the transitivity proof: Do a case analysis.