8
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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, 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, in: Angus Macintyre (ed.), Logic Colloquium ’77, North-Holland, 1978, pp. 285–296.

[4] Emil Jeřábek, Division by zero, Archive for Mathematical Logic 55 (2016), no. 7, pp. 997–1013.

$\endgroup$
  • $\begingroup$ I had a nagging déjà écrit feeling the whole time. Now I found it: mathoverflow.net/a/168412 . $\endgroup$ – Emil Jeřábek Jan 22 '15 at 12:02
  • $\begingroup$ Emil, thank you very much for your very conclusive answer! I will look at your references wrt. formal MRDP and your proof. $\endgroup$ – srs Jan 22 '15 at 14:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Whoops, I meant "... does not show". I even was consistent with the missing negation! Thanks for pointing this out. $\endgroup$ – srs Jan 21 '15 at 21:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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