Characterizing Z in Q with a universal-existential formula

12 June 2008
Bjorn Poonen
Refining Julia Robinson's 1949 work on the undecidability of the first order theory of Q, we prove that Z is definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points.