18
$\begingroup$

By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of Robinson arithmetic, which also happens to make the order relation total. Since Presburger arithmetic is decidable, we can add axioms giving it a nonstandard number and work through Henkin's proof of the completeness theorem to get a computable nonstandard model of Presburger arithmetic. (There's probably a simpler way to get one, though.)

Is any system strictly weaker than PA known to have no computable nonstandard models?

What other systems weaker than PA are known to have computable nonstandard models?

.

possible examples of either include:

I-Delta-0, I-Delta-0(exp), I-Sigma-1

Elementary Function Arithmetic

Elementary Recursive Arithmetic, Primitive Recursive Arithmetic

Robinson arithmetic + Euclidean division, Robinson arithmetic + Euclidean division + order relation is total

Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
14
$\begingroup$

One of the usual ways of proving Tennenbaum's theorem also applies to many of the theories on your list, and so they can have no computable nonstandard models.

The proof I have in mind is the following, which I also explained in this MO answer. Let $A$ be the set of Turing machine programs that halt on input $0$ with output $0$, and let $B$ be the set of programs that halt on input $0$ with output $1$. These sets are disjoint and computably inseparable, meaning that there is no computable $C$ containing $A$ and disjoint from $B$. Now, suppose that $M$ is a nonstandard model of arithmetic. Let $d$ be a nonstandard natural number, and inside $M$, consider the set of programs below $d$ that halt on input $0$ in at most $d$ steps with output $0$. In $M$, this is a (nonstandard) finite list, and so there is a nonstandard number $c$ coding this list of programs. Now, let $C$ be the set of standard programs $p$ that $M$ thinks appear on the list coded by $c$. This includes every program in $A$, since all such programs halt in a standard finite time with output $0$, and hence $M$ will agree that they halt before time $d$. Second, for a similar reason, this set includes no programs in $B$, since those programs halt in finite time with output $1$, and $M$ will see that. Finally, the set $C$ is computable from the operations of $M$, since we need only perform the decoding procedure to see if a given number $p$ is on the list coded by $c$. For example, we might use the coding that would require us merely to check whether $M$ thinks that the $p^{th}$ binary digit of $c$ is $1$ or not. If the operations of $M$ were computable, then this would be a computable procedure, in contradiction to the fact that $A$ and $B$ are computably inseparable. QED

Now, we haven't really used much of PA in this argument. Any theory $T$ that is able to perform basic Goedel coding and simulate Turing machine computations will be sufficient for the argument. This includes any $I\Sigma_n$, even $I\Sigma_0$, since the operation of a Turing machine is inductively iterating a very trivial process. So none of the stronger theories on your list have computable nonstandard models.

Meanwhile, however, I am unsure about the very weakest theories on your list, but this argument reduces the question to: can the given theory prove that for any number $d$, there is a number $c$ coding the list of Turing machine programs less than $d$ that halt on input $0$ with output $0$ in at most $d$ steps?

This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Since the function taking $d$ to the code $c$ of that list of programs is primitive recursive, as well as the de-coding function, it seems that the argument also captures PRA. $\endgroup$
    – Joel David Hamkins
    Commented Sep 9, 2010 at 11:45
  • $\begingroup$ Now, I've only managed to find one paper describing how to code sequences in PA, but that paper uses existential quantification in the decoding procedure. How can sets be coded so membership is computable from the model operations? $\endgroup$
    – user5810
    Commented Sep 9, 2010 at 16:57
  • $\begingroup$ This is a fun exercise in coding and computability. It may be easiest to code a finite set $A$ with the product of primes $p_n$ for $n\in A$, where $p_n$ is the $n^{th}$ prime. Given a nonstandard model $M$ with code $c$, a standard $n$ is in the set coded by $c$ iff the prime $p_n$ divides $c$ in $M$. But if the $+$ and $\cdot$ of $M$ are computable, then so is the residue of $c$ mod $p$; just look for which one of $c,c+1,c+2,\ldots c+(p-1)$ is a multiple of $p$ in $M$, by exhaustive search for the missing factor. Thus, the decoding is computable. $\endgroup$
    – Joel David Hamkins
    Commented Sep 9, 2010 at 19:31
  • $\begingroup$ Then, how do you define "p is the nth prime"? $\endgroup$
    – user5810
    Commented Sep 9, 2010 at 19:44
  • 1
    $\begingroup$ When $n$ is standard, which is all we care about here, we can compute the $n^{th}$ prime directly, outside of $M$, and then add $1$ to itself inside $M$ that many times. $\endgroup$
    – Joel David Hamkins
    Commented Sep 9, 2010 at 19:55
14
$\begingroup$

$\mathsf{IE_1}$ doesn't have computable non-standard models. (George Wilmers, "Bounded existential induction", 1985) Any theory that contains it will not have computable non-standard models, e.g.: $\mathsf{I\Delta_0}$, $\mathsf{PRA}$, ...

On the other hand, $\mathsf{IOpen}$ does have computable non-standard models (J. C. Shepherdson, "A non-standard model for a free variable fragment of number theory", 1964). Any theory contained in it will also have computable non-standard models, e.g.: $\mathsf{Q}$.

The threshold(s) of having a computable non-standard model is somewhere between $\mathsf{IOpen}$ and $\mathsf{IE_1}$. There are various principles that one can add to $\mathsf{IOpen}$ and see if the resulting theory still has a computable non-standard model.

It is known that $\mathsf{IOpen}$ plus cofinality of primes and Bezout axioms has computable non-standard models. Over $\mathsf{IOpen}$, Bezout implies normality and GCD axioms and is provable in $\mathsf{IE_1}$.

Improve this answer
$\endgroup$
11
$\begingroup$

Sheperdson showed that if there are recursive nonstandard models of open induction--the theory where the induction axioms are restricted to quantifier free formulas. The construction is algebraic. Let $R$ be the real algebraic numbers. Let $K$ be the field of Puiseux series over R, that is series in $t^{1/n}$ with coefficients from $R$ for each natural number $n$. Then let $M$ be the elements of $K$ of the form $f+n$ where $n$ is an integer, $f=0$ or all exponents in $f$ are negative, and the leading coefficient of $f+n$ is positive. Then $M$ is a model of open induction. To show how weak this theory is $\sqrt 2$ is rational in $M$.

In the other hand, George Wilmers showed that if you consider IE$_1$ the theory where you allow induction over formulas with only bounded existential quantifier, then there are no computable models improving a theorem of McAloon's for I$\Delta_0$--though I'm not sure it's known if IE$_1$ is actually weaker than I$\Delta_0$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Dave, you seem to have an extra "if" in your first sentence. $\endgroup$
    – Joel David Hamkins
    Commented Sep 9, 2010 at 22:34

You must log in to answer this question.