Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D\_T$ as follows:



> 
> Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether
>  $$
> T \vdash \forall \bar{x}\, p(\bar{x}) \neq 0,
> $$
>  i.e., whether $T$ shows that $p$ does not have a root.
> 
> 
> 


By the [MDRP theorem](http://www.logicmatters.net/resources/pdfs/MRDP.pdf#page=6), we know that $D\_T$ is undecidable for $T = \operatorname{Th}(\mathbb{N})$.


Using the same theorem, we can also show that for any *computably enumerable* $T$ there is a $p$ such that $p$ has no root in $\mathbb{N}$, but $T$ does not show this, so $D\_T$ is not equivalent to solving diophantic equations.


My question is for which smaller $T$ the problem $D\_T$ is still undecidable, especially


* $T$ = Peano arithmetic?
* $T$ = Robinson arithmetic?
* Some computably enumerable $T$?
* *Any* computably enumerable $T$ containing, say, P.A. or R.A.? (this is my intuition, but I haven't been able to show it)


**Edit:** Had "... has a root" before, which is kinda trivial (thanks to @NoahS for pointing this out)



Decidability of diophantine equation in a theory
If $T$ contains $I\Delta\_0+\mathit{EXP}$ (or a strong theory like Peano arithmetic for that matter), then by the formalized MRDP theorem [1], $D\_T$ is essentially the $\Pi^0\_1$ fragment of $T$, which is of course undecidable if $T$ is consistent. Curiously, this holds even for some weaker theories that do *not* prove the MRDP theorem: in particular, Kaye [2] showed that $D\_T$ is undecidable for any consistent extension of $IE\_1$ (induction for bounded existential formulas).


On the other hand, it is a long-standing open problem whether $D\_T$ is decidable for the theory of quantifier-free induction (IOpen); by results of Wilkie [3], this is equivalent to the same problem for the theory of $\mathbb Z$-rings.


Concerning Robinson’s arithmetic $Q$: the problem is not quite well defined here, as $Q$ does not prove the usual semiring axioms like distributivity, hence different terms representing the same polynomial may give different answer. Worse yet, the question only makes sense for integer polynomials, whereas the theory only has nonnegative integers, and its models cannot be extended with negatives in a coherent way. So, for definiteness, let me formulate it as
$$\let\ob\overline\let\ub\underline\def\N{\mathbb N}\let\LOR\bigvee
D\_T=\{(p,q):p,r\text{ are $L$-terms, }T\vdash\forall\ob x\,p(\ob x)\ne q(\ob x)\},$$
where $L=(0,S,+,\cdot)$ is the usual language of arithmetic.


EDIT: I realized that the “exercise” in Claim 2 below was incorrect, so let me formulate the result for the slightly stronger theory
$$Q^+=Q+\forall x\,0\cdot x=0$$
where it works. While $D\_Q$ is also decidable, this is considerably more difficult to prove; see [4].



> 
> **Proposition:** $D\_{Q^+}$ is decidable (in fact, coNP-complete).
> 
> 
> 


**Proof:**
The main point is that $Q^+$ has weird models where one can satisfy next to any equation $p(\ob x)=q(\ob x)$, and the exceptions are easy to deal with.


Let $\ub n=S^n(0)$ denote the numeral for $n\in\N$. Consider the model $\N^\infty$ of $Q^+$ with domain $\mathbb N\cup\{\infty\}$, where $x+\infty=\infty+x=x\cdot\infty=\infty\cdot x=\infty$, except that $\infty\cdot0=0\cdot\infty=0$. By induction on the complexity of the term $p$, we show



> 
> **Claim 1:** If the value of $p(\ob\infty)$ in $\N^\infty$ is $n\in\N$, then $Q^+$ proves $\forall\ob x\,p(\ob x)=\ub n$.
> 
> 
> 


Given terms $p,q$, we can compute the value of $p(\ob\infty)$ and $q(\ob\infty)$ in $\N^\infty$. If both equal $\infty$, we have a witness that $(p,q)\notin D\_{Q^+}$ and we are done. By Claim 1, the remaining cases are when one of the terms is provably equal to a standard constant, hence we can assume without loss of generality that $q$ is $\ub n$ for some $n\in\N$.


As a little exercise with the axioms of $Q$, one can show by induction on $n$:



> 
> **Claim 2:** $Q$ proves
>  $$\begin{align\*}
> x+y=\ub n&\to\LOR\_{k,l\colon k+l=n}(x=\ub k\land y=\ub l),\\
> x\cdot y=\ub n&\to x=0\lor\LOR\_{k,l\colon kl=n}(x=\ub k\land y=\ub l)\qquad\text{for }n\ne0,\\
> x\cdot y=0&\to x=0\lor y=0
> \end{align\*}$$
>  for every $n\in\N$.
> 
> 
> 


Let me write $x\le\ub n$ as a shorthand for the formula $x=0\lor x=\ub1\lor\dots\lor x=\ub n$. (In fact, this agrees with the usual definable ordering in $Q$, but I will not need this.) In $Q$, define
$$x^{\le n}=\begin{cases}x&\text{if }x\le\ub n,\\\ub n&\text{otherwise.}\end{cases}$$



> 
> **Claim 3:** $Q^+$ proves $p(\ob x)\le\ub n\to p(\ob x)=p(\ob x^{\le n})$.
> 
> 
> 


Again, we prove this by induction on the complexity of $p$. For example, assume that $p=p\_0\cdot p\_1$. Reason in $Q^+$, and let $p(\ob x)=\ub m$ for some $m=0,\dots,n$. If $m\ne 0$, then $p\_0(\ob x)=\ub k$ and $p\_1(\ob x)=\ub l$ for some $k,l\le n$ such that $kl=m$ by Claim 2 (the case $p\_0(\ob x)=0$ is impossible by the extra axiom). By the induction hypothesis, we have also $p\_0(\ob x^{\le n})=\ub k$ and $p\_1(\ob x^{\le n})=\ub l$, hence $p(\ob x^{\le n})=\ub m$.


If $m=0$, then Claim 2 gives $p\_0(\ob x)=0$ or $p\_1(\ob x)=0$, hence $p\_0(\ob x^{\le n})=0$ or $p\_1(\ob x^{\le n})=0$ by the induction hypothesis, thus $p(\ob x^{\le n})=0$ as well.


Now, resuming the proof of decidability of $D\_{Q^+}$: if there is a model of $Q^+$ in which $p(\ob x)=\ub n$ is satisfiable, then by Claim 3, it is also satisfiable by a tuple of elements of $\{0,\dots,n\}$. The value of $p(\vec x)$ on standard tuples is evaluated the same in all models, hence we can as well do it in the standard model. Thus,
$$(p(\ob x),\ub n)\in D\_{Q^+}\iff\forall\ob x\in\{0,\dots,n\}\,p(\ob x)\ne n,$$
which is a decidable condition.


**References:**


[1] Haim Gaifman and Constantinos Dimitracopoulos, *Fragments of Peano’s arithmetic and the MRDP theorem*, in: Logic and Algorithmic, Monographie No. 30 de L'Enseignement Mathématique, Université de Genève, 1982, pp. 187–206.


[2] Richard Kaye, [*Hilbert's tenth problem for weak theories of arithmetic*](http://dx.doi.org/10.1016/0168-0072%2893%2990198-M), Annals of Pure and Applied Logic 61 (1993), no. 1–2, pp. 63–73.


[3] Alex Wilkie, [*Some results and problems on weak systems of arithmetic*](http://dx.doi.org/10.1016/S0049-237X%2808%2972011-1), in: Angus Macintyre (ed.), Logic Colloquium ’77, North-Holland, 1978, pp. 285–296.


[4] Emil Jeřábek, [*Division by zero*](http://arxiv.org/abs/1604.07309), Archive for Mathematical Logic 55 (2016), no. 7, pp. 997–1013.


