Skip to main content
added 2 characters in body
Source Link
Michael Hardy
  • 1
  • 12
  • 90
  • 133

This argument is not drastically different from some of the other answers, but I'm going to write it down for the record. It is a kind of unbiased version of the inversion counting argument and can also be seen as a simplification of the argument via the action on the set of orientations of the complete graph.

Let $X$ be a finite set with at least $2$ elements and let $T_X$ be the set of total orders on $X$. Consider the following relation $\sim$ on $T_X$: two orders are equivalent if the number of $2$-element subsets of $X$ on which they disagree is even. Check that this is an equivalence relation with exactly two equivalence classes. The symmetric group $\Sigma_X$ acts on $T_X$ and respects $\sim$. Thus $\Sigma_X$ acts on the $2$-element set $T_X / \sim$$T_X / {\sim}$ and any transposition acts non-trivially. It follows that $\Sigma_X \to \Sigma_{T_X / \sim}$ is a surjective homomorphism.

This argument is not drastically different from some of the other answers, but I'm going to write it down for the record. It is a kind of unbiased version of the inversion counting argument and can also be seen as a simplification of the argument via the action on the set of orientations of the complete graph.

Let $X$ be a finite set with at least $2$ elements and let $T_X$ be the set of total orders on $X$. Consider the following relation $\sim$ on $T_X$: two orders are equivalent if the number of $2$-element subsets of $X$ on which they disagree is even. Check that this is an equivalence relation with exactly two equivalence classes. The symmetric group $\Sigma_X$ acts on $T_X$ and respects $\sim$. Thus $\Sigma_X$ acts on the $2$-element set $T_X / \sim$ and any transposition acts non-trivially. It follows that $\Sigma_X \to \Sigma_{T_X / \sim}$ is a surjective homomorphism.

This argument is not drastically different from some of the other answers, but I'm going to write it down for the record. It is a kind of unbiased version of the inversion counting argument and can also be seen as a simplification of the argument via the action on the set of orientations of the complete graph.

Let $X$ be a finite set with at least $2$ elements and let $T_X$ be the set of total orders on $X$. Consider the following relation $\sim$ on $T_X$: two orders are equivalent if the number of $2$-element subsets of $X$ on which they disagree is even. Check that this is an equivalence relation with exactly two equivalence classes. The symmetric group $\Sigma_X$ acts on $T_X$ and respects $\sim$. Thus $\Sigma_X$ acts on the $2$-element set $T_X / {\sim}$ and any transposition acts non-trivially. It follows that $\Sigma_X \to \Sigma_{T_X / \sim}$ is a surjective homomorphism.

Source Link
Karol Szumiło
  • 7.7k
  • 29
  • 38

This argument is not drastically different from some of the other answers, but I'm going to write it down for the record. It is a kind of unbiased version of the inversion counting argument and can also be seen as a simplification of the argument via the action on the set of orientations of the complete graph.

Let $X$ be a finite set with at least $2$ elements and let $T_X$ be the set of total orders on $X$. Consider the following relation $\sim$ on $T_X$: two orders are equivalent if the number of $2$-element subsets of $X$ on which they disagree is even. Check that this is an equivalence relation with exactly two equivalence classes. The symmetric group $\Sigma_X$ acts on $T_X$ and respects $\sim$. Thus $\Sigma_X$ acts on the $2$-element set $T_X / \sim$ and any transposition acts non-trivially. It follows that $\Sigma_X \to \Sigma_{T_X / \sim}$ is a surjective homomorphism.