# Is the first order theory of ordered rings without infinitesimals effectively enumerable?

We take an ordered ring to be a structure of type $(+ - \times < 0\,\, 1)$ satisfying the usual axioms. If $A$ is an ordered ring then we say that an element $a$ of $A$ is infinitesimal if for all integers $n$ it holds that $-1<na<1$.

Let $T$ be the set of sentences that hold in every ordered ring that has no infinitesimal elements other than 0.

Question: Is $T$ effectively enumerable? Is the set of universal sentences of $T$ effectively enumerable?

-
Don't know if this is relevant. The first-order theory of the (ordered field of) real numbers is decidable. But of course there is no formula defining $\mathbb Z$ in that theory. So the point is that $T$ is strictly smaller than this theory? – Gerald Edgar Sep 5 '12 at 15:14

The answer to the first question is no. First, let $\chi=\forall x>0\\,\exists y\\,(xy=1)$ and $T'=T+\chi$, so that $T'$ is the first-order theory of archimedean ordered fields. Let $\phi(x)$ be a formula defining $\mathbb Z$ in $\mathbb Q$, and let $\psi$ be the sentence “$\phi(x)$ defines a discretely ordered ring”. Since the only DOR embeddable in an archimedean field are the integers, $\phi(x)$ provides an interpretation of true arithmetic in the theory $T'+\psi$. Thus, $T'+\psi$ is not recursively enumerable, and a fortiori $T$ is not recursively enumerable either. (In fact, $T$ is not even arithmetical.)

Let me spell the argument in more detail. For any sentence $\alpha$, let $\alpha^\phi$ be the sentence obtained by relativizing all quantifiers to $\phi(x)$. Then I claim $$\mathbb Z\models\alpha\iff T\vdash\chi\land\psi\to\alpha^\phi,$$ which implies that $\mathrm{Th}(\mathbb N)$ is recursively reducible to $T$.

Right to left: $\mathbb Q$ is an ordered ring without infinitesimals, hence $\mathbb Q\models\chi\land\psi\to\alpha^\phi$. Also, $\mathbb Q\models\chi\land\psi$ and $\phi(\mathbb Q)=\mathbb Z$, hence $\mathbb Z\models\alpha$.

Left to right: Let $R$ be an ordered ring without infinitesimals, we have to show $R\models\chi\land\psi\to\alpha^\phi$. Assume $R\models\chi\land\psi$. Then $R$ is a field (by $\chi$) and $S=\phi(R)$ is its discretely ordered subring (by $\psi$). Since $R$ has no infinitesimals, it is archimedean, hence so is $S$, which means $S\simeq\mathbb Z$. Thus, $S\models\alpha$, and $R\models\alpha^\phi$.

As for the second question, this is an interesting problem. It may be related to the notorious open problem whether the universal theory of $\mathbb Q$ is decidable (or equivalently, recursively enumerable).

-
I don't quite understand this argument. There are non-archimedean fields which are models of T', right? – Ramiro de la Vega Sep 5 '12 at 14:29
Sure. However, a sentence is provable in $T'$ if and only if it holds in all archimedean fields. – Emil Jeřábek Sep 5 '12 at 14:46
Dealing with first-order theories of classes of structures not closed under elementary equivalence may be confusing, hence I have expanded the answer with more details. I hope it is more clear now. – Emil Jeřábek Sep 5 '12 at 15:10
Thank you Emil, it makes sense to me now. – Ramiro de la Vega Sep 6 '12 at 14:48
@Emil: Thank you for your answer. It doesn't look like there are any takers for the second part of my question, which anyway was added later. – SJR Oct 13 '12 at 4:09