Computable nonstandard models for weak systems of arithemtic - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T17:47:18Z http://mathoverflow.net/feeds/question/38160 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38160/computable-nonstandard-models-for-weak-systems-of-arithemtic Computable nonstandard models for weak systems of arithemtic Ricky Demer 2010-09-09T09:30:27Z 2013-02-08T23:34:45Z <p>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.)</p> <p>Is any system strictly weaker than PA known to have no computable nonstandard models?</p> <p>What other systems weaker than PA are known to have computable nonstandard models?</p> <p>.</p> <p>possible examples of either include:</p> <p>I-Delta-0, I-Delta-0(exp), I-Sigma-1</p> <p>Elementary Function Arithmetic</p> <p>Elementary Recursive Arithmetic, Primitive Recursive Arithmetic</p> <p>Robinson arithmetic + Euclidean division, Robinson arithmetic + Euclidean division + order relation is total</p> http://mathoverflow.net/questions/38160/computable-nonstandard-models-for-weak-systems-of-arithemtic/38162#38162 Answer by Joel David Hamkins for Computable nonstandard models for weak systems of arithemtic Joel David Hamkins 2010-09-09T11:26:43Z 2010-09-09T11:26:43Z <p>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.</p> <p>The proof I have in mind is the following, which I also explained in <a href="http://mathoverflow.net/questions/12426/is-there-a-computable-model-of-zfc/12434#12434" rel="nofollow">this MO answer</a>. 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 <a href="http://en.wikipedia.org/wiki/Recursively_inseparable_sets" rel="nofollow">computably inseparable</a>, 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</p> <p>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.</p> <p>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?</p> <p>This is a comparatively simple statement in arithmetic, and any theory proving it will not have computable nonstandard models.</p> http://mathoverflow.net/questions/38160/computable-nonstandard-models-for-weak-systems-of-arithemtic/38166#38166 Answer by Dave Marker for Computable nonstandard models for weak systems of arithemtic Dave Marker 2010-09-09T12:35:48Z 2010-09-09T18:52:23Z <p>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$.</p> <p>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$.</p> http://mathoverflow.net/questions/38160/computable-nonstandard-models-for-weak-systems-of-arithemtic/121252#121252 Answer by Kaveh for Computable nonstandard models for weak systems of arithemtic Kaveh 2013-02-08T23:34:45Z 2013-02-08T23:34:45Z <p>$\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}$, ...</p> <p>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}$.</p> <p>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. </p> <p>It is known that $\mathsf{IOpen}$ plus <em>cofinality of primes</em> and <em>Bezout</em> axioms has computable non-standard models. Over $\mathsf{IOpen}$, <em>Bezout</em> implies <em>normality</em> and <em>GCD</em> axioms and is provable in $\mathsf{IE_1}$. </p>