4
$\begingroup$

In the Wikipedia article Diophantine set there is a section entitled "Further applications" in regards to Matiyasevich's theorem and it states:

Matiyasevich's theorem has since been used to prove that many problems from calculus and differential equations are unsolvable.

One can also derive the following stronger form of Gödel's first incompleteness theorem from Matiyasevich's result:

and then states the theorem. However, this section contains no specific citations. Could somebody provide me with references of this proof worthy of citation? Specifically, I mean the proof regarding the first incompleteness theorem. Granted, it is easy to see how Matiyasevich's theorem can prove Gödel's first incompleteness theorem, but I am looking for (possible the first) published paper with this result to be able to reference it.

$\endgroup$
10
$\begingroup$

If you are writing a research paper on this, the usual practice in mathematics is that you do not need a reference for such an obvious result which is known to everyone in the field already. For things like this, there is often no paper that claims credit for the result - one of the roles of books is to summarize these "well known" results that nobody would take credit for in a paper.

I suspect that the result was "first known" even before Matiyasevich proved the final part of the MDRP theorem, in the sense that everyone realized that a negative answer to Hilbert's 10th problem would lead immediately to this kind of result.

However, Martin Davis does mention this result as Theorem 7.7 of ''Hilbert's 10th problem is unsolvable'', The American Mathematical Monthly, 80(3), 1973, pp. 233-269. He provides what he calls an "informal heuristic" argument, which is the standard argument sketched by Carlo Beenakker in another answer here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fair enough, thank you for the answer $\endgroup$ – Not_Here Apr 18 '17 at 19:30
11
$\begingroup$

The reference to Matiyasevich is

Matiyasevich, Y., 1970, “Diofantovost’ perechislimykh mnozhestv,” Dokl. Akad. Nauk SSSR, 191(2): 297–282 (Russian). (English translation, 1970, “Enumerable sets are Diophantine,” Soviet Math. Dokl., 11(2): 354–358.)

This is Matiyasevich's solution to Hilbert's 10th problem. How it can be used to obtain a proof to Gödel's first incompleteness theorem is explained by Torkel Franzén (Gödel's Theorem: An incomplete guide to its use and abuse, 2005, page 73).

Matiyasevich proved that there is no algorithm that, given a multivariate polynomial $p(x_1, x_2,...,x_k)$ with integer coefficients, determines whether there is an integer solution to the equation $p = 0$. Because polynomials with integer coefficients, and integers themselves, are directly expressible in the language of arithmetic, if a multivariate integer polynomial equation $p = 0$ does have a solution in the integers then any sufficiently strong system of arithmetic $T$ will prove this. Moreover, if the system $T$ is ω-consistent, then it will never prove that a particular polynomial equation has a solution when in fact there is no solution in the integers. Thus, if $T$ were complete and ω-consistent, it would be possible to determine algorithmically whether a polynomial equation has a solution by merely enumerating proofs of $T$ until either "$p$ has a solution" or "$p$ has no solution" is found, in contradiction to Matiyasevich's theorem.

source

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm aware of what Matiyasevich's theorem is and how it can be used to prove the first incompleteness theorem. Franzen's book is a great overview of Gödel's results but what I am meaning to ask for is any paper that proves this result, not a book for non specialists. I'm writing a paper and I need a reference, I guess in particular it would be nice to know when this result was first shown. $\endgroup$ – Not_Here Apr 18 '17 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.