Let $f \colon X → X$ be an injective function.
For $y, z ∈ X$, define $y \sim z$ to mean there
exists an integer $n ≥ 0$ such that either $f^n(z) = y$ or $f^n(y) = z$. (Here $f^0(z) = z$ for all $z ∈ X$.)
Prove this is defines an equivalence relation on $X$.
Give a list of the different possibilities for the
resulting equivalence classes
My attempt: Proving it was an equivalence relation was simple as it involved only using definitions of the function, but I have no idea what the equivalence classes must be.
Best Answer
The question is asking for various possibilities for the equivalence classes. So
1). If $x \in X$ is a fixed point of the function i.e. $f(x)=x$, then $[x]=\{x\}$. Due to injectivity, no other element will map to $x$, so it is the only member in it’s class.
2). If there exists a finite sequence $x_1, x_2, \ldots ,x_k$, such that $f(x_i)=x_{i+1}$ and $f(x_k)=x_1$. Then $[x_1]=\{x_1, x_2, \ldots ,x_k \}$.
3). Other possibility is to have infinite orbits.