Extensions of Hilbert’s Tenth Problem: Definability and Decidability in Number Theory
Abstract This chapter surveys some of the developments in the area of Mathematics that grew out of the solution of Hilbert’s Tenth Problem by Martin Davis, Hilary Putnam, Julia Robinson and Yuri Matiyasevich.
Keywords Hilbert’s tenth problem • Diophantine definability • Existential definability • Recursively enumerable sets
The End of the Beginning
When Yu. Matiyasevich completed the proof started by Martin Davis, Hilary Putnam and Julia Robinson, showing that all recursively enumerable sets of integers are Diophantine (see [4, 5, 22]), he added the last stone to the foundation of a new field which evolved from the solution of Hilbert’s Tenth Problem. This new field intersecting Recursion Theory, Model Theory, Number Theory, Algebraic Geometry and lately parts of Analysis has sought to understand the expressive power of various dialects of the language of rings in different settings and to determine when the truth-values of sentences in these dialects can be decided algorithmically. Below we survey some of the recent developments in this field over finite and infinite algebraic extensions of Q.
The question posed by Hilbert about rational integers can of course be asked about any recursive ring R (i.e. a ring where we know what the elements are and how to perform algorithmically the ring operations): is there an algorithm, which if given an arbitrary polynomial equation in several variables with coefficients in R, can determine whether this equation has solutions in R? Arguably, the most prominent
The author has been partially supported by the NSF grant DMS-1161456.
A. Shlapentokh (B)
© Springer International Publishing Switzerland 2016 55
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_3
open questions in the area are the questions of decidability of an analog of Hilbert’s Tenth Problem for R = Q and R equal to the ring of integers of an arbitrary number field. These questions proved to be quite hard and generated many other questions and mathematical developments. Almost simultaneously, the subject expanded to include infinite algebraic extensions of Q, as well as function fields. In this paper we describe some of the more recent developments in the area dealing with algebraic extensions of Q. We start our survey with a discussion of Hilbert’s Tenth Problem for the field of rational numbers, but before we get there we need to consider a central notion occurring again and again in the discussion below: the notion of a Diophantine set.