Hilbert's Tenth Problem - Applications

Applications

The Matiyasevich/MRDP Theorem relates two notions — one from computability theory, the other from number theory — and has some surprising consequences. Perhaps the most surprising is the existence of a universal Diophantine equation:

There exists a polynomial such that, given any Diophantine set there is a number such that

This can be seen to be true simply because there are universal Turing machines, capable of executing any algorithm.

Hilary Putnam has pointed out that for any Diophantine set of positive integers, there is a polynomial

such that consists of exactly the positive numbers among the values assumed by as the variables

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

provides a Diophantine definition of, then it suffices to set

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.)

Other applications concern what logicians refer to as propositions, sometimes also called propositions of Goldbach type. These are like the Goldbach Conjecture, in stating that all natural numbers possess a certain property that is algorithmically checkable for each particular number. 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. 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 systems such as Peano Arithmetic or ZFC are consistent can be expressed as 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.

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 which can be verified by simple arithmetic. So if a sentence is such that neither it nor its negation is provable in one of these systems, that sentence must be true.

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

Let

provide a Diophantine definition of a non-computable set. Let be an algorithm that outputs a sequence of natural numbers such that the corresponding equation

has no solutions in natural numbers. Then there is a number which is not output by while in fact the equation

has no solutions in natural numbers.

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

We may associate an algorithm 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 whenever a sentence of the form

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.