A question about open induction - MathOverflow

A question about open induction

2010-05-06T23:35:37Z

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}$.

Wilkie's proof proceeds by adjoining transcendental elements to $R$, but it is not clear that this is ever necessary:

Does every ring that extends to a model of open induction have an algebraic extension to a model of open induction?

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.

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.

Answer by SJR for A question about open induction

2010-05-07T14:24:11Z

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.

Let $F$ be an ordered field. An (ordered) subring $R$ of $F$ is called an "integer part" of $F$ if

$R$ is discretely ordered: This means the inequality $x < y < x+1$ has no solution in $R$. Equivalently, nothing in $R$ lies between 0 and 1.
For all $x\in F$ there is some $r\in R$ such that $r\le x < r+1$ .

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.

Items 1 and 2 together imply that there is a unique function $\lfloor\cdot\rfloor$ from $F$ to $R$ given by the inequality $\lfloor x \rfloor \le x < 1+\lfloor x \rfloor$ . Think of this as an abstract analog of the integer part operator.

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.

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.

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".

Answer by Emil Jeřábek for A question about open induction

2011-02-03T16:07:50Z

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$).

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 ~~directly~~ 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 think 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.