3
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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$. $\endgroup$
    – François G. Dorais
    Commented Sep 15, 2010 at 13:42
  • $\begingroup$ 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=10.1.1.105.6509 could prove it.) $\endgroup$
    – user5810
    Commented Sep 15, 2010 at 19:17
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Sep 15, 2010 at 20:58
  • $\begingroup$ (I think) You don't even need Sigma_1 induction, you just need Elementary Arithmetic. $\endgroup$
    – user5810
    Commented Sep 15, 2010 at 22:14
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Sep 16, 2010 at 4:45

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Does he then prove that there is a decidable such initial segment? In either case, do you have a reference? $\endgroup$
    – user5810
    Commented Sep 15, 2010 at 19:19
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Sep 15, 2010 at 21:01
  • $\begingroup$ 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? $\endgroup$
    – user5810
    Commented Sep 15, 2010 at 22:08
  • $\begingroup$ I've edited my answer to include references. $\endgroup$
    – Dave Marker
    Commented Sep 15, 2010 at 22:25
  • $\begingroup$ Don't worry Dave, I will accept your answer, I'm just hoping Joel will respond first. $\endgroup$
    – user5810
    Commented Sep 16, 2010 at 4:09

You must log in to answer this question.