6
$\begingroup$

In the first-order language $\mathscr L$ having $(+, \cdot, 0)$ as signature, it is easy to define a formula $\phi[x]$, namely $\exists y \; x = y^2$, satisfying : $$\text{for all } x \in \Bbb R, \quad x \in \Bbb R_+ \;\text{ if and only if} \;\; \phi[x] $$

My question is : what happens if I replace $\Bbb R$ by $\Bbb Q$ ? More precisely :

Is there a first-order formula $\phi[x]$ of $\scr L$, such that $$\text{for all } x \in \Bbb Q, \quad x \in \Bbb Q_+ \;\text{ if and only if} \;\; \phi[x] $$

Said differently, I would like to know if the set of the positive rationals is definable in that language. Related questions are, for instance : (1), (2).

I don't know if the $\scr L$-structure $(\Bbb Q, +, \cdot, 0)$ admits elimination of quantifiers. If this is the case, then this could be helpful ; see this answer.

Thank you for your comments !

$\endgroup$
13
$\begingroup$

Yes. Every rational number $\ge 0$ is the sum of four squares. This is easily derived from Lagrange's Theorem which says that every non-negative integer is the sum of four squares.

Note that the formula we get is existential.

$\endgroup$
  • $\begingroup$ Thank you for your nice answer ! That may be very easy, but I don't immediately see how you can derive this from Lagrange's Theorem. $\endgroup$ – Watson Feb 3 '16 at 21:06
  • 3
    $\begingroup$ Let $r$ be a non-negative rational. Then $r=\frac{a}{b}$ where $a$ and $b$ are integers, with $b\gt 0 $. So $r=\frac{ab}{b^2}$. Now express $ab$ as a sum of four squares $s^2+t^2+u^2+v^2$. Then $r=(s/b)^2+(t/b)^2+(u/b)^2+(v/b)^2$. $\endgroup$ – André Nicolas Feb 3 '16 at 21:10
2
$\begingroup$

It is a famous result of Julia Robinson that $(\Bbb{Q}, +, \cdot, 0)$ is undecidable. This implies that $(\Bbb{Q}, +, \cdot, 0)$ does not admit elimination of quantifiers. That the rational numbers are not definable in the first-order theory of the reals follows from this, but also follows from well-known facts about O-minimality of the first-order theory of the reals

$\endgroup$
  • $\begingroup$ Thank you for your answer. You gave an answer to my "I don't know if the structure $(\Bbb Q,+,\cdot,0)$ admits elimination of quantifiers", but how is the part of your sentence "the rational numbers are not definable in the first-order theory of the reals" linked to my question ? I apologize if this is trivial, but I don't see how these are related. Anyway, I've learned something :-) $\endgroup$ – Watson Feb 4 '16 at 15:47
  • 1
    $\begingroup$ It was just an extra bit of information that I thought you mind find interesting in this context. $\endgroup$ – Rob Arthan Feb 4 '16 at 20:45

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.