Diophantine set

In the following examples, the natural numbers refer to the set of positive integers. The equation :x = (y_1 + 1)(y_2 + 1) is an example of a Diophantine equation with a parameter x and unknowns y1 and y2. The equation has a solution in y1 and y2 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 x = y_1^2 + y_2^2 with parameter x and unknowns y1, y2 only has solutions in \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 y_1^2 - xy_2^2 = 1 with parameter x and unknowns y1, y2. This is a Pell equation, meaning it only has solutions in \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 x_1 + y = x_2 is a Diophantine equation with two parameters x1, x2 and an unknown y, which defines the set of pairs (x1, x2) such that x1 2. ==Matiyasevich's theorem==

Matiyasevich's theorem, also called the Matiyasevich–Robinson–Davis–Putnam or MRDP theorem, says: :Every computably enumerable set is Diophantine, and the converse. A set S of integers is computably enumerable if there is an algorithm such that: For each integer input n, if n is a member of S, then the algorithm eventually halts; otherwise it runs forever. That is equivalent to saying there is an algorithm that runs forever and lists the members of S. A set S of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n, x1, ..., xk) such that an integer n is in S if and only if there exist some integers x1, ..., xk with f(n, x1, ..., xk) = 0. It is easy to see that every Diophantine set is computably enumerable: consider a Diophantine equation f(n, x1, ..., xk) = 0. Now we make an algorithm that tries all possible values for n, x1, ..., xk (in, say, some simple order consistent with the increasing order of the sum of their absolute values), and prints n every time f(n, x1, ..., xk) = 0. This algorithm will run forever and will list exactly the n for which f(n, x1, ..., xk) = 0 has a solution in x1, ..., xk. Yuri Matiyasevich utilized a method involving Fibonacci numbers, which grow exponentially, in order to show that solutions to Diophantine equations may grow exponentially. Earlier work by Julia Robinson, Martin Davis and Hilary Putnam – hence, MRDP – had shown that this suffices to show that every computably enumerable set is Diophantine. ==Application to Hilbert's tenth problem==

Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's result with the fact that most recursively enumerable languages are not decidable implies that a solution to Hilbert's tenth problem is impossible. Refinements Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Sun Zhiwei, 1992). ==Further applications==

Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable. One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result: :Corresponding to any given consistent axiomatization of number theory, one can explicitly construct a Diophantine equation that has no solutions, but such that this fact cannot be proved within the given axiomatization. According to the incompleteness theorems, a powerful-enough consistent axiomatic theory is incomplete, meaning the truth of some of its propositions cannot be established within its formalism. The statement above says that this incompleteness must include the solvability of a diophantine equation, assuming that the theory in question is a number theory. == Notes ==