Computable rings similar to Z

2010-09-10T02:30:35Z

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)

Answer by SJR for Computable rings similar to Z

2010-09-10T04:11:11Z

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:

$R$ is integrally closed in its quotient field. (So elements with "rational" square roots are perfect squares.)
The prime elements of $R$ are cofinal
$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.)

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

Computable rings similar to Z - MathOverflow

Computable rings similar to Z

Answer by SJR for Computable rings similar to Z