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?

share|improve this question
    
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
show 23 more comments

1 Answer

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.

share|improve this answer
    
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
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.