Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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


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

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.