Note on Quantifier Prefixes Over Diophantine Equations (Q3707986)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3933027
Language Label Description Also known as
default for all languages
No label defined
    English
    Note on Quantifier Prefixes Over Diophantine Equations
    scientific article; zbMATH DE number 3933027

      Statements

      Note on Quantifier Prefixes Over Diophantine Equations (English)
      0 references
      0 references
      1986
      0 references
      Hilbert irreducibility
      0 references
      residue classes
      0 references
      density
      0 references
      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).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references