Diophantine set

A Diophantine set is a subset S of ${\displaystyle {\mathbb{N}}^j}$, the set of all j-tuples of natural numbers, so that for some Diophantine equation P(x, y) = 0,

${\displaystyle \overline{x}\in S⟺(\mathrm{\exists }\overline{y}\in {\mathbb{N}}^k)(P(\overline{x},\overline{y})=0).}$

That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is 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. Also it is sufficient to assume P is a polynomial over ${\displaystyle \mathbb{Q}}$ 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.

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 computably enumerable. 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 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. Hilbert's tenth problem 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 total computable predicate allows us to use the MRDP theorem to conclude that the tenth problem is unsolvable.

Examples

In the following examples, the natural numbers refer to the set of positive integers.

The equation

${\displaystyle x=(y_1+1)(y_2+1)}$

is an example of a Diophantine equation with a parameter x and unknowns y₁ and y₂. The equation has a solution in y₁ and y₂ precisely when x can be expressed as a product of two integers greater than 1, in other words x is a composite number. Namely, this equation provides a Diophantine definition of the set

{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, ...}

consisting of the composite numbers.

Other examples of Diophantine definitions are as follows:

• The equation ${\displaystyle x=y_1^2+y_2^2}$ with parameter x and unknowns y₁, y₂ only has solutions in ${\displaystyle \mathbb{N}}$ when x is a sum of two perfect squares. The Diophantine set of the equation is {2, 5, 8, 10, 13, 17, 18, 20, 25, 26, ...}.
• The equation ${\displaystyle y_1^2-x{y}_2^2=1}$ with parameter x and unknowns y₁, y₂. This is a Pell equation, meaning it only has solutions in ${\displaystyle \mathbb{N}}$ when x is not a perfect square. The Diophantine set is {2, 3, 5, 6, 7, 8, 10, 11, 12, 13, ...}.
• The equation ${\displaystyle x_1+y=x_2}$ is a Diophantine equation with two parameters x₁, x₂ and an unknown y, which defines the set of pairs (x₁, x₂) such that x₁ < x₂.