Matiyasevich's theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilbert's tenth problem is unsolvable. This problem is the challenge to find a general algorithm which can decide whether a given system of Diophantine equations (polynomials with integer coefficients) has a solution among the integers. David Hilbert posed the problem in his 1900 address to the International Congress of Mathematicians.
A typical system of diophantine equations looks like this:
- 3x2y − 7y2z3 = 18
- − 7y2 + 8z2 = 0
- ( 3(x1 − x2)2(y1 − y2) − 7(y1 − y2)2(z1 − z2)3 − 18 )2 + ( −7(y1 − y2)2 + 8(z1 − z2)2)2 = 0.
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 (Zhi Wei Sun, 1992).
Matiyasevich's theorem itself is somewhat more general than the unsolvability of the Tenth Problem. It says:
- Every recursively enumerable set is Diophantine.
(It is amusing to observe that one of the very few places in modern mathematics where an argument that takes exactly the form of an old-fashioned Aristotelian syllogism is of great interest and is not contemptuously dismissed as uninteresting because trivial. That argument is as follows.
- (Major premise): All recursively enumerable sets are Diophantine.
- (Minor premise): Some recursively enumerable sets are non-recursive.
- (Conclusion): Therefore some Diophantine sets are non-recursive.
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 incompleteness theorem from Matiyasevich's result:
- Corresponding to any given axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.
References
- Y. Matiyasevich. "Enumerable sets are Diophantine." Doklady Akademii Nauk SSSR, 191, pp. 279-282, 1970. English translation in Soviet Mathematics. Doklady, vol. 11, no. 2, 1970.
- M. Davis. "Hilbert's Tenth Problem is Unsolvable." American Mathematical Monthly 80, pp. 233-269, 1973.