Relation of equivalency $f^n(x)=f^m(y)$

Question

Lets consider a set $X$ and the relation $\Re$ defined in the following way: $x\Re y\Leftrightarrow \exists n,m\in \mathbb{N}, f^{n}(x)=f^{m}(y)$ $f^{n}=$identity if $n=0$ else $f^{n}=f•f^{n-1}$. Can you show that $\Re$ is a relation of equivalency?

Answer 1

We want to show that the relation $\sim$ defined by $x\sim y \iff $there exists $(m,n)\in\mathbb N_0^2$ such that $f^m(x)=f^n(y)$ ($\mathbb N_0$ are the natural numbers alongwith $0$) is an equivalence relation.

• Reflexivity

Since $f(x)=f(x)$, choosing $(m,n)=(1,1)$ shows that $x\sim x$.

• Symmetricity

Suppose $x\sim y$. Then there exists $(m,n)$ such that $f^m(x)=f^n(y)$. But this implies that $f^n(y)=f^m(x)$ and hence choosing $(n,m)$ shows that $y\sim x$.

• Transitivity

Suppose $x\sim y$. Then there exists $(a,b)$ such that $f^a(x)=f^b(y)$. Now suppose further that $y\sim z$. Then there exists $(c,d)$ such that $f^c(y)=f^d(z)$.

Now let $l=\text{lcm}(b,c)$. Then $\lambda_1b=l=\lambda_2c$ for some $\lambda_1,\lambda_2$ by definition of lcm. Then we have that $$f^{\lambda_1a}(x)=f^{\lambda_1b}(y)=f^l(y)$$ $$f^l(y)=f^{\lambda_1c}(y)=f^{\lambda_1d}(z)$$

and hence $f^{\lambda_1a}(x)=f^{\lambda_2d}(z)$ and hence choosing $(\lambda_1a,\ \lambda_2d)$, we have that $x\sim z$.

Thus the relation is an equivalence relation.

---

In fact we can dispense off with the whole lcm business. Since we have $f^a(x)=f^b(y)$, this implies that $f^{ac}(x)=f^{bc}(y)$. Similarly $f^c(y)=f^d(z)\Rightarrow f^{bc}(y)=f^{bd}(z)$ and thus we get $f^{ac}(x)=f^{bd}(z)$ and by choosing $(ac,bd)$, we can show transitivity.