Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!!

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


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.