Julia Robinson numbers

Abstract

After the algorithm concept was formalized in the 1930’s, it was possible to prove that the first-order theory of the semi-ring N of the natural numbers is undecidable: There is no algorithm that takes an arithmetic statement as input and gives an answer, after finite stages, whether or not said statement is true in N. On the other hand, in 1931, Tarski [3] proved that the field theory Qalg of all algebraic numbers, as well as the field theory Qalg ∩ R of the real algebraic numbers, is decidable. The problem then is the following: determine which rings between N and Qalg have decidable theory. An important step was taken by Julia Robinson in 1959: In [4], she shows that for any field of numbers K, N is definable in the ring of integers OK of K, and OK is definable in K, thus obtaining a definition of N in K. In particular this shows that the theory of any field of numbers is undecidable, reducing the problem to the case of rings that have their fraction field of infinite degree over Q. On one hand, in 1962 J. Robinson [2] proved that N is definable in the ring of integers OQtr of the Qtr field of all totally real algebraic numbers (whose conjugates are all real numbers), while in 1994 Fried, Haran, and V¨olklein [8] proved that the theory of Qtr is decidable. It is conjectured that every ring of totally real integers has an undecidable theory. On the other hand, in that same article [2] J. Robinson proved that N is definable in the ring of integers K = Q( √p: p prime), whereas in 2000 [9] C. Videla proved that OK was definable in K, and finally in 2020 C. Mart´ınez-Ranero, J. Utreras and C. Videla proved that the compositum Q(2) = K( √ −1) of all quadratic extensions of Q also has undecidable theory. This last result was generalized by C. Springer [10] in 2020.