Results 1 to 4 of 4

Math Help - Theorem about the Set of total orders on a given set

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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\}| .

    He asks the reader to show that

    \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.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

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

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

    Quote Originally Posted by issacnewton View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

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

    Quote Originally Posted by issacnewton View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 10th 2010, 05:01 AM
  2. Total Differentiation; total mess.
    Posted in the Calculus Forum
    Replies: 4
    Last Post: May 13th 2010, 12:14 PM
  3. Lagrange's Theorem & orders
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: March 14th 2010, 03:40 AM
  4. Proof of total probability theorem
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: December 23rd 2009, 12:25 AM
  5. help with a proof on orders
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 2nd 2009, 09:14 PM

Search Tags


/mathhelpforum @mathhelpforum