Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove that the DLO $(\mathbb{Q}, <)$ is an $O$-minimal structure, but I am trying to prove this without using the fact that the complete theory of dense linear orderings without endpoints admits quantifier elimination.

Here is my proof thus far: Let $N = \varphi(\mathbb{Q}, \bar{a})$ where $\varphi$ is a first-order formula from the language of partial orders. We may assume that $\bar{a} = (a_0, \ldots, a_{n-1})$ and that $a_0<\cdots <a_{n-1}$. Put $a_{-1}=-\infty$ and $a_n = \infty$.

Assumption: for any $-1\leq j\leq n-1$ and $x,y \in \mathbb{Q}$ such that $a_j<x<y<a_{j+1}$ there is an order automorphism $f$ which fixes $\bar{a}$ and $f(x)=y$.

If this is true, then if $N$ contains an element of the interval $(a_j, a_{j+1})$ it must then contain the whole open interval, and from this we can infer that the structure is O-minimal.

I am having difficulty, however, proving the assumption. Any help would be greatly appreciated.

share|cite|improve this question
up vote 5 down vote accepted

Edit: In the original version I very carelessly used $\frac{y}{x}$ and $\frac{x}{y}$ for the multipliers, when of course they have to be $\frac{y-a_j}{x-a_j}$ and $\frac{a_{j+1}-y}{a_{j+1}-x}$. Barring further stupidity on my part, it’s now fixed.

You want to stretch the interval $[a_j,x]$ to cover the interval $[a_j,y]$ while shrinking $[x,a_{j+1}]$ down to $[y,a_{j+1}]$. This means stretching $[a_j,x]$ by a factor of $\frac{y-a_j}{x-a_j}$. You’re going to leave $a_j$ fixed, so what really gets stretched is the distance of each point of $[a_j,x]$ from $a_j$. A function that does this is $$f_L(q) = \frac{y-a_j}{x-a_j}(q-a_j)+a_j = \frac{y-a_j}{x-a_j}q + \frac{x-y}{x-a_j}a_j;$$ since $\frac{y-a_j}{x-a_j}$ and $a_j$ are rational, $f_L$ takes rationals to rationals.

Of course this still leaves $[x,a_{j+1}]$ to be taken care of. The same basic idea works, but this time it’s the distance from $q$ to $a_{j+1}$ that matters, and it has to be multiplied by a factor of $\frac{a_{j+1}-y}{a_{j+1}-x}$. For this the function $$f_R(q) = a_{j+1}-\frac{a_{j+1}-y}{a_{j+1}-x}(a_{j+1}-q) = \frac{a_{j+1}-y}{a_{j+1}-x}q + \frac{y-x}{a_{j+1}-x}a_{j+1}$$ does the trick. Now just combine and extend these to cover $\mathbb{Q}$: $$f(q) = \begin{cases} q, &q < a_j\\ \frac{y-a_j}{x-a_j}q + \frac{x-y}{x-a_j}a_j, &a_j \le q < x\\ \frac{a_{j+1}-y}{a_{j+1}-x}q + \frac{y-x}{a_{j+1}-x}a_{j+1}, &x \le q < a_{j+1}\\ q, &q \ge a_{j+1}. \end{cases}$$

share|cite|improve this answer

It is sufficient to show that there is an order-preserving map taking $\mathbb{Q} \cap (0,1)$ onto itself. Look for a fractional linear transformation $$f(x) = \frac{(c+d)x}{cx+d}$$ This fixes 0 and 1. If you choose $c, d \in \mathbb{Q}$ properly, it will be increasing in $(0,1)$, take rationals onto rationals, and allow you to map any rational in $(0,1)$ onto any other.

share|cite|improve this answer

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.