Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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