A question on linear orders and elementary equivalence

Solution 1:

The conjecture is not true. Consider the order $\omega+\omega^*$, that is, an increasing $\omega$ sequence with a descending $\omega$ sequence above it, and nothing in the middle. This is an infinite discrete order with endpoints, but there is no closed suborder of $\mathbb{R}$ that is elementarily equivalent to this order. If $X\subset\mathbb{R}$ were such an order, then $X$ would have to have a copy of $\omega$ as an initial segment, since this is expressible by assertions in the order language, and furthermore, this copy would have to be bounded above in $\mathbb{R}$, since it is in the original order. Since $X$ is closed, therefore, $X$ would have a limit to this sequence. Such an element would be a non-minimal element having no immediate predecessor. The existence of such an element is expressible in the language, and is false in the original order, a contradiction to elementary equivalence.

Solution 2:

Edit: This doesn't actually answer the question, but it may possibly be a good starting point.

Your intuition is correct, but you can do even better: I claim that every linear order is elementary equivalent to some suborder of $\mathbb{Q}$.

Here's the idea of the proof.

By the downward Lowenheim-Skolem theorem, every linear order is elementary equivalent to a countable linear order. So it's enough to show every countable linear order is elementary equivalent to a suborder of $\mathbb{Q}$. In fact, every countable linear order embeds into $\mathbb{Q}$.

To see this, let $L$ be any countable linear ordering. We will inductively define a sequence of order embeddings $f_n$ where the domain of $f_n$ is a subset of $L$ consisting of $n$ elements and such that each $f_n$ properly extends the previous $f_k$ (that is, if $k < n$ then the domain of $f_k$ is a proper subset of the domain of $f_n$ and the two functions agree when restricted to the domain of $f_k$).

If we do this right, at the end, every element of $L$ will be accounted for by some $f_n$. Then we just define $f:L\rightarrow\mathbb{Q}$ by $f(l) = f_n(l)$ for some $n$ for which the right hand side makes sense. This will be our desired order embedding.

So, how do we construct the $f_n$? Inductively! First, since $L$ is countable, we can list the elements $L = \{l_1,l_2,...\}$ (we are completely ignoring the order on $L$ for this step). Let $L_n = \{l_1,...,l_n\}$.

To begin with, pick your favorite rational number (mine is $0$) and define $f_1:L_1\rightarrow \mathbb{Q}$ by $f_1(l_1) = 0$.

Now, assume inductively we have defined $f_n:L_n\rightarrow \mathbb{Q}$ so that it's order preserving and so that $f_n$, when restricted to $L_k$ for any $k < n$ agrees with the $f_k$ we defined there.

So, what should $f_{n+1}:L_{n+1}\rightarrow \mathbb{Q}$ be? Well, if we want it to restrict correctly to $L_n$, we must define $f_{n+1}(l_i) = f_n(l_i)$ when $i\neq n+1$, so the only freedom we really have is in defining $f_{n+1}(l_{n+1})$.

This will break into 3 cases. If $l_{n+1}$ is less than (in the order of $L$) all the previous $l_k$, then pick any element $q$ of the rationals which is less that $f_n(L_n)$. We can do this because $f_n(L_n)$ has $n$ elements and $\mathbb{Q}$ has no smallest element. Defining $f_{n+1}(l_{n+1}) = q$ gives us the extension we want. It is easy to verify that if $f_n$ is order preserving, this choice is makes $f_{n+1}$ order preserving.

Of course if $l_{n+1}$ is bigger than all the previous $l_k$, choose a rational larger than all of $f_n(L_n)$.

Finally, assume $l_{n+1}$ is smaller than some and bigger than some elements of $L_n$. Let $s$ be the greatest element of $L_n$ smaller than $l_{n+1}$ and $t$ the smallest element of $L_n$ bigger than $l_{n+1}$. These elements exist because $L_n$ is finite. Pick a rational number $q$ between $f_n(s)$ and $f_n(t)$ and define $f_{n+1}(l_{n+1}) = q$. Then this new $f_{n+1}$ is order preserving.

So, by induction, we've defined $f_n$ for all $n$. Now, define $f:L\rightarrow\mathbb{Q}$ by $f(l_n) = f_n(l_n)$. To see $f$ is order preserving, let $l_k$ and $l_n$ be two elements of $L$ with $k < n $. Assume wlog $l_k < l_n$. Since $k<n$, both $l_k$ and $l_n$ are in the domain of $f_n$. Since $f_n$ is order preserving we have $f_n(l_k) < f_n(l_n)$. Finally, note that $$f(l_k) = f_k(l_k) = f_n(l_k) < f_n(l_n) = f(l_n)$$ so $f$ preserves order as well.