4
$\begingroup$

I don't want to type Greek letters hence I replaced $\gamma$ by $y$. Microsoft didn't replace them all.

Call the identity permutation $id$. Prove the contraposition: $\sigma \neq id \implies \exists \, y \in S_n : \sigma y \neq y\sigma.$

Suppose $\sigma \neq id.$ Then for some $1 \le x_1 \neq x_2 \le n, \; \color{brown}{\sigma(x_i) = x_2}$.
Because $n \ge 3$, hence there exists a third element $x_3 \neq x_2$ such that $y(x_2) = x_3$ and $\color{magenta}{y(x_1) = x_1}$.
Then $(σγ)(x_1) = σ(\color{magenta}{γ(x_1)}) = σ(\color{magenta}{x_1}) = x_2$
while $(γσ)(x_1) = γ(\color{brown}{σ(x_1)}) = γ(\color{brown}{x_2}) = x_3$,
so $σγ \neq γσ.$

(1.) How and why does $n \ge 3$ imply there exists $y \in S_n$ such that $y(x_2) = x_3$ and $\color{magenta}{y(x_1) = x_1}$ ?

(2.) How do you predestine, preordain to prove this by contraposition?

(3.) What's the intuition?

Update Fev. 4 2014: clem wrote $\color{darkred}σ: x_3 \mapsto i$.
Shouldn't this be $\color{darkred}{(γσ)^{−1} =σ^{−1}γ^{−1}} : x_3 \longmapsto i$ ? Hence I apply $γ^{−1}$ first to sally forth from $x_3 \to i$?

$\endgroup$
2
  • 1
    $\begingroup$ As for (1.), we define $\gamma$ so that it satisfies $\gamma(x_2) = x_3$ and $\gamma(i) = i$ -- these properties are part of the definition of $\gamma$. $\endgroup$
    – xyzzyz
    Jan 16, 2014 at 16:40
  • $\begingroup$ For your second question, when you cannot come up with a direct proof you usually try to think of a proof by contradiction or a proof by contraposition. $\endgroup$
    – Module
    Jan 16, 2014 at 17:06

1 Answer 1

1
+50
$\begingroup$

I think the intuition is present in the proof. I'm going to use very casual language, because to me that makes it more intuitively clear.

First, rewrite the condition as finding a $\sigma$ such that $y = \sigma^{-1} y \, \sigma$ for all $y \in S_n$.

Now assume that this holds for some permutation $y$. If $\sigma$ is not the identity, then some element will be moved by $\sigma$. In the proof, we call the element that is moved $x_1$ and we say that it "moves" to the place of $x_2$.

What if we had a $y$ that leaves the element $x_1$ where it was (equivalently, doesn't move $x_1$), and moves $x_3$ to $x_2$? If $n \geq 3 $ this gamma must exist. Because we are assuming the above condition holds, the complete operation $\sigma^{-1} y \, \sigma$ can't move $x_1$, because $y$ doesn't move it. But $\sigma$ moves $x_1$ to $x_2$, which is moved to $x_3$ by $y$. So $\sigma$ must move $x_3$ to $x_1$. But $x_2$ is already moved to $x_1$ by $\sigma^{-1}$, which contradicts the fact that $\sigma$ is a permutation. So if $\sigma$ is not the identity, ie if it moves something, then $y = \sigma^{-1} y \, \sigma$ cannot hold for all possible $y$ in $S_n$.

So the intuition is that we can always choose a $y$ that forces $\sigma$ to have two elements that are moved to the same 'spot' by the permutation, which is impossible. I'm not sure if this is intuition, but that's the best answer to "Why is this true?" that I can give.

Update to answer edited question

1) We need $n \geq 3$ because I name three elements $x_1$, $x_2$ and $x_3$. Since $S_n$ is just permutations, for y just use any permutation of n objects that swaps two objects and leaves at least one in the same position.

2) Because we are trying to prove that no other element with this property exists, a good first step (usually) is to assume such an element exists, then try to find a $\color{red}{contradiction}$.

$\color{red} { \text { But I queried contraposition, not contradiction? Hence this doesn't answer question 2? } }$

3) As for intuition, I'm not sure what else to say. For me, this becomes more clear if I imagine a game where I rearrange objects and my friend can rearrange them either before or after I do, but the answer has to be the same in both cases. Then it's clear that finding such a permutation would be quite difficult, so it's not surprising that it is not possible (other than the trivial rearrangement)

$\endgroup$
5
  • $\begingroup$ You wrote $σ$ must move $x_3 \to i$. Are you sure? Shouldn't this be $(\gamma\sigma)^{-1} = \sigma^{-1}\gamma^{-1} $? Hence I apply $\gamma^{-1}$ first? $\endgroup$
    – NNOX Apps
    Feb 4, 2014 at 5:52
  • $\begingroup$ Sorry, for the condition to hold $\sigma$ must map i to $x_3$. Which is the same as sigma inverse maps x3 to i. Both of these are equivalent and lead to the same contradiction. $\endgroup$
    – clem
    Feb 4, 2014 at 19:22
  • $\begingroup$ Apologies. I still don't understand why $\sigma : x_3 \to x_1$. Can you please notify me in your answer, and not in comments? $\endgroup$
    – NNOX Apps
    Apr 26, 2014 at 20:28
  • $\begingroup$ To boot, did you answer my questions 1 and 2? $\endgroup$
    – NNOX Apps
    Apr 26, 2014 at 20:29
  • $\begingroup$ Thanks. Your update 2 is defected. I wrote why on top. And can you please write more about this 'game' in your update 3. Why is it 'clear' that 'finding such a permutation would be quite difficult'? $\endgroup$
    – NNOX Apps
    May 4, 2014 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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