33
$\begingroup$

In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, +, \cdot$).

It is not hard to see that Robinson's result can be reformulated in the following symmetric form.

Theorem A. The structures ($\Bbb{N}, +, \cdot$) and $(\Bbb{Q}, +, \cdot$) are bi-interpretable.

The following generalization of Theorem A is considered folkore (I am not aware of a published reference).

Theorem B. If $(M, +, \cdot)$ is a model of $PA$ (Peano arithmetic), then the field of rationals $\Bbb{Q}^M$ of $(M, +, \cdot)$ is bi-interpretable with $(M, +, \cdot )$.

Let $EFA$ denote the exponential function arithmetic fragment of $PA$, a fragment also known as $I\Delta_{0}+exp$.

Based on a posteriori evidence classical theorems of Number Theory do not require the full power of $PA$ since they can be already verified in $EFA$ (indeed Harvey Friedman has conjectured that even FLT can be verified in $EFA$, with a proof that would be very different from Wiles').

This suggests that in Theorem B one should be able to weaken $PA$ to $EFA$, hence my question:

Question. Is there a published reference for the strengthening of Theorem B, where $PA$ is weakened to $EFA$?

P.S. The following paper provides an excellent expository account of Robinson's theorem (and related results).

D. Flath and S. Wagon, How to Pick Out the Integers in the Rationals: An Application of Logic to Number Theory, American Mathematical Monthly, Nov. 1991.

$\endgroup$
4
  • $\begingroup$ Ali: Suppose $M\models PA$. To interpret $M$ in $\mathbb{Q}^M$ does Julia Robinson's formula with the operations of $\mathbb{Q}^M$ do the job, or is there something fancier going on? Is your question about how much of the argument in Robinson's paper goes through in models of $I\Delta_0+exp$? $\endgroup$ May 22, 2011 at 5:51
  • $\begingroup$ SJR: The answer to your first question is positive, i.e., nothing fancier is going on. Regarding the second one: the arguments of Robinson's paper should go through in $EFA$ (based on $EFA$'s track record in handling "elementary" number theory); my question is whether anyone has actually shown - in a publishd source - that this is indeed the case. $\endgroup$
    – Ali Enayat
    May 22, 2011 at 16:37
  • 1
    $\begingroup$ @AliEnayat: Have you found an answer to your question yet? I would be very interested to know. $\endgroup$ Mar 11, 2012 at 0:14
  • $\begingroup$ @Samuel Ried: No I have not (sorry for the tardy reply, I have been "away" for a long while). $\endgroup$
    – Ali Enayat
    Apr 11, 2012 at 1:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.