Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

1 Answer 1

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

This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .