Editing Diophantine set (section)

{{Short description|Solution of some Diophantine equation}}
In [[mathematics]], a [[Diophantine equation]] is an equation of the form ''P''(''x''<sub>1</sub>, ..., ''x''<sub>''j''</sub>, ''y''<sub>1</sub>, ..., ''y''<sub>''k''</sub>) = 0 (usually abbreviated ''P''(''{{overline|x}}'', ''{{overline|y}}'') = 0) where ''P''(''{{overline|x}}'', ''{{overline|y}}'') is a [[polynomial]] with integer [[coefficient]]s, where ''x''<sub>1</sub>, ..., ''x''<sub>''j''</sub> indicate parameters and ''y''<sub>1</sub>, ..., ''y''<sub>''k''</sub>  indicate unknowns.

A '''Diophantine set''' is a [[set (mathematics)|subset]] ''S'' of <math>\mathbb{N}^j</math>, the set of all ''j''-tuples of natural numbers, so that for some [[Diophantine equation]] ''P''(''{{overline|x}}'', ''{{overline|y}}'') = 0,

:<math>\bar{x} \in S \iff (\exists \bar{y} \in \mathbb{N}^{k})(P(\bar{x},\bar{y})=0) .</math>

That is, a parameter value is in the Diophantine set ''S'' [[if and only if]] the associated Diophantine equation is [[Satisfiability|satisfiable]] under that parameter value. The use of natural numbers both in ''S'' and the existential quantification merely reflects the usual applications in [[computability theory]] and [[model theory]]. It does not matter whether natural numbers refer to the set of nonnegative integers or positive integers since the two definitions for Diophantine sets are equivalent. We can also equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers.<ref>{{cite web |title=Diophantine set |url=http://encyclopediaofmath.org/index.php?title=Diophantine_set&oldid=46710 |website=[[Encyclopedia of Mathematics]] |access-date=11 March 2022}}</ref> Also it is sufficient to assume ''P'' is a polynomial over <math>\mathbb{Q}</math> and multiply ''P'' by the appropriate denominators to yield integer coefficients.  However, whether quantification over rationals can also be substituted for quantification over the integers is a notoriously hard open problem.<ref>{{cite book
 | last1 = Pheidas | first1 = Thanases
 | last2 = Zahidi | first2 = Karim
 | contribution = Decision problems in algebra and analogues of Hilbert's tenth problem
 | contribution-url = https://scholar.archive.org/work/u2qccxcwindxlmlm4dh7syojlq
 | doi = 10.1017/CBO9780511735219.007
 | isbn = 978-0-521-70908-8
 | mr = 2436143
 | pages = 207–235
 | publisher = Cambridge University Press
 | series = London Mathematical Society Lecture Note Series
 | title = Model theory with applications to algebra and analysis. Vol. 2
 | volume = 350
 | year = 2008}}</ref>

[[Hilbert's tenth problem|The MRDP theorem]] (so named for the initials of the four principal contributors to its solution) states that a set of integers is Diophantine if and only if it is [[recursively enumerable set|computably enumerable]].<ref>The theorem was established in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem. However, the proof given by Matiyasevich relied extensively on previous work on the problem and the mathematical community has moved to calling the equivalence result the MRDP theorem or the Matiyasevich–Robinson–Davis–Putnam theorem, a name that credits all the mathematicians that made significant contributions to this theorem.</ref> A set of integers ''S'' is computably enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of ''S'' and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to [[number theory]], can be taken rather in [[mathematical logic|logical]] or computability-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work.

Matiyasevich's completion of the MRDP theorem settled [[Hilbert's tenth problem]]. [[David Hilbert|Hilbert's]] tenth problem<ref>[[David Hilbert]] posed the problem in his celebrated list, from his 1900 address to the [[International Congress of Mathematicians]].</ref> was to find a general [[algorithm]] that can decide whether a given Diophantine equation has a solution among the integers.  While Hilbert's tenth problem is not a formal mathematical statement as such, the nearly universal acceptance of the (philosophical) identification of a decision [[algorithm]] with a [[recursive set|total computable predicate]] allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.