Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Another way to write it is to say that the theory of linear orders coincides with the theory of "Dedekind complete" linear orders. By Dedekind complete I mean that every subset with a lower bound has an infimum and every subset with an upper bound has an supremum. –  boumol Jun 2 '11 at 23:15

2 Answers 2

up vote 10 down vote accepted

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$.

share|improve this answer
    
Wonderful counterexample. –  boumol Jun 3 '11 at 14:01

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$.

share|improve this answer
    
Very nice. The way I think about it is that in the order $\omega+\mathbb{Q}$, one can just say that there is no largest point with a successor, and the set of points with a sucessor is bounded above, but has no least upper bound. This statement is true in $\omega+\mathbb{Q}$, but is not true in any closed set, since the supremum of any bounded set must exist. –  JDH Jun 3 '11 at 14:07
    
@JDH: The intuitions are the same, but I was forcing a problematic limit point axiomatically, while you started from a model. –  André Nicolas Jun 3 '11 at 14:37
    
What all the counterexamples rely on is the ability to define a certain nontrivial cut in the order and make the assertion that the cut has no least upper bound. (Thus, it cannot be realized by a closed suborder of $\mathbb{R}$.) In your case, the cut is "the points having a successor"; in my case, the cut was "the points below a limit-from-below point". –  JDH Jun 3 '11 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.