# Thread: Theorem about the Set of total orders on a given set

1. ## Theorem about the Set of total orders on a given set

Hello

Here is a problem I am doing. Suppose $|A|=n$ and let
$F=\{f|f\mbox{ is a one to one,onto function from }I_n\mbox{ to }A\}$.

Let $L=\{R|R\mbox{ is a total order on }A\}$

Prove that $F\sim L$ and therefore $|L|=n!$.

Velleman gives some hints at the back of the book. To prove $F\sim L$,
he suggets a function $h:F\to L$ defined as

$h(f)=\{(a,b)\in A\times A|f^{-1}(a)\le f^{-1}(b)\}$.

He suggets some things to prove that h is one to one. I could do that. Now to prove
that h is onto, he says , suppose R is a total order on A. Define
$g:A\to I_n$ by the formula $g(a)=|\{x\in A\;|\;xRa\}|$.

$\forall a\in A \;\forall b\in A(aRb\leftrightarrow g(a)\le g(b))$

I could show this. Then he says use this fact to show that $g^{-1}\in F$

and $h(g^{-1})=R$. I could show that g is one to one. To prove that
$g^{-1}\in F$, I should also show that g is onto. But I have not been able
to show this. Input is welcome.

2. ## Re: Theorem about the Set of total orders on a given set

I am assuming that $I_n=\{1,\dots,n\}$.

Originally Posted by issacnewton
Then he says use this fact to show that $g^{-1}\in F$ and $h(g^{-1})=R$. I could show that g is one to one. To prove that $g^{-1}\in F$, I should also show that g is onto.
It's a general fact that on finite sets of equal cardinality, every one-to-one function is onto.

3. ## Re: Theorem about the Set of total orders on a given set

emkarov,

I have to first establish that $g\in F$ i.e. g is one to one and onto function
from $I_n$ to $A$. You are right that on finite sets of equal cardinality, every one-to-one function is onto. I think I said at the beginning that
$|A|=n \Rightarrow |A|=|I_n|$ .

Since I have proven that g is one to one, I can use the above fact to establish that
g is onto. Correct ?

4. ## Re: Theorem about the Set of total orders on a given set

Originally Posted by issacnewton
Since I have proven that g is one to one, I can use the above fact to establish that g is onto. Correct ?
Yes. By definition, $g:A\to I_n$ and, since g is one-to-one, g is onto, i.e., g is a bijection. Therefore, $g^{-1}$ is a bijection and so it belongs to F.