Note on Quantifier Prefixes Over Diophantine Equations
This paper gives a negative answer to 2 questions of \textit{J. P. Jones} [ibid. 27, 403-410 (1981; Zbl 0472.03034)]: For \(P_ 1,P_ 2,Q_ 1,Q_ 2\in {\mathbb{Z}}[x,y]\), do either of the following 2 conditions hold? \[ (1)\quad \forall P_ 1\exists Q_ 1: \{x\in {\mathbb{N}}| \forall y\in {\mathbb{N}},\quad P_ 1(x,y)>0\}=\{x\in {\mathbb{N}}| \exists z\in {\mathbb{N}},\quad Q_ 1(x,z)=0\}, \] \[ (2)\quad \forall P_ 2\exists Q_ 2: \{x\in {\mathbb{N}}| \forall y\in {\mathbb{N}},\quad P_ 2(x,y)\neq 0\}=\{x\in {\mathbb{N}}| \exists z\in {\mathbb{N}},\quad Q_ 2(x,z)=0\}. \] (1) implies (2), since, for \(P_ 1:=P^ 2_ 2\), \(P_ 2\neq 0\) if and only if \(P_ 1>0\). We refute (2), and hence (1), when \(P_ 2:=x-y^ 2\), that is, when the set \(\{\) \(x\in {\mathbb{N}}|\) \(\forall y\in {\mathbb{N}}\), \(P_ 2(x,y)\neq 0\}\) is the set of non-squares. We do this in 2 ways, first using a theorem of R. M. Robinson, then using Hilbert's irreducibility theorem. If the answer to either of Jones' questions had been positive, then Jones could have given an algorithm for deciding which binary Diophantine equations have integral solutions (for Diophantine equations in 9 or more variables, Matijasevič had shown that there is no such algorithm).
- Correction to “Note on Quantifier Prefixes Over Diophantine Equations”
- Classification of Quantifier Prefixes Over Exponential Diophantine Equations
- Computational complexities of diophantine equations with parameters
- Further results on Hilbert's tenth problem
- Questions of decidability and undecidability in Number Theory
This page was built for publication: Note on Quantifier Prefixes Over Diophantine Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3707986)