10
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Can you please explain what it means for a ring to "model open induction"? $\endgroup$ May 7, 2010 at 13:31

2 Answers 2

7
$\begingroup$

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

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

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

$\endgroup$
2
  • 3
    $\begingroup$ Interesting. In Brouwerian intuitionism the following is called "open induction", where $A \subseteq [0,1]$ is an open subset of the unit interval: $(\forall x \in [0,1] . (\forall y < x . y \in A) \implies x \in A) \implies [0,1] = A$. This seems unrelated to what you are talking about. $\endgroup$ May 7, 2010 at 15:27
  • 5
    $\begingroup$ I think this should have been edited into the question instead of posted as an answer. In any case, this should be community wiki. $\endgroup$ May 7, 2010 at 22:42
6
$\begingroup$

I think that the answer in general is “no”, and that this follows from results by D’Aquino, Knight, and Lange [1].

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

Reference:

[1] Paola D’Aquino, Julia Knight, Karen Lange: Limit computable integer parts, Archive for Mathematical Logic 50 (2011), no. 7, pp. 681–695, doi:10.1007/s00153-011-0241-z. Erratum in: Archive for Mathematical Logic 54 (2015), no. 3, pp. 487–489, doi:10.1007/s00153-015-0418-y

$\endgroup$
2
  • $\begingroup$ Emil, Thanks very much for the reference. I'm not sure that Example 2 DIRECTLY contradicts Proposition 3.1, because (in the example you gave) $\mathbb{Z}[(x^2+1)/4]$ is not a Z-ring, as Prop. 3.1 requires it to be. But I'll have to think about this. $\endgroup$ Feb 3, 2011 at 17:12
  • $\begingroup$ Fair enough, thanks for pointing it out. Hopefully it's correct now. $\endgroup$ Feb 3, 2011 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.