3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Do you know (1) the downward Löwenheim–Skolem theorem (which implies that $(\Bbb{R}, \le)$ has a countable elementary substructure) and (2) the theorem (due to Cantor) that any two countable dense linear orders without endpoints are order-isomorphic? Aside: you should learn a bit about quantifier-elimination: the quantifier-elimination process in this case is easy and intuitive. $\endgroup$ – Rob Arthan Sep 16 '18 at 20:11
  • $\begingroup$ @RobArthan I don't think those two ingredients are enough. Suppose $M$ is a countable elementary substructure of the reals. To conclude that the rationals are an elementary substructure of the reals, you have to show that there's an automorphism of the reals moving $M$ to the rationals. And that's not true for an arbitrary $M$ (e.g. the set of all rationals in $(0,1)$). $\endgroup$ – Alex Kruckman Sep 16 '18 at 20:57
  • 1
    $\begingroup$ @AlexKruckman: You are right. I was reading the question as asking if the rationals could be embedded as an elementary substructure of the reals. $\endgroup$ – Rob Arthan Sep 16 '18 at 21:06
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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