0

Can anyone help me show this? I read this in my classnotes but no proof was given. Thanks.

jerry
  • 83
  • 1
    Induction on $n$, and use cycle decomposition of elements of $S_n$. – Batominovski Dec 12 '17 at 04:33
  • 5
    Duplicate of https://math.stackexchange.com/questions/2286481/symmetric-group-s-n-is-generated-by-consecutive-transpositions?rq=1 – John Hughes Dec 12 '17 at 04:37
  • 1
    Also https://math.stackexchange.com/questions/1928957/proving-s-n-is-generated-by-the-set-1-text-2-2-text-3-cdots-n-1-t?noredirect=1&lq=1, which has no upvoted answer, but the answer that's there points to a complete and detailed proof/ – John Hughes Dec 12 '17 at 04:39

2 Answers2

1

Note that any permutation can be written as a product of transpositions. So if we can show that any transposition $(i,j)$, $1\le i,j\le n$, can be generated by the given set then we are done. Assume w.l.o.g. that $i<j-1$. Then the product $(i,i+1)(i+1,i+2)\cdots(j-1,j)$ will take $i\mapsto j$ and for every $k$, such that $i<k\le j$, $k\mapsto k-1$. We then apply the product $(j-2,j-1)(j-3,j-2)\cdots(i,i+1)$.

QED
  • 12,644
1

Induction on $n$: for the induction step you need that the usual copy of $S_n$ inside $S_{n+1}$ and $(n\,\, n+1)$ generate $S_{n+1}$. But they generate a transitive subgroup $G$, whose point stabiliser has order $\ge n!$, so $G$ has order at least $(n+1)n!=(n+1)!$.

Angina Seng
  • 158,341