existential form in the structure (N, +, ·). Julia Robinson's work here started with the specific question, posed by Tarski, whether the set {2, 22, . . . , 2n, . . .} of powers of 2 is Diophantine. At first she tried to establish Tarski's conjecture that the answer would be negative, but failing in that, she began to consider the opposite conjecture, and before long was led to the general problem of the Diophantine definability of arbitrary recursively enumerable sets. In her paper (1952) Robinson reported her first results in this direction. She showed there if R is any binary relation in the natural numbers of roughly exponential growth in the sense of (5) next, then the relation x Pow y (x is some power of y) is existentially definable in the structure (N, +, ·, R), where:

Furthermore, she showed that

(6) The relations xy = z, (x/y) = z and x! = y are all existentially definable in terms of Pow, hence in terms of any R of roughly exponential growth.

The full significance of Robinson's 1952 results was not to emerge for close to a decade. During that period she continued to work hard on the general problem of Diophantine definability without substantial progress, though, as described above, she was able to obtain very satisfying results in her other two main areas of interest.

Around 1960, Julia received the draft of a paper by Martin Davis and Hilary Putnam in which they showed that if the famous hypothesis that there exist arbitrarily long arithmetic progressions containing only prime numbers were true, then every recursively enumerable (r.e.) set would be exponen-



The National Academies | 500 Fifth St. N.W. | Washington, D.C. 20001
Copyright © National Academy of Sciences. All rights reserved.
Terms of Use and Privacy Statement