Hilbert’s tenth problem

Page last updated 25 Jun 2024

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,

David Hilbert

there can be a finite process which can definitively tell whether there is a solution to the equation when the unknown variables take only integer values. (Footnote: In Hilbert’s words: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.)

A Diophantine equation is a polynomial equation with integer coefficients and a finite number of unknown variables, for example, 4x³ + 3xy² - 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 ax³ + bxy² - x + d = 0 is a general form of an equation, and 4x³ + 3xy² - 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.

Yuri Matiyasevich

The argument of the proof has also been used as the basis for proofs of incompleteness. (Footnote: See for example:
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 a₁, a₂, a₃ … 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 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 a₁ x³ + a₂ xy² - a₃ x + a₄ = 0 we could equally well use the equivalent a₃ x³ + a₄ xy² - a₂ x + a₁ = 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/parameters of the mathematical system to which those variables belong.

Variable names in the MRDP proof

In the Section 3.2 Gödel coding, Matiyasevich states:

He continues:

A little further on he says:

In 3.2.1 to 3.2.6 the terms a₁, … , a_n are introduced without any specific reference to Diophantine equations or their coefficients; the terms a₁, … , a_n 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 mathematical system in question - a system which includes Diophantine equations and which is to be consistent.

However, consider Matiyasevich’s claim that:

b_i = 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, and which have the domain of natural numbers.

On the other hand, what about the term b_i on the left side? Is it a constant or a variable of the mathematical system (the system of Diophantine equations)? We can consider that it cannot be a constant since when i changes b_i also changes. Hence we might consider that it must be a variable of the mathematical system. But if it is a variable of the mathematical system, its domain must be a set of entities that are not variables of that mathematical system. But when the subscript i is substituted by some specific value, we generate a term that is an entity of the mathematical system - a variable of the mathematical system - which demonstrates that the term b_i 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 of the mathematical system in question. That is, when the subscript i is substituted by k, where k is a non-variable term, we get a term such as b_k 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:

b₃ = 3b + 1

where b₃ and b are both variables of the system.

But a function and its variables can have any name, for example we could call it fn(x). And as already noted, any parameter such as b₃ may be assigned any name, and any variable such as b may also be assigned any name. Matiyasevich’s assumption that if one calls the function b_i rather than fn(x) then there is some sort of innate correlation of b₃ and b is logically absurd.

It follows that the term b_i is a term of a meta-language to the mathematical system to which terms such as b₃ 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.

Self-reference

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 a₁ x³ + a₂ xy² - a₃ x + a₄ = 0 and a₄ xy² + a₃ x³ + a₁ - a₂ x = 0 and - a₅ x + a₂ + a₈ x³ + a₇ xy² = 0 and a₉ - a₇ x + a₃ x³ + a₄ y²x = 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(x₁, … , x_n) = 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.

Conclusions

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.