# 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 $\displaystyle |A|=n$ and let
$\displaystyle F=\{f|f\mbox{ is a one to one,onto function from }I_n\mbox{ to }A\}$.

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

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

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

$\displaystyle 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
$\displaystyle g:A\to I_n$ by the formula $\displaystyle g(a)=|\{x\in A\;|\;xRa\}|$.

$\displaystyle \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 $\displaystyle g^{-1}\in F$

and $\displaystyle h(g^{-1})=R$. I could show that g is one to one. To prove that
$\displaystyle 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 $\displaystyle I_n=\{1,\dots,n\}$.

Originally Posted by issacnewton
Then he says use this fact to show that $\displaystyle g^{-1}\in F$ and $\displaystyle h(g^{-1})=R$. I could show that g is one to one. To prove that $\displaystyle 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 $\displaystyle g\in F$ i.e. g is one to one and onto function
from $\displaystyle I_n$ to $\displaystyle 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
$\displaystyle |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, $\displaystyle g:A\to I_n$ and, since g is one-to-one, g is onto, i.e., g is a bijection. Therefore, $\displaystyle g^{-1}$ is a bijection and so it belongs to F.