# 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,*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, 4*x*^{3} + 3*xy*^{2} - 7*x* + 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*^{3} + *bxy*^{2} - *x* + *d* = 0 is a general form of an equation, and 4*x*^{3} + 3*xy*^{2} - 7*x* + 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 *a*_{1}, *a*_{2}, *a*_{3} … 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

*a*

_{1}

*x*

^{3}+

*a*

_{2}

*xy*

^{2}-

*a*

_{3}

*x*+

*a*

_{4}= 0 we could equally well use the equivalent

*a*

_{3}

*x*

^{3}+

*a*

_{4}

*xy*

^{2}-

*a*

_{2}

*x*+

*a*

_{1}= 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:

*a*

_{1}, … ,

*a*⟩ (3.2.1)

_{n}Let

*b*

_{1}, … ,

*b*(3.2.2)

_{n}be any pairwise co-prime numbers such that:

*a*<

_{i}*b*,

_{i}*i*= 1, …,

*n*(3.2.3)

By the Chinese Remainder Theorem, we can find a number *a* such that:

*a*= rem(

_{i}*a*,

*b*),

_{i}*i*= 1, …,

*n*(3.2.4)

Thus all the elements of tuple (3.2.1) are uniquely determined by the numbers:

*a*,

*b*

_{1}, … ,

*b*(3.2.5)

_{n}

He continues:

… 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

*b*=

_{i}*bi*+ 1,

*i*= 1, …,

*n*(3.2.6)

A little further on he says:

… we call the triple (*a, b, c*) a Gödel code of tuple ⟨*a*_{1}, … , *a _{n}*⟩ if

*c = n*, and for

*i*= 1, … ,

*n*,

*a*= GElem(

_{i}*a, b, i*) (3.2.14)

where GElem is the Diophantine function such that:

*a*= GElem(

_{i}*a, b, i*) ↔

*a*= GElem(

_{i}*a, bi*+ 1) (3.2.15)

In 3.2.1 to 3.2.6 the terms *a*_{1}, … , *a _{n}* are introduced without any specific reference to Diophantine equations or their coefficients; the terms

*a*

_{1}, … ,

*a*simply represent

_{n}*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:

*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 with 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? We can consider that it cannot be a constant since when

*i*changes

*b*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

_{i}*variables. It is only when the subscript*

**not***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

*b*is not a term of a well-formed consistent mathematical system.

_{i}

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 *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*_{3} = 3*b* + 1

where *b*_{3} and *b* are both variables of the system. As already noted, any parameter such as *b*_{3} may be assigned * any* name, and any variable such as

*b*may also be assigned

*name. Matiyasevich’s assumption of some sort of innate correlation of*

**any***b*

_{3}and

*b*is logically absurd.

It follows that the term *b _{i}* is a term of a

*to the mathematical system to which terms such as*

**meta-language***b*

_{3}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*_{1} *x*^{3} + *a*_{2} *xy*^{2} - *a*_{3} *x* + *a*_{4} = 0 and *a*_{4} *xy*^{2} + *a*_{3} *x*^{3} + *a*_{1} - *a*_{2} *x* = 0 and - *a*_{5} *x* + *a*_{2} + *a*_{8} *x*^{3} + *a*_{7} *xy*^{2} = 0 and *a*_{9} - *a*_{7} *x* + *a*_{3} *x*^{3} + *a*_{4} *y*^{2}*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*_{1}, … , *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.

Footnotes:

Rationale: Every logical argument must be defined in some language, and every language has limitations. Attempting to construct a logical argument while ignoring how the limitations of language might affect that argument is a bizarre approach. The correct acknowledgment of the interactions of logic and language explains almost all of the paradoxes, and resolves almost all of the contradictions, conundrums, and contentious issues in modern philosophy and mathematics.Site MissionPlease see the menu for numerous articles of interest. Please leave a comment or send an email if you are interested in the material on this site.

Interested in supporting this site?You can help by sharing the site with others. You can also donate at

_{}where there are full details.