Skip to main content
1 of 2
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

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.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k