# 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?

-

## 2 Answers

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)$.

-
Oh snap. Just one second! :-) – Asaf Karagila Feb 4 '13 at 0:06
@Asaf: I think that counts as simultaneous. (Evidently this simultaneity isn’t an equivalence relation. :-)) – Brian M. Scott Feb 4 '13 at 0:08

To prove that this is an equivalence relation you need to show three things:

1. 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$.

2. 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.

3. 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$.

-
does your point 2 apply if k has to be >= 0 ? – Angelo.Hannes Apr 22 '13 at 13:30
@Angelo: Only if $\sigma$ is the product of finite cycles. Consider $X=\Bbb Z$ and $\sigma(x)=x+1$, if we require $k\geq 0$ then $-1\sim 0$ but it is impossible for $0\sim -1$, because no matter how many times you apply $\sigma$ on $0$ you will never get a negative integer. – Asaf Karagila Apr 22 '13 at 13:35