(This is related to my question at Computable nonstandard models for weak systems of arithemtic )

Is there a nontrivial computable discrete ordered ring with Euclidean division that is not isomorphic to Z?

If so, what other first-order properties could it share with Z?


Possible properties include:

all numbers with rational square roots are perfect squares

Lagrange 4-square theorem

prime elements are unbounded


Could it satisfy all Pi_1 properties satisfied by Z?

(bounded quantifiers referring to the absolute value being bounded)


Berarducci and Otero in "A Recursive Nonstandard Model of Normal Open Induction" (Journal of Symbolic Logic v61, 1996) give a discretely ordered ring $R$ with recursive operations having the following properties:

  1. $R$ is integrally closed in its quotient field. (So elements with "rational" square roots are perfect squares.)
  2. The prime elements of $R$ are cofinal
  3. $R$ satisfies the induction axioms for quantifier-free formulas

In an earlier paper of Otero (Journal of Symbolic Logic, vol 55, 1990) Otero proves that every model of Open Induction extends to one in which Lagrange's Four-Square Theorem holds. Whether this can be done effectively I don't know.

As for the general question "What properties can a recursively presented discretely ordered ring share with $\mathbb{Z}$": Let's say that a discretely ordered ring $R$ is "diophantine correct" if it satisfies all universal sentences that hold in $\mathbb{Z}$. Assuming that the language of rings has signature $(+, -, \times , \le,0 ,1)$, diophantine correctness amounts to the requirement that any system of polynomial equations and inequalities that are solvable in $R$ is solvable in the standard integers. Incidentally, models of open induction satisfy a weaker property: Any system of equations solvable in some (at least one) model of open induction has a p-adic solution.

The question whether a nonstandard diophantine correct model of open induction can be effectively constructed was raised by Adamowic and Morales-Luna in "A Recursive Model for Arithmetic with Weak Induction", (Journal of Symbolic Logic v50, 1985). I believe that this question is still open. I also believe that the models constructed in the Otero-Berarducci paper are in fact diophantine correct, but the proof of this seems to bump up against open problems in number theory. This is all discussed in an article on diophantine correct open induction by Sidney Raffer in "Set theory, Arithmetic, Philosophy: Essays in Memory of Stanley Tennenbaum (edited by J. Kennedy and R. Kossak), Cambridge University Press. (To appear.)

This is a response to a question from the comments: It is too long to fit there.

Proof of the Euclidean Division Theorem from the axioms of Open Induction: The problem is to show that if $A$ is a model of open induction and if $x,y$ are elements of $A$ with $y>0$ and $x \ge 0 $ then there are unique elements $r, q$ of $A$ such that $x=yq+r$ and $0 \le r < q$. (The statement actually holds for all $x$ and the proof for $x < 0 $ is similar.)

  1. First show that for every $x\in A$ with $x\ge 0$, there is some $q\in A$ such that $yq\le x < y(q+1)$. (Suppose, by way of by contradiction, that $x \ge 0$ and there is no such $q$. Let $S$ be the subset of $A$ defined by the quantifier-free formula $\sigma(q): q \ge 0 \wedge yq\le x$. Show that $S$ contains 0 and is closed under successor. By induction $S$ contains every positive element of $A$. But this is impossible because $x+1$ cannot be in $S$.)

  2. Next, given $y > 0$ and $x \ge 0 $ choose $q$ (as in Part 1) such that $yq \le x < y(q+1)$. Put $r=x-yq$. Using that fact that $A$ is discretely ordered it is follows easily that $r$ and $q$ are the unique elements of $A$ satisfying $x=yq+r$ and $0 \le r < q$.

  • $\begingroup$ Do you know if the ring that article gives has Euclidean division? $\endgroup$ – user5810 Sep 10 '10 at 4:22
  • $\begingroup$ Every model of Open Induction has Euclidean Division. $\endgroup$ – Sidney Raffer Sep 10 '10 at 4:23
  • $\begingroup$ Do you know where I could find a proof of that? $\endgroup$ – user5810 Sep 10 '10 at 4:37
  • $\begingroup$ @Ricky - I don't have access to anything at the moment, but I've added a brief proof-sketch of the Euclidean division theorem to the end of my answer. The proof is exactly what you would think of if you set out to prove the theorem by induction over the ordinary integers. $\endgroup$ – Sidney Raffer Sep 10 '10 at 6:24
  • $\begingroup$ Nice. Although, if I set out to prove the theorem by induction over the ordinary integers, I would do the induction on x in the statement of Euclidean division, rather than q in the formula you used. $\endgroup$ – user5810 Sep 10 '10 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy