I have a signature given with the real numbers as its universe and addition and multiplication as functions. I need to write the following expression in First Order Logic.

  • $x$ is a rational number

My idea: $\varphi(x) = \exists a \, \exists b \, x = \frac{a}{b}$.

The problem is I don't have division.

Extra question: how can I write

  • $x \geq 0$?
  • 4
    $\begingroup$ How about $bx=a$ instead of $x=\frac{a}{b}$. $\endgroup$ – Lee Mosher Jan 9 '17 at 16:06
  • 6
    $\begingroup$ The real question IMO is, how do you denote the fact that $a$ and $b$ are integers? With only $\times,+$ and $\mathbb{R}$ it seems somewhat infeasible. $\endgroup$ – barak manos Jan 9 '17 at 16:07
  • 1
    $\begingroup$ Regarding the extra question: $x\ge0\iff \exists y\colon x=y^2$ $\endgroup$ – Hagen von Eitzen Jan 9 '17 at 16:09
  • $\begingroup$ @HagenvonEitzen Thank you very much. Why didn't I think that? $\endgroup$ – MessitÖzil Jan 9 '17 at 16:11
  • 1
    $\begingroup$ You can't express the predicate "is an integer" in first order logic over $({\mathbb{R}},+,\cdot)$. You need second order logic to define that predicate, for instance as the smallest set containing $0$, $1$ and being closed under addition. $\endgroup$ – Magdiragdag Jan 9 '17 at 16:19

Let me strengthen what others have already said:

The structure $\mathcal{R}=(\mathbb{R}; +, \times)$ is decidable (this is due to Tarski). This immediately rules out the possibility of defining $\mathbb{Z}$ in $\mathcal{R}$, since the theory of the integers is undecidable (by Goedel). (Incidentally, since $\mathbb{Z}$ is (nontrivially) definable in $\mathbb{Q}$, this also rules out the possibility of defining $\mathbb{Q}$ in $\mathcal{R}$.)

But in fact more is true: Tarski showed that it is o-minimal, that is, every definable set is a finite union of intervals. So nothing remotely like $\mathbb{Z}$ or $\mathbb{Q}$ can be a definable subset of $\mathcal{R}$.


EDIT: I just noticed you said first order arithmetic. This answer uses second order arithmetic. It's a theorem that it is impossible to define $\mathbb{Z}$ in $(\mathbb{R},+,\cdot)$

As mentioned in the comments, division is easy: define $a/b$ to be the number $c$ such that $cb=a$. It's identifying integers that is hard. Notably, $\mathbb{Z}$ and $\mathbb{Z}[\pi]$ have pretty much the same arithmatic structure. However, you can identify $0$ as the only number that satisfies $$\varphi(x):=\forall a(ax=x)$$ and then you can identify $1$ as the only number that satisfies $$\varphi'(x)=\forall a(\varphi(a)\lor a=ax)$$

Given these two constants, we can then recursively define the integers by using the fact that they are generated by $1$ as a group under addition, a la the Peano Axioms.

For your bonus question, again the comments had the right idea.

  • $\begingroup$ but for x to be rational, a and b must not be Integers, right? so $ax=b$ works. $\endgroup$ – MessitÖzil Jan 9 '17 at 16:28
  • $\begingroup$ @user3612693 Showing x is rational requires showing that there are /integer/ a and b such that ax=b. Not any a and b $\endgroup$ – Stella Biderman Jan 9 '17 at 16:30
  • $\begingroup$ and it's NOT possible to say a and b are integers in first order logic over $(R,+,⋅)$ ? $\endgroup$ – MessitÖzil Jan 9 '17 at 16:35
  • $\begingroup$ @user3612693 correct. If it were, then since addition and multiplication are first order properties, all of arithmetic would be. But there are theorems that say that the Peano Axioms cannot be expressed in first orde logic $\endgroup$ – Stella Biderman Jan 9 '17 at 16:37
  • 2
    $\begingroup$ @StellaBiderman That's not really relevant here. The second-order Peano axioms are not first-order expressible, but that doesn't a priori mean that $\mathbb{N}$ isn't a definable subset of the field of reals. Indeed, it is a definable subset of the field of rationals. $\endgroup$ – Noah Schweber Jan 9 '17 at 18:29

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.