10
$\begingroup$

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

  • 0
    Never mind, I was being silly.2011-06-02

2 Answers 2

11

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.

  • 0
    I have now made a counterexample to the revised conjecture over at the new question: http://math.stackexchange.com/questions/42875/the-first-order-theory-of-linear-orders-given-by-closed-subsets/42990#429902011-06-03
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, 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.

  • 0
    @Jason: Can you edit your answer saying that it does not solve the question?2011-06-02