Note on Quantifier Prefixes Over Diophantine Equations

From MaRDI portal





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











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)