Hilbert’s tenth problem
Page last updated 16 Feb 2023
in 1900 the mathematician David Hilbert posed twenty-three problems that were at that time all unanswered. His tenth problem was the question as to whether, given any Diophantine equation,
A Diophantine equation is a polynomial equation with integer coefficients and a finite number of unknown variables, for example, 4x3 + 3xy2 - 7x + 5 = 0. The numbers 4, 3, 7 and 5 are the coefficients of the equation, and a group of Diophantine equations can be referenced by the use of terms that are called parameters, so that the equation ax3 + bxy2 - x + d = 0 is a general form of an equation, and 4x3 + 3xy2 - 7x + 5 = 0 is just one instance of the set of all such equations.
In 1970 Yuri Matiyasevich claimed to have completed a proof that proved Hilbert’s question in the negative, that is there can be no finite method which can deduce, for any given Diophantine equation, whether there is a solution of the equation where all the variables take only integer values. Matiyasevich’s work utilized previous results by others, and for this reason it is commonly referred to as the MRDP theorem, named after Yuri Matiyasevich, Julia Robinson, Martin Davis and Hilary Putnam.
Torkel Franzen. Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. A K Peters, 2005. ISBN: 1568812388, and
an online article PDF The MRDP Theorem by the convicted paedophile ex-professor Peter Smith claiming that the MRDP “theorem” can be used to prove incompleteness.) There is an English translation of the full text of Matiyasevich’s proof in the book Hilbert’s Tenth Problem. (Footnote: Yuri Matiyasevich, Hilbert’s Tenth Problem , MIT press, 1993, ISBN 0-262-13295-8.) In the following we will analyze the proof presented in that book.
Naming of variables
Conventionally, while it is common to see names such as a1, a2, a3 … used for the coefficients of a Diophantine equation, it must be stressed that this is only for convenience when referencing the equation, and in general, within any given mathematical system, there is no particular significance to the names used for variables and any names can be used can be used provided they do not conflict with any other variable or constant names within the system. For example, one could simply use the names a, b, c, d, … aa, bb, cc, dd, … , and so on. If one wishes to distinguish variables by subscripts there is no reason within the system that compels the subscripts to follow in sequence in an initial equation. For example instead of a1 x3 + a2 xy2 - a3 x + a4 = 0 we could equally well use the equivalent a3 x3 + a4 xy2 - a2 x + a1 = 0 without having any effect on manipulations within the given mathematical system. However, from outside the system, it is usually more convenient to use the former set of names simply to make it easier to follow the manipulations within the system.
Furthermore, if numerical subscripts are desired, there is no logical reason that requires the subscripts of the variables and parameters to be in the same numerical format as the format of the numbers that form the domain of natural numbers for the variables/
Variable names in the MRDP proof
In the Section 3.2 Gödel coding, Matiyasevich states:
Consider an arbitrary tuple:
be any pairwise co-prime numbers such that:
By the Chinese Remainder Theorem, we can find a number a such that:
Thus all the elements of tuple (3.2.1) are uniquely determined by the numbers:
… we have great freedom in choosing the numbers (3.2.2), and we can choose them to be determined by just a few numbers. For example, put
A little further on he says:
… we call the triple (a, b, c) a Gödel code of tuple ⟨a1, … , an⟩ if c = n, and for i = 1, … , n,
where GElem is the Diophantine function such that:
In 3.2.1 to 3.2.6 the terms a1, … , an are introduced without any specific reference to Diophantine equations or their coefficients; the terms a1, … , an simply represent n different variables. As noted previously, there is no restriction on the names that may be used other that they do not conflict with other names.
Since it is the case that there is no inherent naming method for the variables, then if one intends to use a single symbol (such as a) followed by different subscripts, it is important to ensure that no false correlation is assumed to exist between these subscripts and the entities that constitute the domain of variables of the system in question.
However, consider Matiyasevich’s claim that:
bi = bi + 1
We can assert that by consideration of the right side of the equation, both b and i are variables of the mathematical system with the domain of natural numbers.
On the other hand, what about the term bi on the left side? Is it a constant or a variable? We can consider that it cannot be a constant since when i changes bi also changes. Hence we might consider that it must be a variable. But if it is a variable, its domain must be a set of entities that are not variables. It is only when the subscript i is substituted by some specific value that we generate a term that is an entity of the system - a variable of the system - which demonstrates that the term bi is not a term of a well-formed consistent mathematical system.
One can, however, say of the left side that b is a function with one free variable i, and upon substitution of that free variable by some natural number, the function evaluates as a specific variable. That is, when the subscript i is substituted by k, where k is a non-variable term, we get a term such as bk which is a valid term of the system, representing a variable of the system. For example, when we substitute the i by 3, by Matiyasevich’s equation (3.2.6) we have that:
b3 = 3b + 1
where b3 and b are both variables of the system. As already noted, any parameter such as b3 may be assigned any name, and any variable such as b may also be assigned any name. Matiyasevich’s assumption of some sort of innate correlation of b3 and b is logically absurd.
It follows that the term bi is a term of a meta-language to the mathematical system to which terms such as b3 belong, and not of that mathematical system itself. Matiyasevich’s use of i as a variable of the mathematical system on the right side, and as a meta-language term on the left side is an illogical confusion of language which affects the entire thread of Matiyasevich’s subsequent argument, and which is based upon this erroneous equivalence.
That erroneous equivalence is used to make the mathematical system appear to self-reference, to be able to refer to such matters as the length of formulas of the system and to positions of its coefficients, etc, by its very own formulas, which makes it appear that the system can somehow infer certain information about its own formulas, even though its own axioms and rules of inference are completely agnostic regarding such information. (Footnote: For example, the equations a1 x3 + a2 xy2 - a3 x + a4 = 0 and a4 xy2 + a3 x3 + a1 - a2 x = 0 and - a5 x + a2 + a8 x3 + a7 xy2 = 0 and a9 - a7 x + a3 x3 + a4 y2x = 0 are all equivalent within a given mathematical system, while from outside of the system, they can be considered to be different in their formatting, but not with regard to their evaluation.) That is why claims such as Matiyasevich’s must be analyzed with the utmost care and attention.
As already pointed out, if one wants to use numerical subscripts, then a simple way to reduce the possibility of any confusion of levels of language is to use different formats for the subscripts. Matiyasevich uses standard base 10 positional notation for natural numbers that constitute the domain of his variables for natural numbers. This means that there is no logical reason why, for example, a format such as a# , a## , a### , … could not be used, which still enables easy tracking of variables from outside of the system over a series of manipulations of equations, while reducing the possibility of a false correlation between natural numbers within the system and the subscripts.
I have demonstrated in many places elsewhere on this site how a confusion of different levels of language are often the basis of fallacious arguments. Many of these arguments claim to demonstrate that a well-formed logical mathematical system can self-reference itself.
Torkel Franzen and others claim that the MRDP proof leads to a proof of incompleteness without invoking any self-reference, and consider that this aspect of the MRDP “theorem” has tremendous significance. Franzen says: (Footnote: From Torkel Franzen. Gödel’s Theorem: An Incomplete Guide to its Use and Abuse. A K Peters, 2005)
As for the contrasting of the “new viewpoint” with “the old proof based on the paradox of the liar,” … the MRDP theorem shows that every theory to which the incompleteness theorem applies leaves undecided infinitely many statements of the form “the Diophantine equation D(x1, … , xn) = 0 has no solution”. It is indeed important to emphasize that undecidable arithmetical sentences need not be formalizations of odd self-referential statements, but this point is fully illustrated by the undecidability of statements about Diophantine equations.
But, as shown above, a logical analysis demonstrates that self-reference is in fact involved in the MRDP proof and hence such claims are fallacious.
At this point I want to make it quite clear that I am not anywhere asserting that it is impossible that there can be a proof that a formal system having certain properties is incomplete. A claim of a proof of incompleteness that relies on a confusion of levels of language is not a proof, it is only the semblance of a proof, where at some point the proof relies on some form of self-reference (whether explicit or hidden) and which is the result of an illogical confusion of levels of language. This sort of confusion of levels of language cannot occur within a properly formulated logically valid formal language.
It is a mystery why mathematicians and logicians appear unwilling to contemplate the possibility that a confusion of levels of language can result in arguments that have no logical validity, and seem to never consider that they should examine proofs carefully to ascertain whether this might be the case. Of course, once you start pretending that there isn’t an elephant in the room, not only do you not set out to look for it, you actively avoid doing so, instead concentrating your attention anywhere but in that direction.