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.
Best Answer
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$