# Equivalence relation function

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.

-
Thank you, I have symmetry: $$x \sim y \iff (f^k (x) = y) \lor (f^j (y) = x) \iff (f^k (x) = y) \lor (f^j (y) = x) \iff y \sim x$$ But why is my proof of transitivity incorrect? –  Visitor Feb 7 '13 at 13:25
I get it. Thanks. –  Visitor Feb 7 '13 at 13:26
Assume $x \sim y$ and $y \sim z$. Then (1) $f^k(x) = y$ or (2) $f^j(y) = x$ and either (3) $f^n(y) = z$ or (4) $f^m(z) = y$. If (1) and (3), $f^{n+k}(x) = z$. If (1) and (4), wlog $m>k$. Then since $f^k(x) = f^m (z)$ it follows that $f^{m-k}(z) = x$. If (2) and (3), then wlog $n>j$. Then $f^{n-j}(x) = z$. If (2) and (4), then $f^{m+j}(z) = x$. –  Visitor Feb 7 '13 at 13:37
Looks good. Of course, you could also define $f^{-k}(x) = y$ to mean $f^k(y) = x$. This would spare you the explicit case analysis, but it's actually the same proof in a different notation. –  Johannes Kloos Feb 7 '13 at 15:15