Composition of permutations is an equivalence relation

Question

For a permutation $p : X \rightarrow X$, let $p_k$ denote the permutation arising by a $k$-fold composition of $p$, i.e. $p^1 = p$ and $p^k = p \circ p^{k−1}$ . Define a relation $\approx$ on the set $X$ as follows: $i \approx j$ if and only if there exists a $k \geq 1$ such that $p^k (i) = j$. Prove that $\approx$ is an equivalence relation on $X$, and that its classes are the cycles of $p$.

An equivalence relation is reflexive, transitive and symmetric.

Reflexivity

$\forall(i) \in X$ we must have $(i, i) \in \approx$ This is true by definition, as $p^1=p$, so we have for every $i,i \in X$ $p^1(i) = i$.

Symmetry $\forall (x,y) \in \approx$ we must have $(y,x) \in \approx$ This means whenever $p^k (i) = j$, then $p^k (j) = i$.

Transitivity ?

Several questions:

1. is reflexivity correct?
2. in my symmetry case, can $k$ be different for $(x,y)$ and $(y,x)$?
3. how to handle transitivity? I can write out the definition, but not sure how to follow

Please give hints, not full solutions if possible.

Answer 1

1. Your proof of reflexivity is not correct. $p(i)$ is not necessarily $i$. However, notice that, if $i$ is a member of a cycle of length $n$ in $p$, then $p^n(i)=i$. There may be no infinite cycles in finite sets.
2. $k$ can be different for $(x,y)$ and $(y,x)$ - symmetry would be the property that there exist $$\exists k_1[p^{k_1}(i)=j]\Leftrightarrow \exists k_2[p^{k_2}(j)=i]$$ or, in words, "If applying $p$ some number of times will take $i$ to $j$, then by applying $p$ some more, we can get $j$ back to $i$"
3. Notice that $p^{k_2}(p^{k_1}(i))=p^{k_1+k_2}(i)$ - that is, applying $p$ first $k_1$ times, then $k_2$ times is the same as applying it $k_1+k_2$ times. Thus, if you have that $$p^{k_1}(i)=j$$ $$p^{k_2}(j)=k$$ what is $p^{k_1+k_2}(i)$?