Order-preserving Embedding Functions

  • #1

Main Question or Discussion Point

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?
 

Answers and Replies

  • #2
gel
533
5
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).
Set,
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?)
 

Related Threads for: Order-preserving Embedding Functions

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
2K
Top