Logic and
Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2024 https://www.jamesrmeyer.com

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
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, 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.
Yuri Matiyasevich
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 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 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 a1x3 + a2xy2 - a3x + a4 = 0 we could equally well use the equivalent a3x3 + a4xy2 - a2x + 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/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:

Consider an arbitrary tuple:

a1, … , an   (3.2.1)

Let

b1, … , bn   (3.2.2)

be any pairwise co-prime numbers such that:

ai < bi ,   i = 1, …, n   (3.2.3)

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

ai = rem(a, bi ),   i = 1, …, n   (3.2.4)

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

a, b1, … , bn   (3.2.5)

 

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

bi = 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  ⟨a1, … , an if c = n, and for i = 1, … , n,

ai = GElem(a, b, i)   (3.2.14)

 

where GElem is the Diophantine function such that:

ai = GElem(a, b, i) ↔ ai = GElem(a, bi + 1)   (3.2.15)

 

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 mathematical system in question - a system which includes Diophantine equations and which is to be consistent.

 

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, and which have 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 of the mathematical system (the system of Diophantine equations)? 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 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 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 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 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.

 

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 b3 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 bi rather than fn(x) then there is 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.

 

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 a1x3 + a2xy2 - a3x + a4 = 0 and a4xy2 + a3x3 + a1 - a2x = 0 and - a5x + a2 + a8x3 + a7xy2 = 0 and a9 - a7x + a3x3 + a4y2x = 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.

 

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?

You can help by sharing the site with others. You can also donate at Go Get Funding: Logic and Language 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 user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly 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.

 

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2024
https://www.jamesrmeyer.com