Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Order-preserving Embedding Functions

  1. Apr 23, 2009 #1
    How would you show that for every countable order, there is an order embedding function
    f: (A,<) -> (Q,<) ?
    Is this similiar to the proof of the w-categoricity of the Theory of Dense Linear Orders?
  2. jcsd
  3. Apr 28, 2009 #2


    User Avatar

    Surely you can just define f inductively. As A is countable, A={a0, a1,...}. Set f(a0) = 0, and for each n>0 do the following.
    Choose j<n to maximize a_j subject to a_j < a_n (if such a j exists).
    Choose k<n to minimize a_k subject to a_k > a_n (if such a k exists).
    i) f(a_n)=(f(a_j)+f(a_k))/2 if both j,k exist
    ii) f(a_n)=f(a_j)+1 if only j exists
    ii) f(a_n)=f(a_k)-1 if only k exists

    No idea about w-categoricity though.

    (For a follow up question. If A is also dense with no minimum or maximum element, can you construct f to be an order isomorphism?)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook