How many total orderings can be defined on a set with n elements?

Question

I was thinking the answer is n total orderings can be defined, but the answer in the book states it's n!, which I don't really understand. I was wondering if someone could maybe explain?

Answer 1

How many total orders can you define on $\{1,2,\ldots,n\}$? For each such order $\prec$, you can define a bijection $\varphi$ from $\{1,2,\ldots,n\}$ onto itself by:

• $\varphi(1)$ is the first element of $\{1,2,\ldots,n\}$;
• $\varphi(2)$ is the first element of $\{1,2,\ldots,n\}\setminus\bigl\{\varphi(1)\bigr\}$;
• $\varphi(3)$ is the first element of $\{1,2,\ldots,n\}\setminus\bigl\{\varphi(1),\varphi(2)\bigr\}$;
• $\vdots$

And if $\varphi$ is a bijection $\varphi$ from $\{1,2,\ldots,n\}$ onto itself, you can defined a total order $\prec$ on $\varphi$ from $\{1,2,\ldots,n\}$ by$$a\prec b\iff\varphi(a)<\varphi(b).$$So, there are as many total orders on $\{1,2,\ldots,n\}$ as there are bijections from $\{1,2,\ldots,n\}$ onto itself. And there are $n!$ such bijections.