Show that the symmetric group S_n has elements of all order

[Mr Davis 97]

Homework Statement

Prove that if ##1 \leq d \leq n##, then ##S_n## contains elements of order d.

Homework Equations

The Attempt at a Solution

Here is my idea. The order of the identity permutation is 1. Written in cycle notation, the order of (1,2) is 2, the order of (1,2,3) is 3, the order of (1,2,3,4) is 4, and in general the order of (1,2,3,4,...,n-1,n) is n. It would seem that this shows that if ##1 \leq d \leq n##, then ##S_n## contains elements of order d.

However, I am not sure how rigorous this is. Do I need to make an induction argument that in general (1,2,3,4,...,n-1,n) has order n, or is it fine as it is?

 

[fresh_42]

However, I am not sure how rigorous this is. Do I need to make an induction argument that in general (1,2,3,4,...,n-1,n) has order n, or is it fine as it is?

This only depends on whom it is meant for. For me, it is o.k., but I already had the same thought as I've read the question. For someone in high school, some kind of reasoning might be helpful. You don't need an induction here, because you can show it directly for ##(1,2,\ldots,n)## and the knowledge that ##(1,2,\ldots,n-1)## is of order ##n-1## is of no help for ##(1,2,\ldots,n)^n=1\, : \,## You would have to write
$$ \begin{align*}(1,2,\ldots,n)^n &= [(1,2,\ldots,n-1) \cdot (n,n-1)]^n \\ &= (1,2,\ldots,n-1) \cdot (n,n-1) \cdot \ldots \cdot (1,2,\ldots,n-1) \cdot (n,n-1) \end{align*}$$
and deal with the fact, that the permutations are not commutative, which would make it unnecessarily complicated.

Thus simply take any number ##i\in \{1,2,\ldots,n\}## and justify why it takes ##n## turns to reach ##i## again.

 

[Mr Davis 97]

Okay, that answers my question.

On a related note, how would I prove that the order of a cycle is equal to its length? It seems very obvious, but I can't quite see how to formalize a proof

 

[fresh_42]

Okay, that answers my question.

On a related note, how would I prove that the order of a cycle is equal to its length? It seems very obvious, but I can't quite see how to formalize a proof

Just count the steps: ##i \mapsto i+1 \mapsto \ldots \mapsto n \mapsto 1 \mapsto \ldots \mapsto i-1 \mapsto i## where you have to be careful at the turning point ##n## with the counting (e.g. I tend to make a mistake by one at this point) and remark, that there is no way of getting back to ##1## earlier.

Or assume ## {(1,2,\ldots,n)}^m = 1 = id## which is ## {i}+m \cdot 1 = 1({i}) = i \mod n ## for all ##1 \leq i \leq n## and show that this can only be true for ##m=n##.