Concluding Comments by Martin

Martin Davis

Abstract After a very brief comment on Yuri Matiyasevich’s contribution, I discuss at greater length proposals to use modal logic to clarify foundational issues in set theory. Finally, I very sadly bid farewell to my friend and collaborator Hilary Putnam.

Comments on Yuri Matiyasevich’s Essay

First I want to express my thanks to my good friend Yuri for his generous account of my contributions to the solution of Hilbert’s Tenth Problem. The theorem that every listable set is Diophantine that, as Yuri explains, I had conjectured in my doctoral dissertation, is often referred to as Matiyasevich’s Theorem because he supplied the crucial final step. He kindly suggests calling it DPRM to emphasize the role each of us played in its eventual proof. It is also sometimes referred to as MRDP.

I would like to comment briefly on a few of the matters he discusses. Although, as Yuri emphasizes, my conjecture was widely disbelieved because of its counterintuitive consequences, I want to mention one argument in its favor that impressed me, perhaps unduly. Namely it was easy to prove (non-constructively) that there is a Diophantine set whose complement is not Diophantine. Namely, because the class of Diophantine subsets of Nn is closed under existential quantification (i.e., projection), if it were also closed under complementation, it would be closed under universal quantification as well. Therefore it would include all arithmetic sets. But this is impossible because all Diophantine sets are listable and there are arithmetic sets that are not listable. Thus I knew that the class of Diophantine sets shares with the class of listable sets the properties of being closed under union, intersection and existential quantification, but not under complementation.

M. Davis (B)

Department of Mathematics, University of California, Berkeley, CA, USA e-mail: This email address is being protected from spam bots, you need Javascript enabled to view it

M. Davis

Courant Institute of Mathematical Sciences, New York University,

New York, NY, USA

© Springer International Publishing Switzerland 2016 357

E.G. Omodeo and A. Policriti (eds.), Martin Davis on Computability,

Computational Logic, and Mathematical Foundations,

Outstanding Contributions to Logic 10, DOI 10.1007/978-3-319-41842-1_15

In connection with the arithmetic representation of listable sets involving only a single bounded universal quantifier (what Raphael Robinson called Davis Normal Form), I’d like to point out that while from one point of view it is a simple reduction of Godel’s representation with several universal quantifiers, given what Hilary Putnam, Julia Robinson, and I knew in 1959, Davis Normal Form was crucial for our proof of the DPR theorem. This was because without assuming JR, the variable exponents introduced by the elimination of the innermost universal quantifier from Godel’s representation, could not be eliminated to permit iterating the process. Of course after Yuri proved JR, this was no longer an issue, and contemporary proofs of DPR no longer need mention Davis Normal Form.

Yuri mentions his own crucial contribution in a single modest sentence. His wonderful proof of JR, showing that the relation between a number n and the 2nth Fibonacci number is Diophantine by an explicit construction, accomplished something that we others had been trying unsuccessfully to do for twenty years.

Although Yuri mentions my recent conjecture in connection with Bjorn Poonen’s work on rings of rational numbers, referring to me as a “guru”, I am not very optimistic about the usefulness of that conjecture. However, he does not mention my most successful conjecture of all. During the period when DPR had been proved so that it was known that the truth of my conjecture and thus the unsolvability of Hilbert’s Tenth Problem would follow if JR were proved, I gave a number of talks in which I emphasized the consequences of either the truth or the falsity of JR, noting that, in either case, some of those consequences were rather implausible. Asked during the question period for my own opinion as to the truth of JR, I would reply, half in jest: Oh, I think that JR is true and will be proved by a clever young Russian.

Martin Davis, June 13, 2015

< Prev   CONTENTS   Source   Next >