The first-order theory of linear orders given by closed subsets

Question

[ This question can be seen as a second part to my question A question on linear orders and elementary equivalence ]

The question is whether the following conjecture is true or false. I am interested on this question because using this result I know how to solve a problem I have been working during the last months; thus, besides an answer I am also interested in knowing any publication (book, paper, etc.) I can cite.

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 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} \})$

Answer 1

What a great question! I had thought at first that it might be true, but unfortunately, here is a counterexample.

Consider the order $\omega^2+\omega^*$. This is an order consisting of countably many convergent sequences, one after the other, with a descending $\omega$-sequence on top. Note that the limit of the $\omega^2$ initial part of the order has no least upper bound. Let us say that $x$ is a limit-from-below node in an order if it is not minimal, but has no immediate predecessor. In this order, these would be the limit ordinals $\omega\cdot n$.

Consider now the sentence $\varphi$ expressing the fact that there is a limit-from-below node but no largest limit-from-below node, that they are bounded above, and furthermore that any node that is above all the limit-from-below nodes has an imediate predecessor (which is also above all the limit-from-below nodes).

This sentence $\varphi$ is true in $\omega^2+\omega^*$, since every node in the descending $\omega^*$ sequence at the top has an immediate predecessor, but I claim it is not true in any closed suborder $X\subset\mathbb{R}$. If $X$ is closed, and has no largest limit-from-below nodes, but these are bounded above, then there will be a supremum of the limit-from-below nodes, and such a supremum will be above all the limit-from-below nodes, but can have no immediate predecessor. So $\varphi$ will fail in $X$.

Answer 2

The following is an argument that is in spirit close to a sketch once posted by boumol. In some ways it does not differ very much from the solution by JDH, but it has a more syntactic feel.

Let $Succ(x,y)$ be a formula that says that $y$ is "the successor" of $x$; for example, it could be an abbreviation for $$(x \le y) \land \forall u((x \le u \land u \le y) \longrightarrow (u=x)\lor (u=y)).$$

Consider the following axioms, the conjunction of which will be the sentence $\phi$ asked for in the post. The axioms are given semi-formally, but in a way that is easily made fully formal.

1. There is a smallest element, $\exists u\forall v(u \le v)$.

2. The smallest element has a successor.

3. If $x$ is a successor then $x$ has a successor, $\forall x(\exists u Succ(u,x) \longrightarrow \exists v Succ(x,v))$.

4. If $x$ has a successor and $x$ is not the smallest element, then there is a $w$ such that $x$ is the successor of $w$.

5. There is an object which is not a successor, and is not the smallest element.

6. If $x$ is not a successor, and $x$ is not the smallest element, then there is a non-successor $u$ such that $u$ is not the smallest element, and such that $u \le x$, and $u \ne x$.

It is easy to come up with models for the conjunction $\phi$ of these axioms. A simple one is the natural numbers followed by the open interval $(0,1)$, under the obvious order. This model had already been mentioned by boumol.

Now we show that the above set of axioms does not have a model which is a closed set of reals. Suppose to the contrary that the closed set $K$ of reals, with the natural order, is a model. Without loss of generality we may assume that the smallest element of $K$ is $0$.

It is easy to see that any model of the axioms has an initial segment that is order isomorphic to $\mathbb{N}$.

Let $D\subset K$ consist of all elements of $K$ other than $0$ which are non-successors.
Then $D$ is non-empty and bounded below. Let $m=\inf D$. By Axiom 6, $m$ must be a successor. Also, every object smaller than $m$ other than $0$ is a successor, by the definition of $m$.

It is clear that $m$ cannot belong to the initial segment $K_0$ of $K$ which is isomorphic to $\mathbb{N}$. So there are successors less than $m$ which are bigger than any element of $K_0$.

Let $a$ be the supremum of $K_0$. Then $a \in K$, since $K$ is closed. By the definition of $m$, this number $a$ must be a successor. But then the predecessor of $a$ is an upper bound for $K_0$, contradicting the fact that $a$ is the supremum of $K_0$.