Note: Full functionality of this website requires JavaScript to be enabled in your browser.

Show Site MissionHide Site Mission

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

- To rid the fields of philosophy and mathematics of arcane and irrational notions which have resulted in numerous contradictions.
- To promulgate the understanding that the validity of a logical argument is not necessarily independent of the way in which language is used by that argument.
- To ensure that future generations of young people will not be put off the study of mathematics and philosophy by the mystical and illogical notions that are currently widespread in those subjects.

# Hilbert’s tenth problem

Page last updated 08 Nov 2022

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, 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, 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. 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 The MRDP Theorem by 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/parameters of the mathematical system to which those variables belong.

### Variable names in the MRDP proof

In the Section 3.2 *Godel 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 Godel 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

While 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, but 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. For example, when the subscript

_{i}*i*is substituted by

*k*, where

*k*is a

*non-variable*term, we get a term such as

*b*which is a valid term of the system, representing a variable of the system. It follows that the term

_{k}*b*is a term of a

_{i}*to the mathematical system to which terms such as*

**meta-language***b*belong, and not of that mathematical system itself.

_{k}

Hence we can see that by the assumption of *b _{i}* =

*bi*+ 1 that while Matiyasevich uses

*i*as a variable of the mathematical system on the right side, on the left side he is using

*i*as a meta-language variable. This is an illogical confusion of language which affects the entire thread of Matiyasevich’s subsequent argument 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*_{3} *x*^{3} + *a*_{4} *xy*^{2} - *a*_{2} *x* + *a*_{1} = 0 and *a*_{2} *xy*^{2} - *a*_{3} *x* + *a*_{1} *x*^{3} + *a*_{7} *xy*^{2} = 0 and *a*_{9} - *a*_{2} *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:

**Interested in supporting this site?**

Share the site with others. You can donate at _{} where there are full details.

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:

Frivolous, irrelevant comments.

Comments devoid of logical basis.

Derogatory comments.

Long-winded comments.

Comments with excessive number of different points.

Questions about matters that do not relate to the page they post on. Such posts are not comments.

Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.

Reasons for deleting comments of certain users:

Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.

Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.

Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.

Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

**This is the comment section for the above article, the comment section for the site in general is below**

**This is the comment section for this site in general**