Editing Hilbert's tenth problem (section)

==Applications==
The Matiyasevich/MRDP theorem relates two notions&mdash;one from computability theory, the other from number theory&mdash;and has some surprising consequences. Perhaps the most surprising is the existence of a ''universal'' Diophantine equation:

:''There exists a polynomial'' <math>p(a,n,x_1,\ldots,x_k)</math> ''such that, given any Diophantine set'' <math>S</math> ''there is a number'' <math>n_0</math> ''such that''
::<math display=block> S = \{\,a \mid \exists x_1, \ldots, x_k \, [p(a,n_0,x_1,\ldots,x_k)=0]\,\}.</math>

This is true simply because Diophantine sets, being equal to recursively enumerable sets, are also equal to [[Turing machine]]s. It is a well known property of Turing machines that there exist universal Turing machines, capable of executing any algorithm.

Hilary Putnam has pointed out that for any Diophantine set <math>S</math> of positive integers, there is a polynomial

:<math>q(x_0,x_1,\ldots,x_n)</math>

such that <math>S</math> consists of exactly the positive numbers among the values assumed by <math>q</math> as
the variables

:<math>x_0,x_1,\ldots,x_n</math>

range over all natural numbers. This can be seen as follows: If

:<math>p(a,y_1,\ldots,y_n)=0</math>

provides a Diophantine definition of <math>S</math>, then it suffices to set

:<math display=block>q(x_0,x_1,\ldots,x_n)= x_0[1- p(x_0,x_1,\ldots,x_n)^2].</math>

So, for example, there is a polynomial for which the positive part of its range is exactly the prime numbers. (On the other hand, no polynomial can only take on prime values.) The same holds for other recursively enumerable sets of natural numbers: the factorial, the binomial coefficients, the fibonacci numbers, etc.

Other applications concern what logicians refer to as <math>\Pi^{0}_1</math> propositions, sometimes also called propositions of ''Goldbach type''.{{efn|<math>\Pi^{0}_1</math> sentences are at one of the lowest levels of the so-called [[arithmetical hierarchy]].}} These are like [[Goldbach's conjecture]], in stating that all natural numbers possess a certain property that is algorithmically checkable for each particular number.{{efn|Thus, the Goldbach Conjecture itself can be expressed as saying that for each natural number <math>n</math> the number <math>2n+4</math> is the sum of two prime numbers. Of course there is a simple algorithm to test a given number for being the sum of two primes.}} The Matiyasevich/MRDP theorem implies that each such proposition is equivalent to a statement that asserts that some particular Diophantine equation has no solutions in natural numbers.{{efn|In fact the equivalence is provable in [[Peano arithmetic]].}} A number of important and celebrated problems are of this form: in particular, [[Fermat's Last Theorem]], the [[Riemann hypothesis]], and the [[four color theorem]]. In addition the assertion that particular [[formal system]]s such as Peano arithmetic or [[ZFC]] are consistent can be expressed as <math>\Pi^{0}_1</math> sentences. The idea is to follow [[Kurt Gödel]] in coding proofs by natural numbers in such a way that the property of being the number representing a proof is algorithmically checkable.

<math>\Pi^{0}_1</math> sentences have the special property that if they are false, that fact will be provable in any of the usual formal systems. This is because the falsity amounts to the existence of a counter-example that can be verified by simple arithmetic. So if a <math>\Pi^{0}_1</math> sentence is such that neither it nor its negation is provable in one of these systems, that sentence must be true.{{citation needed|date=September 2015}}

A particularly striking form of [[Gödel's incompleteness theorem]] is also a consequence of the Matiyasevich/MRDP theorem:

<blockquote>Let

:<math>p(a,x_1,\ldots,x_k)=0</math>

provide a Diophantine definition of a non-computable set. Let <math>A</math> be an algorithm that outputs a sequence of natural numbers <math>n</math> such that the corresponding equation

:<math>p(n,x_1,\ldots,x_k)=0</math>

has no solutions in natural numbers. Then there is a number <math>n_0</math> that is not output by <math>A</math> while in fact the equation

:<math>p(n_0,x_1,\ldots,x_k)=0</math>

has no solutions in natural numbers.</blockquote>

To see that the theorem is true, it suffices to notice that if there were no such number <math>n_0</math>, one could algorithmically test membership of a number <math>n</math> in this non-computable set by simultaneously running the algorithm <math>A</math> to see whether <math>n</math> is output while also checking all possible <math>k</math>-tuples of natural numbers seeking a solution of the equation

:<math>p(n,x_1,\ldots,x_k)=0</math>

and we may associate an algorithm <math>A</math> with any of the usual formal systems such as [[Peano arithmetic]] or [[ZFC]] by letting it systematically generate consequences of the axioms and then output a number <math>n</math> whenever a sentence of the form

:<math>\neg \exists x_1,\ldots , x_k \, [p(n,x_1,\ldots,x_k)=0]</math>

is generated. Then the theorem tells us that either a false statement of this form is proved or a true one remains unproved in the system in question.