# A question on linear orders and elementary equivalence

Does anybody know whether the following statement is true or false?

Conjecture: For every linear order $\langle A, \leq \rangle$ there is a (topologically) closed subset $X$ of $\mathbb{R}$ (the real numbers) such that $\langle A, \leq \rangle$ and $\langle X , \leq \rangle$ (here I consider $X$ ordered by the restriction of the real order) are elementary equivalent (i.e., they satisfy the same first order sentences).

I would suspect this to be true, but I do not see how to prove it. For example, if $A$ is densely ordered then the previous statement is true. This is so because it is enough to take, depending on whether there is a minimum or a maximum, $X$ as either $\mathbb{R}$, $( -\infty, 1]$ and $[ 1, +\infty)$.

Can anybody suggest a way to prove the previous statement? Or a way to build a counterexample?

EDIT: JDH has shown that the conjecture is easily falsified. What about the following modification? [I believe his counterexample do not apply]

Updated Conjecture: For every first order sentence $\varphi$, if $\varphi$ is satisfiable in some linear order $\langle A, \leq \rangle$ then it is also satisfiable in some linear order $\langle X, \leq \rangle$ where $X$ is a closed subset of real numbers.

Remark: This updated conjecture can be rewritten as saying that $Th(\{ \langle X, \leq \rangle: X \text{ is a closed set of reals} \}) = Th (\{ \langle A, \leq \rangle: \langle A, \leq \rangle \text{ is a linear order} \})$

-
How do you want to express "there is at most countable many elements ..." using first-order sentences? – boumol Jun 2 '11 at 13:26
Never mind, I was being silly. – Qiaochu Yuan Jun 2 '11 at 13:39

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.

-
Thanks. It is an obvious counterexample (since this linear order is discrete in the sense that all points, except the minimum-maximum, have a predecessor and a successor) to my above statement. – boumol Jun 2 '11 at 18:10
I have somehow modified the conjecture (see the main text) to have a "local aspect". Do you think this might be true? – boumol Jun 2 '11 at 18:15
I like the new conjecture very much, and I think it is likely true, but proving that will be much harder. I shall have to think about it. (Incidently, it's no big deal, but I think the recommended procedure on this site is for you to open a new question and provide a link to it and back rather than to edit the existing question to a completely new question as you have; the previous question after all was interesting, and is now settled. This way of proceeding avoids the inevitably confusing situation of answers that answer a question that was the question but is no longer the question.) – JDH Jun 2 '11 at 20:50
OK. I have just added a new question with the updated conjecture. – boumol Jun 2 '11 at 21:54
I have now made a counterexample to the revised conjecture over at the new question: math.stackexchange.com/questions/42875/… – JDH Jun 3 '11 at 10:46

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.

-
I came to the same conclusion, but this doesn't show that the resulting subset is closed in $\mathbb{R}$. – Qiaochu Yuan Jun 2 '11 at 13:39
Oh, I missed the "closed" part. I think I'm going to leave this up anyway while I think about it. The easy trick of taking the closure of the subset I constructed doesn't work, unfortunately. – Jason DeVito Jun 2 '11 at 13:40
@Jason: Why taking the closure doesn't work? – Apostolos Jun 2 '11 at 14:29
@Apostolos: The order type of, say, $(0,\infty)$ is not elementary equivalent to its closure $[0,\infty)$ since the second has a least element and the first doesn't. – Jason DeVito Jun 2 '11 at 14:52
@Jason: I see, thanks. – Apostolos Jun 2 '11 at 14:56