# Proof that transpositions generate $S_n$, and proof that $\#(S_n) = n!$ (Lang's Algebra p. 13)

I am trying to unpack Lang's proofs and verify that I'm correctly filling in the details.

Excerpt:

My attempt:

To prove that the transpositions generate $$S_n$$, we proceed by induction on $$n$$. When $$n = 1$$ we can use the identity map to generate $$S_1$$. Assume the result is true for $$S_{n - 1}$$.

Consider $$\sigma \in S_n$$ and assume that $$\sigma(n) = k \neq n$$, otherwise we could think of $$\sigma$$ as a product of transpositions in $$S_{n - 1}$$ and tack on $$\tau (n) = n$$ for all the transpositions. Take transposition $$\tau \in S_n$$ that interchanges $$k$$ and $$n$$. Then $$\tau \sigma$$ leaves $$n$$ fixed and can therefore be written as $$\tau \sigma = \tau_m \tau_{m - 1} \dots \tau_1$$ where all the transpositions on the right-hand side are extensions of transpositions in $$S_{n - 1}$$ that leave $$n$$ fixed. Multiply by $$\tau$$ on the left to see that $$\sigma = \tau \tau_m \tau_{m - 1} \dots \tau_1$$ as desired.

To prove that $$\#(S_n) = n!$$ we again use induction on $$n$$. The base case is clear. Assume that $$\# (S_{n - 1}) = (n - 1)!$$. The subgroup $$H$$ of $$S_n$$ that leaves $$n$$ fixed is isomorphic to $$S_{n - 1}$$ because the elements of $$S_{n - 1}$$ are the same as those of $$H$$, except that they are restricted to $$\{ 1, \dots n - 1 \}$$. The elements $$\sigma_1, \dots, \sigma_n$$ as described are coset representatives (of distinct cosets) of $$H$$ in $$S_n$$. The argument $$\sigma_i h_1 = \sigma_j h_2 \Rightarrow \sigma_i = \sigma_j h_2 h_1^{-1} \Rightarrow \sigma_i H = \sigma_j h_2 h_1^{-1} H \Rightarrow \sigma_i H = \sigma_j H$$ shows that two such cosets are either disjoint or equal.

Question:

Unfortunately I cannot quite put my finger on why $$\bigcup_{i = 1}^n \sigma_i H = S_n$$. If I consider $$\sigma \in S_n$$ such that $$\sigma (n) = k$$, then I feel like I need to show that $$\sigma \in \sigma_k H$$, but I don't see how to do this. Why is this "immediately verified"?

Once I've shown this, I see that Lagrange's theorem gets us $$(S_n : 1) = n(n - 1)!$$ as desired.

I appreciate any help.

If $$\sigma(k)=n$$ and $$\sigma_k(n)=k$$ then $$\sigma^{-1}\sigma_k(n)=n$$ so $$\sigma^{-1}\sigma_k\in H$$ since it fixes $$n$$ hence $$\sigma_k^{-1}\sigma \in H\Rightarrow \sigma \in \sigma_k H$$
• Thank you for your help, but I find your answer confusing. I wonder if you made an error. If we let $\sigma (n) = k$ and $\sigma_k (n) = k$, then $\sigma_k^{-1} \big( \sigma (n) \big) = n$ and therefore $\sigma_k^{-1} \sigma \in H$, whence $\sigma \in \sigma_k H$. – Novice Sep 25 '20 at 6:07
• You wrote $\sigma (k) = n$. I did not see how to make that work, so I used $\sigma (n) = k$ and things seemed to work out (see my prior comment). – Novice Sep 25 '20 at 16:24
The point is that any permutation $$\tau \in S_n$$ has to send $$n$$ somewhere. That somewhere tells you which coset contains $$\tau$$.