Permutations and Equivalence Relations Let X be a nonempty set and let $\sigma \in$ Sym(X). Define the two place relation $\sim$ on X as follows: 
x$\sim$y if and only if $\sigma^{k}(x)=y$ for some integer k. 
Prove that $\sim$ is and equivalence relation.
I know that Sym(X) is the set of onto maps from X to X. Since the function is onto than it has an inverse. Also my professor said something about on Z the formation of a negative is a permutation and how it fixes 0 and maps 1 to -1 and so on. How do I get started on this?
 A: To prove that this is an equivalence relation you need to show three things:


*

*Reflexivity: For every $x\in X$, $x\sim x$, that is there is some $k$ such that $\sigma^k(x)=x$. Recall that if $f\colon A\to A$ is a function on some set $A$ then $f^0(a)=a$.

*Symmetry: For every $x,y\in X$ if $x\sim y$ then $y\sim x$, that is if there is some $k$ such that $\sigma^k(x)=y$ then there is some $n$ such that $\sigma^n(y)=x$. Recall that $(\sigma^k)^{-1}=\sigma^{-k}$ and deduce that $-k$ witnesses the symmetry of the relation.

*Transitivity: For every $x,y,z\in X$ if $x\sim y$ and $y\sim z$ then $x\sim z$. For this recall that $\sigma^k\circ\sigma^n=\sigma^{k+n}$ and as with the previous properties, deduce the transitivity of $\sim$.
A: HINT: For each $\sigma\in\operatorname{Sym}(X)$, $\sigma^{-1}$ is also a permutation of $X$, and $y=\sigma^k(x)$ if and only if 
$$\left(\sigma^{-1}\right)^k=\left(\sigma^k\right)^{-1}(x)=\left(\sigma^k\right)^{-1}\left(\sigma^k(x)\right)=x\;.$$
This is what you need to prove symmetry of $\sim$. Reflexivity is easy: the identity map $x\mapsto x$ is a permutation of $X$. For transitivity, you must prove that if $\sigma,\tau\in\operatorname{Sym}(X)$, then $\sigma\circ\tau\in\operatorname{Sym}(X)$.
