5
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Sep 5, 2012 at 15:14

1 Answer 1

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I don't quite understand this argument. There are non-archimedean fields which are models of T', right? $\endgroup$ Sep 5, 2012 at 14:29
  • $\begingroup$ Sure. However, a sentence is provable in $T'$ if and only if it holds in all archimedean fields. $\endgroup$ Sep 5, 2012 at 14:46
  • $\begingroup$ 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. $\endgroup$ Sep 5, 2012 at 15:10
  • $\begingroup$ @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. $\endgroup$ Oct 13, 2012 at 4:09

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.