$(\mathbb{Q},\leq)$ is an elementary substructure of $(\mathbb{R},\leq)$

Question

I'm trying to understand why $(\mathbb{Q},\leq)$ is an elementary substructure of $(\mathbb{R},\leq)$.
It is obviously a substructure, and I also know that both structures are elementary equivalent (because the theory of dense linear orders with no maximum or minimum is complete), but that's not enough.
The proof I've seen involves quantifier elimination, but I haven't learned that subject. I'd be happy to hear about different approaches.

Answer 1

If $\phi$ is an $n$-ary formula and $b_1,\ldots,b_n\in\Bbb Q$, we want to show $$\tag1(\Bbb Q,\le)\vDash \phi(b_1,\ldots, b_n)\iff (\Bbb R,\le)\vDash \phi(b_1,\ldots, b_n)$$

Assume that $\phi(x_1,\ldots,x_n) $ has the form $$ Q_1 y_1Q_2 y_2Q_3 y_3\ldots Q_my_m\colon\psi(x_1,\ldots, x_n,y_1,\ldots,y_m)$$ where each $Q_i$ is either $\forall $ or $\exists$. We can show $(1)$ by induction on the number $m$ of quantors.

If $m=0$, it is clear that $(1)$ holds as we are left just with a logical combination of a bunch of true or false relations among given rationals.

For $m>0$, first assume that $Q_1=\forall$.

To show $\Rightarrow$, assume the left hand side of $(1)$ is true. Let $y_1\in\Bbb R$ be arbitrary. Let $\hat y_1$ be a "nearby" rational, i.e., if $y_1\in\Bbb Q$ let $\hat y_1=y_1$, otherwise let $y_1$ be a rational number in the same open interval determined by the $b_i$ as $y_1$ is. One readily defines a piecewise linear automorphism of $(\Bbb R,\le)$ that leaves the $b_i$ fix and maps $y_1\mapsto \hat y_1$. By induction hypothesis, the equivalence in $(1)$ holds for $$\tag2 Q_2 y_2Q_3 y_3\ldots Q_my_m\colon\psi(x_1,\ldots, x_n,\hat y_1, y_2\ldots,y_m)$$ and we have $(\Bbb Q,\le)\vDash (2)$, hence also $(\Bbb R,\le)\vDash (2)$. Via our piecewise linear automorphism, also $$(\Bbb R,\le)\vDash Q_2 y_2Q_3 y_3\ldots Q_my_m\colon\psi(x_1,\ldots, x_n, y_1, y_2\ldots,y_m).$$ As $y_1$ was arbitrary, we infer that the right hand side of $(1)$ is true, as desired.

To show $\Leftarrow$, assume the right hand side of $(1)$ is true. Let $y_1\in\Bbb Q$ be arbitrary. By induction hypothesis, the equivalence in $(1)$ holds for $$\tag3 Q_2 y_2Q_3 y_3\ldots Q_my_m\colon\psi(x_1,\ldots, x_n, y_1, y_2\ldots,y_m)$$ and we know that $(\Bbb R,\le)\vDash (3)$, hence also $(\Bbb Q,\le)\vDash (3)$. As $y_1$ was arbitrary, we infer that the left hand side of $(1)$ is true, as desired.

A similar argument works if $Q_1=\exists$: One direction works directly, for the other we need can make use of a piecewise linear isomorphism of $(\Bbb R,\le)$ that maps $y_1$ to a "nearby" rational.