4
$\begingroup$

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

Excerpt:

enter image description here

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.

$\endgroup$
4
$\begingroup$

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$

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ – Novice Sep 25 '20 at 6:07
  • $\begingroup$ @Novice Maybe I've made an error but could you specify where exactly? $\endgroup$ – 1123581321 Sep 25 '20 at 6:38
  • $\begingroup$ 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). $\endgroup$ – Novice Sep 25 '20 at 16:24
  • $\begingroup$ @Novice Yes you're right, what you have written suits your question better $\endgroup$ – 1123581321 Sep 25 '20 at 18:06
3
$\begingroup$

The point is that any permutation $\tau \in S_n$ has to send $n$ somewhere. That somewhere tells you which coset contains $\tau$.

$\endgroup$

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.