Let us define a countable model $\cal{M}$ = $(M,+_M ,\cdot_M, <_M)$ of $Q$ (Robinson arithmetic) to have a (primitive) recursive presentation if $\cal{M}$ is isomorphic to $(\omega, \oplus, \otimes)$, where $\omega$ is the set of natural numbers, and $\oplus$, and $\otimes$ are (primitive) recursive functions.

Similarly we can define what it means for $\cal{M}$ to have a feasible presentation, by insisting that $\oplus$, and $\otimes$ are polynomial-time computable functions (and representing natural numbers by their base-2 representations).


(1) Is there a nonstandard model of the fragment IOpen of $PA$ with a feasible presentation? IOpen is a subsystem of Peano arithmetic whose induction axioms are limited to open (quantifier free) formulae.

(2) Suppose a model $\cal{M}$ of IOpen has a recursive (i.e., computable) presentation, does $\cal{M}$ also a primitive recursive presentation? If so, and the answer to (1) is positive, does it have a feasible presentation?

Motivation for the Questions.

  1. Shepherdson (1967) showed that (a) models of IOpen are precisely the integer parts of real closed fields; and (b) in contrast to $PA$, there are nonstandard models of IOpen that have a recursive presentation.

  2. As shown in this paper (which appeared in Theor. Comp. Sci. 2017), in certain classes of structures the notion of having a recursive presentation coincides with the notion of having a primitive recursive presentation; and in some other classes of structures, these two notions diverge (but the paper does not address the status of models of arithmetic).

  3. Shepherdson's work was extended by a number of researchers, including Berarducci, Otero, Moniri, and most recently (to my knowledge) Mohsenipour, who constructed a recursive nonstandard model for IOpen with the GCD property and cofinal primes (in the reference below, he informed me that his construction results in a primitive recursive presentation).

Mohsenipour, Shahram, A recursive nonstandard model for open induction with GCD property and cofinal primes. (English summary) Logic in Tehran, 227–238, Lect. Notes Log., 26, Assoc. Symbol. Logic, La Jolla, CA, 2006.

  • 1
    $\begingroup$ I think Shepherdson’s model of IOpen may well be feasible. What it boils down is, is there a feasible presentation of the field of real algebraic numbers (or another real closed field)? $\endgroup$ – Emil Jeřábek Nov 18 '18 at 19:12
  • $\begingroup$ @EmilJeřábek Thanks for your feedback Emil; your "boling down" comment is on the dot. $\endgroup$ – Ali Enayat Nov 18 '18 at 19:48
  • 2
    $\begingroup$ @EmilJeřábek, it seems that one can present the algebraics feasibly, since for an integer polynomial of degree $n$ with coefficients absolutely bounded by $2^r$, we can isolate roots in time at most $O(n^4 + n^3r^2)$. See Michael Sagraloff and Kurt Mehlhorn, Computing Real Roots of Real Polynomials. $\endgroup$ – Matt F. Nov 19 '18 at 1:45
  • 2
    $\begingroup$ Here is the link for the paper mentioned by Matt's comment: people.mpi-inf.mpg.de/~msagralo/RealRootComputation.pdf $\endgroup$ – Ali Enayat Nov 19 '18 at 21:44

Your Answer

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

Browse other questions tagged or ask your own question.