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.

I've always heard that it's trivial that $|S_n|=n!$ where $S_n$ is the symmetric group of degree $n$. Now, my proof was the following: consider $I_n=\{1,\dots,n\}$ and consider $\mathcal{I}=\prod_{k=1}^n I_n$. Set the following map $\varphi : S_n\to \mathcal{I}$ given by $\varphi(f) = (f(1),\dots,f(n))$. If we denote $A=\varphi(S_n)$, the obviously $\varphi$ is surjective over $A$. Also, it's injective, because if $\varphi(f)=\varphi(g)$, then for each $i$, $f(i)=g(i)$ and hence $f=g$. In that case $|S_n|=|A|$.

Finally, to find $|A|$ we argue as follows, if $(i_1,\dots,i_n)\in A$, then there's a function $f : I_n\to I_n$ that is bijective and such that $i_k = f(k)$. Because of that, there are $n$ possible values for $i_1$. When such a value is selected, since the function must be injective, there are remaining $n-1$ values for $i_2$, and so on, until $i_n$. In that case, there are $n!$ objects to choose, and hence $|S_n|=n!$.

I think this proof is not good, I feel it's not rigorous. Is this proof allright? If not, how can I improve it?

Thanks very much in advance!

share|improve this question
1  
Just think of how many ways are there to put the numbers ${1,2,..,N}$ in line.There are $n!$ ways. Simple combinatorics:) –  Mitsos Oct 30 '13 at 14:12
    
The approach in the second paragraph is correct. In the first paragraph you seem to be carefully constucting a correspondence between elements of $S_n$ and functions $f:I_n\rightarrow I_n$ -- but your elements of $S_n$ were exactly such functions to begin with. I'd suggest you're worrying too much about 'rigour' here, it's just disguising your perfectly good argument. –  aPaulT Oct 30 '13 at 15:45

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.