Return to Answer

Your paragraph beginning "using the same theorem . . ." is false: it is true that for any computably enumerable theory $T\subseteq Th(\mathbb{N})$ (or $T\supseteq$Robinson if you prefer) there is a polynomial $p$ with no root such that $T$ does not prove "$p$ has no root." However, by contrast:

I claim that, as long as $T$ contains the ordered semiring axioms and $T\subseteq Th(\mathbb{N})$ (that is, $T$ contains only true sentences), then $D_T=D_{Th(\mathbb{N})}$.

To see this, just note that for any polynomial $p$, if $\overline{n}$ is a root of $p(\overline{x})$, then we can use the axioms of arithmetic to show that $p(\overline{n})=0$ - plugging a specific value into a specific polynomial and evaluating is not something which takes logical strength! In the other direction, since $T$ only contains true sentences, if $T$ proves $p$ has a root then $p$ has a root.

So we are done.

Note how little we had to assume about $T$.

EDIT: Given the change to the question, this answer is no longer relevant; I'm going to leave it up because it is worth comparing the OP to the "dual" version of the question.

Your paragraph beginning "using the same theorem . . ." is false: it is true that for any computably enumerable theory $T\subseteq Th(\mathbb{N})$ (or $T\supseteq$Robinson if you prefer) there is a polynomial $p$ with no root such that $T$ does not prove "$p$ has no root." However, by contrast:

I claim that, as long as $T$ contains the ordered semiring axioms and $T\subseteq Th(\mathbb{N})$ (that is, $T$ contains only true sentences), then $D_T=D_{Th(\mathbb{N})}$.

To see this, just note that for any polynomial $p$, if $\overline{n}$ is a root of $p(\overline{x})$, then we can use the axioms of arithmetic to show that $p(\overline{n})=0$ - plugging a specific value into a specific polynomial and evaluating is not something which takes logical strength! In the other direction, since $T$ only contains true sentences, if $T$ proves $p$ has a root then $p$ has a root.

So we are done.

Note how little we had to assume about $T$.

I claim that, as long as $T$ contains the ordered semiring axioms and $T\subseteq Th(\mathbb{N})$ (that is, $T$ contains only true sentences), then $D_T=D_{Th(\mathbb{N})}$.

To see this, just note that for any polynomial $p$, if $p$ has a root then certainly $T$ proves $p$ has a root; and in the other direction, since $T$ only contains true sentences, if $T$ proves $p$ has a root then $p$ has a root.

So we are done.

Note how little we had to assume about $T$.

Your paragraph beginning "using the same theorem . . ." is false: it is true that for any computably enumerable theory $T\subseteq Th(\mathbb{N})$ (or $T\supseteq$Robinson if you prefer) there is a polynomial $p$ with no root such that $T$ does not prove "$p$ has no root." However, by contrast:

I claim that, as long as $T$ contains the ordered semiring axioms and $T\subseteq Th(\mathbb{N})$ (that is, $T$ contains only true sentences), then $D_T=D_{Th(\mathbb{N})}$.

To see this, just note that for any polynomial $p$, if $\overline{n}$ is a root of $p(\overline{x})$, then we can use the axioms of arithmetic to show that $p(\overline{n})=0$ - plugging a specific value into a specific polynomial and evaluating is not something which takes logical strength! In the other direction, since $T$ only contains true sentences, if $T$ proves $p$ has a root then $p$ has a root.

So we are done.

Note how little we had to assume about $T$.

Let $T$ be an "appropriate" theory - this means $T\subseteq Th(\mathbb{N})$, and $T$ is strong enough to talk about Turing machines (I'm almost certain containing Robinson arithmetic is enough, but I could be wrong, I don't know much about it). Then we have, for any Turing machine $\Phi_e$, $$\Phi_e(e)\text{ halts}\iff e\in 0'\iff T\vdash\text{"$\Phi_e(e)$ halts"}.$$ But the statement "$\Phi_e(e)$ halts" is equivalent mod $T$ (in fact, mod Robinson arithmetic) to the existence of a root of a polynomial $p_e$, and the passage from $e$ to $p_e$ is computable. So if $D_T$ were decidable, $0'$ would be computable.

Note that we did not assume that $T$ was computably axiomatizable!

I claim that, as long as $T$ contains the ordered semiring axioms and $T\subseteq Th(\mathbb{N})$ (that is, $T$ contains only true sentences), then $D_T=D_{Th(\mathbb{N})}$.

To see this, just note that for any polynomial $p$, if $p$ has a root then certainly $T$ proves $p$ has a root; and in the other direction, since $T$ only contains true sentences, if $T$ proves $p$ has a root then $p$ has a root.

So we are done.

Note how little we had to assume about $T$.