Take the 2-minute tour ×

After thinking on Joel's answer at Computable nonstandard models for weak systems of arithemtic for a few days, I do not see how to develop enough tuple machinery in I-Sigma_0 (PA with induction restricted to Sigma_0 formulas) to prove the necessary result.

Does I-Sigma_0 prove that "for any number d, there is a number c coding the set of Turing machine programs less than d that halt on input 0 with output 0 in at most d steps", with a coding such that determining whether a standard number n is in the set is computable from (=,0,S,+,*)?

With the coding Joel suggested, which is code(set) := $\displaystyle\Pi_{n \in set} \; p_n$, I don't even see a way for I-Sigma_0 to prove "For all n, there is a number coding the set of numbers less than n", and I can't think of a better coding either.

share|improve this question
This seems to need the totality of exp. I don't think you can get by with less than that if you want a reasonable coding. I would suggest working in $I\Delta_0 + Exp$ unless you have a really reason to only work in $I\Delta_0$. –  François G. Dorais Sep 15 '10 at 13:42
I don't see how I_Delta_0 + Exp can prove it, either. (Although I do see how Elementary Arithmetic citeseerx.ist.psu.edu/viewdoc/summary?doi= could prove it.) –  Ricky Demer Sep 15 '10 at 19:17
Ricky, the coding proof I had in mind seems to use more than $\Delta_0$ induction. François, for the Tennenbaum application, you don't actually need totality, but only that the coding overspills into the nonstandard part---it suffices if we have a single nonstandard $d$ for which there is a code of the length $d$ computations. For this, $\Sigma_1$ induction suffices, since the fact that for every $n$ has a code is true in the standard part, and hence overspills. This is also why it suffices to prove as Dave mentions that there is a nonstandard initial segment with PA, or $\Sigma_1$-induction. –  Joel David Hamkins Sep 15 '10 at 20:58
(I think) You don't even need Sigma_1 induction, you just need Elementary Arithmetic. –  Ricky Demer Sep 15 '10 at 22:14
The problem is not defining a coding of sequences, it is easy to define a coding for sequences (checking if if s is a valid code and computing the i-th member of s, concatenating two sequences, computing the length of the sequence, ...), the problem is proving the totality of the coding, which intuitively should not be possible for reasonable theories as long as they can't prove exponentiation is total, and if you can prove totality of exponentiation then it is easy to prove the totality of the coding. –  Kaveh Sep 16 '10 at 4:45
show 4 more comments

1 Answer

up vote 2 down vote accepted

As I recall, McAloon's method for proving that there are no computable nonstandard models of $I\Delta_0$ was to show that there are initial segments that are nonstandard models of PA. The usual Tennenbaum tricks can then be used to show that addition and multiplication are not computable.

Additional Comment-- Here are references for McAloon's paper and the paper of Wilmers that proves a similar result for $IE_1$ the fragment of $I\Delta_0$ where you only have induction for formulas with bounded existential quantifiers

McAloon, Kenneth, On the complexity of models of arithmetic. J. Symbolic Logic 47 (1982), no. 2, 403--415.

Wilmers, George Bounded existential induction. J. Symbolic Logic 50 (1985), no. 1, 72--90.

share|improve this answer
Does he then prove that there is a decidable such initial segment? In either case, do you have a reference? –  Ricky Demer Sep 15 '10 at 19:19
Ricky, you don't need that the initial segment is computable---if you know the whole structure is computable, then the fact that there is a nonstandard iniinitial segment with PA gives you a nonstandard $d$ with a code for the halting problem for computations of length $d$, and then you simply appeal to the arithmetic of the big structure again, to find the computable separation as I explained in my answer to the other question. –  Joel David Hamkins Sep 15 '10 at 21:01
Excellent point, Joel. Although, if I-Sigma_0 doesn't prove "For all n, there is a number coding the set of numbers less than n", this would seem to contradict the statement that it "is able to perform basic Goedel coding" from your answer to my other question. Also, is there an online reference for McAloon's result? –  Ricky Demer Sep 15 '10 at 22:08
I've edited my answer to include references. –  Dave Marker Sep 15 '10 at 22:25
Don't worry Dave, I will accept your answer, I'm just hoping Joel will respond first. –  Ricky Demer Sep 16 '10 at 4:09
add comment

Your Answer


