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.

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

share|improve this question
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

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
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.

share|improve this answer
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

Your Answer


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.