Return to Answer

Let me remark that while the answer above exploits the weakness of $Q$ which allows for quite pathological models, reasonable stronger base theories can still make a trouble. In particular, it is a long-standing open problem whether the universal fragment of the theory of quantifier-free induction ($\mathit{IOpen}$) is decidable; if it is, then one can construct a counterexample $T$ as above with $T\supseteq\mathit{IOpen}$. [EDIT: While I’m pretty sure the existence of models of $\mathit{IOpen}$ with decidable existential theory is also an open problem, it’s stronger than decidability of its universal fragment: we would need decidability of Boolean combinations of $\exists$ sentences, or some kind of amalgamation property.]

[2] Verena H. Dyson, James P. Jones, and John C. Shepherdson, Some diophantine forms of Gödel’s theorem, Archiv für mathematische Logik und Grundlagenforschung 22 (1982), pp. 51–60. http://gdz.sub.uni-goettingen.de/index.php?id=resolveppn&PID=GDZPPN002045400

As a related result, the set of Dophantine sentences consistent with $Q$ is decidable, see https://mathoverflow.net/a/194502 .

Let me remark that while the answer above exploits the weakness of $Q$ which allows for quite pathological models, reasonable stronger base theories can still make a trouble. In particular, it is a long-standing open problem whether the universal fragment of the theory of quantifier-free induction ($\mathit{IOpen}$) is decidable; if it is, then one can construct a counterexample $T$ as above with $T\supseteq\mathit{IOpen}$. [EDIT: While I’m pretty sure the existence of models of $\mathit{IOpen}$ with decidable existential theory is also an open problem, it’s stronger than decidability of its universal fragment: we would need decidability of Boolean combinations of $\exists$ sentences, or some kind of amalgamation property.]

[2] Verena H. Dyson, James P. Jones, and John C. Shepherdson, Some diophantine forms of Gödel’s theorem, Archiv für mathematische Logik und Grundlagenforschung 22 (1982), pp. 51–60. https://eudml.org/doc/137991

On the other hand, the answer is positive for theories $T$ extending $I\Delta_0+\mathit{EXP}$, as this theory proves the MRDP theorem.

Reference:

[1] Richard Kaye, Diophantine induction, Annals of Pure and Applied Logic 46 (1990), no. 1, pp. 1–40. http://dx.doi.org/10.1016/0168-0072(90)90076-E

EDIT: I found that the Lemma above, using the same model $M$, was proved by Dyson, Jones and Shepherdson [2]. Better yet, they also found a model $M_1\models Q$ that embeds in the non-negative part of an ordered domain such that the validity of existential sentences of the language $\langle0,S,+,{\cdot},{\le}\rangle$ in $M_1$ is decidable. (The order is not discrete, though. It also does not agree with the usual order defined in $Q$ via $\exists z\,x+z=y$.)

On the other hand, the answer is positive for theories $T$ extending $I\Delta_0+\mathit{EXP}$, as this theory proves the MRDP theorem.

References:

[1] Richard Kaye, Diophantine induction, Annals of Pure and Applied Logic 46 (1990), no. 1, pp. 1–40. http://dx.doi.org/10.1016/0168-0072(90)90076-E

[2] Verena H. Dyson, James P. Jones, and John C. Shepherdson, Some diophantine forms of Gödel’s theorem, Archiv für mathematische Logik und Grundlagenforschung 22 (1982), pp. 51–60. http://gdz.sub.uni-goettingen.de/index.php?id=resolveppn&PID=GDZPPN002045400

EDIT: In fact, the positive answer does not need anything as strong as exponentiation for the base theory, because we do not need full MRDP theorem for Diophantine definability on standard integers. Let $IE_1\subseteq I\Delta_0$ be the fragment of PA with induction only for bounded existential formulas, and $IE_1^-$ its further restriction where induction formulas are not allowed parameters. I will write just $n$ for $S^n(0)$ below.

Theorem: Every partial recursive function $f(\vec x)$ has a Diophantine representation $\phi(\vec x,y)$ in $IE_1^-$, in the sense that

1. $IE_1^-\vdash\forall x,y,y'\,(\phi(\vec x,y)\land\phi(\vec x,y')\to y=y')$.

2. If $f(\vec n)=m$, $IE_1^-\vdash\phi(\vec n,m)$.

Consequently, for every pair of disjoint r.e. sets $A,B$, there is a Diophantine formula $\phi(x)$ such that $n\in A$ implies $IE_1^-\vdash\phi(n)$, and $n\in B$ implies $IE_1^-\vdash\neg\phi(n)$.

The argument is mostly a rehashing of results of Kaye [1]. First, $IE_1$ is $\exists\forall E_1$-conservative over $IE_1^-$ [1, Thm. 5.5], hence we may work in $IE_1$, and every existential formula is easily seen to be equivalent to a Diophantine formula over $IE_1$, hence it suffices to find an existential representation.

EDIT: In fact, the positive answer does not need anything as strong as exponentiation for the base theory, because we do not need full MRDP theorem for Diophantine definability on standard integers. Let $IE_1,IU_1\subseteq I\Delta_0$ be the fragments of PA with induction only for bounded existential formulas and bounded universal formulas, respectively, and $IU_1^-$ a further restriction of $IU_1$ where induction formulas are not allowed parameters. (Actually, $IE_1$ and $IU_1$ with parameters coincide.) I will write just $n$ for $S^n(0)$ below.

Theorem: Every partial recursive function $f(\vec x)$ has a Diophantine representation $\phi(\vec x,y)$ in $IU_1^-$, in the sense that

1. $IU_1^-\vdash\forall x,y,y'\,(\phi(\vec x,y)\land\phi(\vec x,y')\to y=y')$.

2. If $f(\vec n)=m$, $IU_1^-\vdash\phi(\vec n,m)$.

Consequently, for every pair of disjoint r.e. sets $A,B$, there is a Diophantine formula $\phi(x)$ such that $n\in A$ implies $IU_1^-\vdash\phi(n)$, and $n\in B$ implies $IU_1^-\vdash\neg\phi(n)$.

The argument is mostly a rehashing of results of Kaye [1]. First, $IE_1$ is $\forall_1$-conservative over $IU_1^-$, hence we may work in $IE_1$, and every existential formula is easily seen to be equivalent to a Diophantine formula over $IE_1$, hence it suffices to find an existential representation.