# Show that the group $S_n$ is generated by two sets

Show that the group $S_n$ is generated by $\{(1,2), (1,2,3,...,n) \}$ and also $\{(1,2), (2,3,...,n)\}$.

How I should start, maybe use induction?

-
Whatever the real idea or insight behind the proof, on the technical level it will probably be induction anyway. I think that if you dig deep enough, most facts about finite groups ultimately use induction. – Dan Shved Aug 18 '13 at 16:57
So I should use induction? Because @Prahlad Vaidyanathan below said, that it isn't good way. – Mat Aug 18 '13 at 16:59
You should use your common sense. You should first understand yourself why the group is generated by these sets. You don't need induction for that. hardmath's answer is a good explanation. Induction is only necessary when you write the proof rigorously. – Dan Shved Aug 18 '13 at 17:01
Look in comments below anwer @hardmath, my last but one comment is good ? – Mat Aug 18 '13 at 17:04
Well, the calculations are correct (provided the permutations are multiplied "left to right"). But I'm not sure you quite got the hint about conjugation. – Dan Shved Aug 18 '13 at 17:08

I would start with the observation that it suffices to generate all transpositions (cycles of length 2), since these will certainly suffice to generate the rest of $S_n$.

Observe what happens when you conjugate the transposition $(1,2)$ with the longer cycle. How can we generalize this to get more transpositions?

A couple of facts are useful before attempting such a proof:

(1) Every permutation can be written as a product of disjoint cycles.

(2) Every cycle can be written as a product of transpositions.

-
I don't know, I just start learn permutations and transpositions ;). So induction is bad idea? – Mat Aug 18 '13 at 16:14
Induction in group theory is (usually) only useful if the group you are working with has "enough" normal subgroups. In this case, $S_{n-1}$, while a subgroup of $S_n$ is not normal, so it might not help to use induction. – Prahlad Vaidyanathan Aug 18 '13 at 16:16
In what class are you studying permutations and transpositions? – hardmath Aug 18 '13 at 16:16
@hardmath I know the facts from your answer, but I don't know how I should begin prove. – Mat Aug 18 '13 at 16:22
Do you know what it means to "conjugate" in a group? Given two group elements $g,h$ (permutations in this case) multiplying $ghg^{-1}$ can be called conjugating $h$ by $g$. See what happens when you do this with the two permutations you started with. – hardmath Aug 18 '13 at 16:27