Undecidability in Number Theory

By Jochen Koenigsmann. 2013

59 citations recorded by the source corpus.

In these lecture notes we give sketches of classical undecidability results in number theory, like Godel’s first Incompleteness Theorem (that the first order theory of the integers in the language of rings is undecidable), Julia Robinson’s extensions of this result to arbitrary number fields and rings of integers in them, as well as to the ring of totally real integers, and Matiyasevich’s negative solution of Hilbert’s 10th problem, i.e., the undecidability of the existential first-order theory of the integers. As Hilbert’s 10th problem is still open for the rationals (i.e., the question whether the existential theory of the field of rational numbers is decidable) we also present a sketch of the fact that there is a universal definition of the ring of integers inside the field of rationals. In terms of complexity this is the simplest definition known so far. If one had an existential definition instead then Hilbert’s 10th problem over the rationals would reduce to that over the integers (and hence be, as expected, unsolvable), but, modulo a widely believed in conjecture in number theory, we also indicate why there should be no such existential definition. We conclude with a list of nice open questions in the area.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/7b26cac4956b3b1cb95bb7d3c56631d516621c54