A question about open induction - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T12:23:06Z http://mathoverflow.net/feeds/question/23796 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23796/a-question-about-open-induction A question about open induction SJR 2010-05-06T23:35:37Z 2011-02-03T18:12:58Z <p>An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction if and only if for all $n>1$, there is a homomorphism from $R$ onto $\mathbb{Z}/n\mathbb{Z}$. </p> <p>Wilkie's proof proceeds by adjoining transcendental elements to $R$, but it is not clear that this is ever necessary:</p> <p>Does every ring that extends to a model of open induction have an algebraic extension to a model of open induction?</p> <p>Does anyone know anything about this? I know of no place in the literature where the question is even mentioned, although it has come up more than once in conversation.</p> <p>Here is simple test-case: Let $R$ be the ring $\mathbb{Z}[t,\sqrt{2}t-r]$, where $r$ is a real transcendental and $t$ is an indeterminate. Order $R$ by declaring $t$ positive infinite. It is not hard to show that $R$ extends to a model of true arithmetic. I don't know if $R$ has an algebraic extension to a model of open induction.</p> http://mathoverflow.net/questions/23796/a-question-about-open-induction/23858#23858 Answer by SJR for A question about open induction SJR 2010-05-07T14:24:11Z 2010-05-07T15:18:10Z <p>Andrej Bauer asked in a comment, "What is a model of open induction?" Let me give the most modern and relevant answer and then explain the term "open induction", which is somewhat archaic.</p> <p>Let $F$ be an ordered field. An (ordered) subring $R$ of $F$ is called an "integer part" of $F$ if </p> <ol> <li><p>$R$ is discretely ordered: This means the inequality <code>$x &lt; y &lt; x+1$</code> has no solution in $R$. Equivalently, nothing in $R$ lies between 0 and 1.</p></li> <li><p>For all $x\in F$ there is some $r\in R$ such that <code>$r\le x &lt; r+1$</code>. </p></li> </ol> <p>Item 2 is equivalent to saying that every element of $F$ is a finite distance from some element of $R$, where "finite" means bounded by an element of $\mathbb{Z}$. Remember that $F$ can and usually will be nonarchimedian. </p> <p>Items 1 and 2 together imply that there is a unique function $\lfloor\cdot\rfloor$ from $F$ to $R$ given by the inequality <code>$\lfloor x \rfloor \le x &lt; 1+\lfloor x \rfloor$</code>. Think of this as an abstract analog of the integer part operator. </p> <p>A "model of open induction" is an integer part of a real closed field. Mourges and Ressayre proved that every real closed field has an integer part. The term "open induction" comes from a paper of Shepherdson, who started this whole topic by proving that an ordered ring $R$ is an integer part of its real closure if and only if the positive semiring of $R$ satisfies the axioms of Peano Arithmetic, with the induction axioms restricted to quantifier-free (i.e. open) formulas. Shepherdson also gave recursively presentable nonstandard models of open induction, which is interesting because according to Tennenbaum's Theorem there are no such models of Peano Arithmetic. </p> <p>Since then there have been many successful attempts to build recursive nonstandard models of theories a little stronger than open induction. The champ, to-date, is a recursive nonstandard normal model of open induction, given in a paper by Otero and Berarducci. Here "normal" means integrally closed in its quotient field.</p> <p>The main unsolved problems concerning open induction, in my opinion, are (1) Is the universal theory of open induction decidable (i.e. is it decidable whether a diophantine equation has a solution in some model of open induction) and (2) Is there a recursive non-standard diophantine correct model of open induction, where "diophantine correct" means "extends to a model of true arithmetic".</p> http://mathoverflow.net/questions/23796/a-question-about-open-induction/54209#54209 Answer by Emil Jeřábek for A question about open induction Emil Jeřábek 2011-02-03T16:07:50Z 2011-02-03T18:12:58Z <p>I think that the answer in general is “no”, and that this follows from results in a paper “Limit computable integer parts” by D'Aquino, Knight, and Lange (http://www.nd.edu/~klange1/Research/LimitIPJuly12.pdf). Namely, by Theorem 3.5 and Remark 3, there exists a real-closed field $R$ with an element $r\in R$ and a $\mathbb Z$-ring $I\subseteq R$ such that no discretely ordered subring $I\subseteq J\subseteq R$ intersects $[r,r+1)$, but $b/i\in[r,r+1)$ for some $b,i\in I$. Then $I$ (being a $\mathbb Z$-ring) can be extended to a model of $\mathit{IOpen}$, but no such extension can be found in its real closure $\operatorname{rcl}(I)\subseteq R$ (since no discretely ordered $I\subseteq J\subseteq \operatorname{rcl}(I)$ can contain an integer part of $b/i$).</p> <p>Caveat: the paper is so far an unpublished preprint, and I have actually serious doubts about its correctness. Namely, the claim “$\frac{p(a)}n+z$ cannot be in $(0,1)$” in the proof of the widely used Proposition 3.1 is unjustified, and in fact, I think that this proposition <s>directly</s> contradicts Example 2 (take $I=(x^2+1)\mathbb Q[x^2]+\mathbb Z$, $R=\operatorname{rcl}(\mathbb Q(x))$, and $a=x$; then conditions 2 and 3 hold as $I[x]=I+xI$ is easily seen to be discretely ordered, but condition 1 does not). However, I <em>think</em> that this does not affect the proof of Theorem 3.5, since all the elements which 3.1 is applied on there are (or can be taken to be) transcendental.</p>