# Permutation and Equivalence

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?

-

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$,

$$\rho^{-1}\left(\sigma\big(\rho(x)\big)\right)=\sigma(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

$$\rho^{-1}\left(\sigma\big(\rho(x)\big)\right)=\rho^{-1}\big(\sigma(x)\big)\;.$$

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

$$\rho^{-1}\left(\sigma\big(\rho(x)\big)\right)=\rho^{-1}\big(\sigma(x)\big)=\sigma(x)\;.$$

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.

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

-