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 define the two place relation ~ as

$\sigma\sim\tau$ if and only if $\rho^{-1}\circ\sigma\circ\rho=\tau$ for some permutation $\rho$

For reflexivity this is what I have:

Let x$\in$X such that $(\rho^{-1}\circ\sigma\circ\rho)(x)=\sigma(x)$

Than $\rho^{-1}(\sigma(\rho(x)))=\sigma(x)$

So $\sigma(\rho(x))=\rho(\sigma(x))$

Therefore $\sigma(x)=\rho^{-1}(\rho(\sigma(x))$

So $\sigma(x)=\rho^{-1}(\sigma(\rho(x))$

Finally $\sigma(x)=\rho^{-1}\circ\sigma\circ\rho$

Does that show that the relation is reflexive?

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

It does not, I’m afraid. You’ve apparently misunderstood what you have to prove in order to show that $\sim$ is reflexive. You must show that if $\sigma$ is any permutation of $X$, then $\sigma\sim\sigma$, which means that there is some permutation $\rho$ of $X$ such that $\rho^{-1}\circ\sigma\circ\rho=\sigma$. This in turn means that for each $x\in X$, $(\rho^{-1}\circ\sigma\circ\rho)(x)=\sigma(x)$, i.e., that for each $x\in X$,


What if $\rho$ did nothing at all to each element of $X$, so that $\rho(x)=x$ for each $x\in X$? Then you’d have


And since $\rho$ does nothing, $\rho^{-1}$, which undoes $\rho$, must also do nothing, and we have


It works! If we take $\rho$ to be the identity permutation, sometimes written $1_X$, we have $1_X^{-1}\circ\sigma\circ 1_X=\sigma$, no matter which permutation of $X$ $\sigma$ might be. This shows that $\sigma\sim\sigma$ for each permutation $\sigma$ of $X$ and hence that $\sim$ is reflexive.

share|cite|improve this answer
If I let ρ(x)=x again then σ∼τ is ρ−1∘σ∘ρ=τ equals σ(x)=τ(x) and τ∼σ is ρ−1∘τ∘ρ=σ which equals τ(x)=σ(x). Does that show symmetry? – Gamecocks99 Feb 4 '13 at 1:59
@Gamecocks99: From the hypothesis that $\sigma\sim\tau$ you know only that $\rho^{-1}\circ\sigma\circ\rho=\tau$ for some permutation $\rho$: you have no idea what permutation $\rho$ is, and no control over it. However, you can show that if $\rho^{-1}\circ\sigma\circ\rho=\tau$, then $\rho^{-1}\circ\tau\circ\rho=\sigma$ and hence that $\tau\sim\sigma$; it doesn’t matter for this which permutation $\rho$ is. – Brian M. Scott Feb 4 '13 at 2:03
I've tried to show symmetry but I cant seem to get it. I'm not sure if I'm missing something. – Gamecocks99 Feb 4 '13 at 2:56
@Gamecocks99: My previous comment contains the whole proof of symmetry except the verification that if $\rho^{-1}\sigma\rho=\tau$, then $\rho\tau\rho^{\rho}=\sigma$. (Note that last equation: I typoed it in the previous comment.) To check that, apply $\rho$ on the left to $\rho^{-1}\sigma\rho=\tau$ to get $\sigma\rho=\rho\tau$, then apply $\rho^{-1}$ on the right to get $\sigma=\rho\tau\rho^{-1}$. Now realize that $\left(\rho^{-1}\right)^{-1}=\rho$, so $\sigma=\left(\rho^{-1}\right)^{-1}\tau\rho^{-1}$; $\rho^{-1}$ is a permutation of $X$, so by definition $\tau\sim\sigma$. – Brian M. Scott Feb 4 '13 at 3:02

You assumed, I believe, what you were to prove. Look at your expression following "Let" and look at your expression following "Finally"...they say the same thing!

How about letting $\rho = \sigma$: all that matters to show is that for each $\sigma \in X$, $\sigma \sim \sigma$, there exists some permutation in $X$ satisfying the relation:

This reflexive relation is satisfied for any $\sigma \in X$ by choosing $\rho$ to be itself: for $\tau$, let $\rho = \tau$...etc...

Then $$(\sigma^{-1} \circ \sigma \circ \sigma)(x) = (\sigma^{-1} \circ \sigma)(x) \circ \sigma(x) $$ $$\vdots$$ $$ = \sigma(x)$$.

share|cite|improve this answer

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.