# 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 at 0:06
@Asaf: I think that counts as simultaneous. (Evidently this simultaneity isn’t an equivalence relation. :-)) – Brian M. Scott Feb 4 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 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 at 13:35
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 44, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9258007407188416, "perplexity_flag": "head"}