# Prove the symmetric group is generated by

• Samuelb88
In summary, the problem requires using induction to show that the transpositions s_i = (i, i+1) for 1 ≤ i ≤ n-1 are sufficient to generate S_n. The base case for n=2 is shown by the transposition s_1 = (12) which generates S_n since s_1^2 = e. It is then shown that the transpositions s_i for 1 ≤ i ≤ n-1 can generate S_n+1 by using the additional transposition s_n+1 = (n, n+1) and writing an element s in S_n+1 as a product of transpositions and elements in S_n. The elements of s are labeled and it is shown that
Samuelb88

## Homework Statement

Use induction of n to prove that the transpositions $s_i = (i, i+1)$, $1 \leq i \leq n - 1$ generate $S_n$.

## Homework Equations

Notation: $e$ = Identity permutation.

Any permutation can be written as a disjoint product of transpositions.

## The Attempt at a Solution

Proof. We proceed by induction on n. As our base case for $n=2$, we cite that the transposition $s_1 = (12)$ is sufficient to generate $S_n$ since $s_1^2 = e$. Suppose now that the transpositions $s_i = (i, i+1)$, $1 \leq i \leq n-1$ generate $S_n$.

I'm not really sure where to go next. I know that $S_n$ has $n!$ elements and want to use that fact along with the transposition $(i+1,i+2)$ to somehow show that $S_{n+1}$ will have $(n+1)!$ elements but I am not sure if that is sufficient to prove that the $s_i$'s generate $S_n$.

Try to show you can write an element s of S_n+1 as an element of S_n times some transpositions. Label which elements of the permutation s map to and from n+1.

Dick,

Thanks for your response. It makes sense that I should be able to generate the elements of $S_{n+1}$ using the permutations that are contained in $S_n$ plus the additional transposition $s_{n+1} = (n, n+1)$. But how would I do this?

For example, say I was constructing elements in $S_4$ from the old transpositions $s_1 = (12)$, $s_2 = (23)$, and the newly acquired transposition $s_3 = (34)$. Then the products $s_1 s_2 s_3$, $s_1 s_3 s_2$, and $s_2 s_2 s_3$ are all different. Here's what confusing me: How can I work around the problem of generalizing a product when the newly acquired transposition is wedged in between two old permutations. Does this make sense? Would it suffice to say that if $\sigma \in S_{n+1}$ and $\sigma ' \in S_n$, then we can write $\sigma$ in the form of either $\sigma' s_{n+1}$, or $s_{n+1} \sigma'$, or $\sigma_1' s_{n+1} \sigma_2'$?

Also, I don't understand what you mean by label which elements of the permutation s map to and from n+1. Can you explain further, please?

If s is in S_n+1 there is some l in {1...n+1} such that s(l)=n+1 and some k in {1...n+1} such that s(n+1)=k. For the rest of the i in {1...n} s(i) is in {1...n}. So yes, what you say makes perfect sense. You do some transpositions, apply an element in S_n then do some more transpositions so the result is s in S_n+1. You just have to spell out what those initial and final transpositions are.

Great. It makes perfect sense to me now. Thanks again!

## 1. What is the symmetric group?

The symmetric group is a mathematical concept that represents all possible ways to arrange a set of elements. It is denoted as Sn, where n is the number of elements in the set.

## 2. What does it mean for a group to be generated?

A group is said to be generated by a set of elements if every element in the group can be expressed as a combination (or product) of those elements. In other words, the set of elements is sufficient to create and represent all elements in the group.

## 3. How can we prove that the symmetric group is generated by a specific set of elements?

To prove that the symmetric group is generated by a specific set of elements, we need to show that every element in the group can be expressed as a combination of those elements. This can be done through various techniques such as using induction, group axioms, and specific properties of the group.

## 4. Why is it important to prove that the symmetric group is generated by a set of elements?

Proving that the symmetric group is generated by a set of elements helps us understand the structure and properties of the group. It also allows us to simplify calculations and proofs involving the symmetric group by reducing them to the set of generating elements.

## 5. Can the symmetric group be generated by different sets of elements?

Yes, the symmetric group can be generated by different sets of elements. In fact, there are infinitely many possible generating sets for the symmetric group. However, some sets may be more convenient or useful than others depending on the specific problem or context.

Replies
7
Views
1K
Replies
3
Views
1K
Replies
11
Views
2K
Replies
9
Views
1K
Replies
3
Views
1K
Replies
7
Views
1K
Replies
4
Views
4K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
2
Views
1K