ROBINSON, JULIA BOWMAN

(b. St. Louis, Missouri, 8 December 1919; d. Berkeley, California, 30 July 1985), mathematics, mathematical logic, number theory, decision problems, definability.

Robinson’s mathematical work exhibits power and charm. She tackled difficult problems and strove for elegant solutions. Her life and work cannot be properly seen without noting that as a woman in a male-dominated field, she was something of a pioneer. Her métier was the interface between two branches of mathematics, logic and the theory of numbers, ordinarily thought to have little to do with one another. She is particularly known for her contributions to the solution of the tenth problem in a famous list of twenty-three proposed by the mathematician David Hilbert in 1900. She was elected to the National Academy of Sciences and also to the presidency of the American Mathematical Society, in both cases the first female mathematician to be so honored, and was also a recipient of a MacArthur Fellowship.

Early Life Born Julia Bowman, she suffered two calamities early in life. She was only two when her mother died, leaving her father to cope with Julia and her elder sister Constance. After his remarriage, the family moved west, ultimately to San Diego, where her step-sister Billie was born. When Julia was nine she underwent a devastating illness: scarlet fever followed by rheumatic fever. She missed two years of school and suffered very serious damage to her heart. Academically she excelled and soon made up her lost ground. In high school she was the only girl to take the advanced science and mathematics courses and graduated with a number of honors. In 1936 she entered San Diego State College, majoring in mathematics. Seeking wider vistas, she transferred to the University of California at Berkeley for her senior year. Among the five mathematics courses she took that year was one on the theory of numbers taught by Raphael Robinson. Impressed by her ability, he convinced her to continue her studies as a graduate student. Raphael was a mathematician of broad interests and knowledge and an ideal mentor. But soon their relationship became more personal and they were married in December 1941. Their hopes to begin a family were dashed when Julia suffered a miscarriage and was warned by a doctor that, because of her severely damaged heart, pregnancy would be extremely dangerous. His opinion was that she would likely die before she was forty. In an effort to help Julia overcome the deep depression into which she was flung, Raphael encouraged her to seek solace in mathematics.

Mathematical Background The 1930s had seen revolutionary developments in the ancient subject of logic, drastically changed from the traditional field originated by Aristotle. Kurt Gödel’s famous incompleteness theorem had pointed to the inherent limitations of formal systems of logic in encapsulating mathematical practice. Work by Alonzo Church, Alan Turing, and Emil Post as well as Gödel himself had shown that the question of the existence of algorithmic solutions to specific mathematical problems could be given a precise formulation. This opened the possibility that in specific cases, such algorithmic solutions might not exist, and even that in such cases, this might be proved. Alfred Tarski had explained how to define semantic notions of truth and definability of formal languages. These were the developments that provided the context of Julia Robinson’s research.

Any particular branch of mathematics will use symbols to stand for the particular operations and relations that are fundamental to that subject. In addition to such symbols, modern mathematical logic uses the special symbols

along with the familiar = sign. One speaks of these symbols together with those corresponding to a particular branch of mathematics as constituting a language. Julia Robinson’s work was largely in the context of the language of arithmetic which uses the two symbols + and × standing for addition and multiplication, respectively, as well as symbols for 0 and 1. Letters of the alphabet are used as variables, and in the case of the language of arithmetic, they are usually understood to vary over the familiar natural numbers 0,1,2 …… So for example, the “sentence”

expresses the true proposition that adding two odd numbers yields an even number. The formula (u)(x = u+u+1)> by itself defines the set of odd numbers, i.e., if x is replaced by a particular natural number, the resulting sentence will be true if and only if that number is odd. Questions of definability and the existence of algorithms were fundamental to Robinson’s work.

A set of natural numbers S is called computable (or recursive) if there is an algorithm that can determine for a given natural number n whether or not n belongs to S. A set of natural numbers is called listable (the term preferred by Julia Robinson) or recursively enumerable if there is an algorithm for systematically making a list of the members of S. All unsolvability results can be thought of as consequences of the key theorem: There exists a listable set that is not computable. These matters were also very important in Robinson’s work.

Julia Robinson’s Dissertation It was in a seminar led by the charismatic Alfred Tarski, one of the great logicians of the twentieth century, that Robinson found her métier. Tarski had left his native Poland in August 1939 on what was to have been a brief trip to attend a conference in the United States, just before the German invasion of Poland precipitated the Second World War. Tarski posed a number of unsolved questions about definability in the language of arithmetic to which Robinson was attracted. By the 1940s it was well known that there is no algorithm to determine whether a given sentence in the language of arithmetic, with the variables ranging over the natural numbers, is true. As one says, this is an algorithmically unsolvable problem. Tarski wanted to know whether the same is true when in this same language, variables are permitted to range over all rational numbers instead of just the natural numbers. (The rational numbers are those expressible as fractions m/n or -m/n where m is a natural number and n is a non-zero natural number.) There had been developed techniques for “reducing” one such “decision problem” to another. In this case one would show that if there were an algorithm for testing for truth a sentence of the language of arithmetic with the variables constrained to vary over the rational numbers, such an algorithm could be used to furnish an algorithm to do the same when the variables range over the natural numbers. So, since there is no such algorithm for the latter, it would follow that neither could there be one for the former.

The main result of Robinson’s dissertation was an explicit formula in the language of arithmetic, with the variables constrained to vary over the rational numbers, that defines precisely the set of integers (that is, the set of natural numbers and their negatives). It then followed that the problem of determining the truth of a sentence of arithmetic remains unsolvable even when the variables range over the rational numbers. Other unsolvability results followed as well. Robinson’s approach was intricate, elegant, and ingenious using some rather deep ideas from number theory.

Elegant Characterizations Robinson always sought elegance and simplicity in her mathematical work. One of her early papers showed how to characterize, in a particularly simple way, the algorithmically computable functions (also called the recursive functions) that map the natural numbers into themselves. Her beautiful characterization involves two initial functions and three operations for obtaining new functions from given functions. One of the initial functions is just the successor function S(x)= x+1. The other, which Robinson calls E, is defined as the difference between a given number and the largest perfect square that does not exceed it. (Thus E(19) = 19 - 16 = 3 and E(25) = 25 -25 = 0.) The three operations are as follows: (1) from given functions F and G obtain the function H(x)=F(G(x)); (2) from given functions F and G obtain the function H(x)=F(x) + G(x); and (3) from a given function F whose values include all natural numbers obtain the function H where H(x) is the least number t for which F(t)=x.

It is truly remarkable that all computable functions (from the natural numbers to the natural numbers) can be obtained by beginning with the two initial functions and applying these three operations over and over again.

Much later Robinson showed the same elegance and verve in finding new characterizations of a domain far removed from the computable. The existence of a listable set K that is not computable has already been mentioned. So there is no algorithm for determining membership in K. By considering sets that can be listed by algorithms having access to membership information about such sets (metaphorically via an “oracle”) additional sets can be brought into the fold, and this process can be iterated. By allowing this iteration to occur any finite number of times, the sets obtained turn out to be exactly those called arithmetical, the sets definable in the language of arithmetic with variables ranging over the natural numbers. But there is no need to stop here. One can define a non-arithmetical set, and then use that as an “oracle” to be able list still more sets. There is a natural place where this process does come to an end, and the sets of natural numbers so obtained are called hyperarithmetical. It was this rarefied realm for which Robinson provided a simple and direct characterization.

Existential Definability and Hilbert’s Tenth Problem The work for which Julia Robinson is most remembered originated with an apparently simple problem posed by Alfred Tarski. Tarski wanted to know which sets of natural numbers are definable by formulas of the language of arithmetic if the symbols and are excluded. He called such sets existentially definable and proposed the problem of proving that the set {1,2,4,8,16, ….} of powers of 2 is not existentially definable. This was exactly the sort of problem that Robinson liked. The notion of existential definability could easily be seen to be closely related to problems of a kind that number theorists study, so-called Diophantine problems. These typically have to do with a polynomial equation p(a,x,y,z,u,v,w,….) = 0 with integer coefficients where a is a parameter and x,y,z,u,v,w,…. are “unknowns.” (Recall that such a polynomial is just the sum of terms like 5a³x²v⁵ and -7a⁴x³z⁶.) For particular Diophantine equations of this kind, number theorists try to determine for which natural number values of the parameter a, the equation has natural number solutions in the unknowns. Now by simple standard methods it is easy to see that a set of natural numbers S is existentially definable if and only if there is a polynomial equation of this kind such that S is exactly the set of values of the parameter for which the equation has natural number solutions. For this reason, existentially definable sets are also called Diophantine, and this is the term that has been adopted in the later literature.

Not having any success in proving Tarski’s conjecture that the set of powers of 2 is not Diophantine, Robinson began to consider the possibility that Tarski’s guess might have been wrong. In order to make any progress, she had to assume a certain hypothesis, unproved at the time, that came to be called J.R.; roughly speaking J.R. states that there is a Diophantine equation with two parameters a,b with the property that the pairs (a,b) for which the equation has solutions are such that b grows exponentially as a function of a. By assuming J.R. and carrying out a complex and ingenious analysis, she proved not only that the powers of 2 are Diophantine, but also that the set of prime numbers as well as many others are also. It is readily seen that all Diophantine sets are listable, but now she wondered whether the converse might be true, whether all listable sets might be Diophantine. This, she knew would have profound consequences.

In 1900, to greet the new century, the great mathematician David Hilbert proposed a list of twenty-three problems to stand as a challenge. The tenth on his list was to provide an algorithm to determine whether a given polynomial Diophantine equation has solutions. If indeed all listable sets were Diophantine, she realized, then in particular there would be a non-computable Diophantine set, implying that there could be no algorithm such as Hilbert had asked for. This would constitute a negative solution of Hilbert’s tenth problem.

In the summer of 1959, Robinson received in the mail a preprint of a paper by Martin Davis and Hilary Putnam. The paper contained a proof that, assuming J.R., all listable sets are indeed Diophantine. However, the proof had an important gap. It used the fact that there are arbitrarily long sequences of prime numbers with the special property that the difference between consecutive terms of the sequence is constant. Although this is true, in 1959 it was a mere hypothesis; it was proved only in 2004. Robinson knew the previous work of Davis and Putnam very well and expressed surprise and pleasure at their accomplishment. In very short order, she showed how to do without the extra hypothesis about prime numbers, and even found a short version of the proof. So, to obtain the anticipated negative solution of Hilbert’s tenth problem, it only remained to prove J.R.

This was accomplished in January 1970 by the twenty-two-year-old Yuri Matiyasevich using the famous Fibonacci sequence 1,1,2,3,5,8,13,…. He found a Diophantine equation with two parameters a,b that he was able to prove has solutions just in case b is the Fibonacci number in the 2a-th place in this sequence. Because the Fibonacci numbers do grow exponentially, this did constitute a proof of J.R. Robinson was delighted by Matiyasevich’s ingenious proof and traveled to Leningrad where their families met. Their collaboration was fruitful; together they were able to show that Hilbert’s tenth problem is unsolvable even for equations in 13 unknowns. (Later Matiyasevich was able to reduce the number to 9.)

Coda The “nepotism” rules in effect at the University of California would have made a regular faculty appointment for Robinson impossible as long as her husband was on the faculty. In any case it may well be that her health problems would have precluded a full-time position. She did occasionally teach a course as an adjunct, and she served as de facto adviser to two excellent doctoral students, Leonard Adleman and Kenneth Manders. Robinson defied the doctor’s prediction that she would not live to be forty, but by her forty-first birthday her damaged heart had brought her close to invalid status. She was rescued by a surgical procedure that had only recently become available and which greatly improved her situation, enabling her to live an active life for an additional twenty-five years.

Her outstanding work was recognized by her election in 1975 to the National Academy of Sciences, the first woman to be elected to the mathematics section. That same year she was finally offered a professorial appointment at the University of California at Berkeley.

At her request it was a quarter-time appointment. A MacArthur Fellowship came in 1983. She was elected president of the American Mathematical Society for 1983–1984, the first woman to hold this office. Tragically, she was unable to complete her term. She was found to be suffering from leukemia during the summer of 1984. After a brief remission, Julia Robinson died of the disease on 30 July 1985.

BIBLIOGRAPHY

WORKS BY ROBINSON

“Definability and Decision Problems in Arithmetic.” Journal of Symbolic Logic 14 (1949): 98–114. This was Robinson’s dissertation. “General Recursive Functions.” Proceedings of the American Mathematical Society 1 (1950): 703–718. In addition to the characterization of computable functions of one argument described above, many other interesting results are discussed in this paper. “Existential Definability in Arithmetic.” Transactions of the American Mathematical Society 72 (1952): 437–449. A fundamental paper in which what came to be called J.R. was shown to imply the existential definability of the powers of 2, the primes, and actually, the full exponential function.

With Martin Davis and Hilary Putnam.“The Decision Problem for Exponential Diophantine Equations.” Annals of Mathematics 74 (1961): 425–436. It was in this paper that it was proved that J.R. implies the unsolvability of Hilbert’s tenth problem. “An Introduction to Hyperarithmetical Functions.” Journal of Symbolic Logic 32 (1967): 325–342. This was Robinson’s one excursion to the very uncomputable.

With Yuri Matiyasevich. “Reduction of an Arbitrary Diophantine Equation to One in 13 Unknowns.” Acta Arithmetica 27 (1975): 521–553. Virtuoso number theory! With Martin Davis and Yuri Matiyasevich. “Hilbert’s Tenth Problem. Diophantine Equations: Positive Aspects of a Negative Solution.” In Mathematical Developments Arising from Hilbert Problems, edited by Felix Browder. Providence, RI: American Mathematical Society, 1976.

Proceedings of Symposia in Pure Mathematics 28 (1976): 323–378. A survey of the proof of the unsolvability of Hilbert’s tenth problem as well as of mathematical developments stemming from it by three of the four mathematicians whose work led to that proof.

The Collected Works of Julia Robinson. Edited by Solomon

Feferman. Providence, RI: American Mathematical Society, 1996. All twenty-five of Robinson’s publications are reprinted here in full. In addition, there is the fine biographical essay about her written by Feferman for the National Academy of Sciences.

OTHER SOURCES

Davis, Martin. “Hilbert’s Tenth Problem Is Unsolvable.”

American Mathematical Monthly 80 (1973): 233–269; reprinted as an appendix in Computability and Unsolvability, edited by Martin Davis. New York: Dover, 1983. A Steele-Prize-winning essay that offers the complete proof of the unsolvability of Hilbert’s tenth problem. The Dover reprint is of one of the first book-length treatments of computability theory.

———, and Reuben Hersh. “Hilbert’s Tenth Problem.”

Scientific American 229 (November 1973): 84–91. Reprinted in The Chauvenet Papers, Vol. 2, edited by J. C. Abbott. Washington, DC: Mathematical Association of America, 1978. A Chauvenet-Prize winning article intended for the general educated public.

Matiyasevich, Yuri. “My Collaboration with Julia Robinson.”

The Mathematical Intelligencer 14 (1992): 38–45. His story of how a young Russian and a much older American woman came to produce elegant mathematics together.

———. Hilbert’s Tenth Problem. Cambridge, MA: MIT Press,

1993. An excellent introduction and survey suitable for undergraduate mathematics majors, with a very inclusive bibliography.

Reid, Constance. Julia, a Life in Mathematics. Washington, DC:

Mathematical Association of America, 1996. By Robinson’s sister, it has photographs, Reid’s useful biography, entitled “The Autobiography of Julia Robinson,” and a brief note by Martin Davis about his work with Hilary Putnam.

Martin Davis

Robinson, Julia Bowman

American Logician and Number Theorist 1919–1985

Julia Bowman Robinson, the second daughter of Helen Hall and Ralph Bowers Bowman, was born in St. Louis, Missouri, on December 8, 1919. When Robinson was 9 years old, she contracted scarlet fever and a year later developed rheumatic fever. Julia's father hired a private teacher to work with her three mornings a week and, in one year, she had completed the state-required materials for the fifth through eighth grades. It was during this time that she first became fascinated with mathematics.

Early Mathematics Honors

By the time Robinson entered her junior year of high school, she was the only girl taking mathematics courses and advanced science courses such as physics. In 1936, when she graduated* from high school, she was awarded honors in mathematics and science, including the Bausch-Lomb medal for all-around excellence in science.

*When Julia Robinson graduated from high school, her parents gave her a slide rule that she treasured and named "Slippy."

At the age of 16, Robinson enrolled at San Diego State College, now known as San Diego State University, where her older sister, Constance Bowman, attended classes. Julia majored in mathematics with the intention of earning teaching credentials.

Prior to her senior year, Julia transferred to the University of California at Berkeley to study to become a mathematician. It was there that she met Raphael M. Robinson, an assistant professor of mathematics at Berkeley. After receiving a Bachelor of Arts (B.A.) in 1940, she immediately began graduate studies and earned a graduate teaching fellowship in the mathematics department.

In 1941, during her second year of graduate school at Berkeley, Julia married Robinson. Because of a university rule forbidding spouses to teach concurrently in the same department, Julia gave up her teaching fellowship and attempted to start a family.

But Robinson later discovered the risk of bearing a child was too dangerous for her health due to the rheumatic fever she suffered as a child. In 1946, at the encouragement of her husband, Robinson turned her attention back to mathematics and in 1947 began to work at Berkeley toward a Doctor of Philosophy (Ph.D.) under the advisement of Alfred Tarski, a Polish mathematician.

Work on the Tenth Problem

In 1948 Robinson received her Ph.D. and began work on trying to solve the tenth on a list of twenty-three major problems posed by David Hilbert, a prominent mathematician at the beginning of the century. The Tenth Problem was:

Given a Diophantine equation , with only integer solutions, with any number of unknown quantities and with rational integral numerical coefficients (and whole-number exponents) devise a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers. For example, x ² + y ² − 2 = 0 has four Diophantine solutions—(1, 1), (−1, 1), (−1,−1), (1,−1)—but x ² + y ² − 3 = 0 has no solutions.

Striving to solve this problem occupied the largest portion of Robinson's professional career. The solution, which would be her major contribution to mathematics, was not completed until 1970. Many honors were bestowed upon Robinson as a result of her foundation for the solution to the Tenth Problem. In 1975 she became the first woman mathematician to be elected to the National Academy of Science. She later became the first woman officer of the American Mathematical Society (1978) and the first woman to serve as its president (1982). In 1983 she was awarded a MacArthur Fellowship, consisting of $60,000 a year for 5 years, in recognition of her contributions to mathematics.

In August 1984, Robinson was diagnosed with leukemia, and she died on July 30, 1985, at the age of 65.

Gay A. Ragan

Bibliography

Grinstein, Louise S., and Paul J. Campbell. Women in Mathematics. Westport, CT: Greenwood Press, Inc., 1987.

Henderson, Henry. "Julia Bowman Robinson." In Modern Mathematicians. New York: Facts on File, Inc., 1996.

National Council of Teachers of Mathematics. Celebrating Women in Mathematics and Science. Reston, VA: National Council of Teachers of Mathematics, 1996.

Internet Resources

"Julia Bowman Robinson." <http://www.agensscott.edu/lriddle/women/robinson.htm>.

"Julia Bowman Robinson." <http://www-grouups,dcs.st-and.ac.uk/~history/Mathematicians/Robinson_Julia.html>.

"Julia Robinson, Functional Equations in Arithmetic." <http://www.awm.math.org/noetherbrochure/Robinson82.html>.

Reid, Constance. Being Julia Robinson's Sister. Notices of the American Mathematical Society, December 1996, p. 1486–1492. <http://www.ams.org/notices/>.

Julia Robinson

Excelling in the field of mathematics, Julia Robinson (1919-1985) was instrumental in solving Hilbert's tenth problem—to find an effective method for determining whether a given diophantine equation is solvable with integers. Over a period of two decades, she developed the framework on which the solution was constructed.

In recognition of her accomplishments, Julia Robinson became the first woman mathematician elected to the National Academy of Sciences, the first female president of the American Mathematical Society, and the first woman mathematician to receive a MacArthur Foundation Fellowship.

Robinson was born Julia Bowman on December 8, 1919, in St. Louis, Missouri. Her mother, Helen Hall Bowman, died two years later; Robinson and her older sister went to live with their grandmother near Phoenix, Arizona. The following year their father, Ralph Bowman, retired and joined them in Arizona after becoming disinterested in his machine tool and equipment business. He expected to support his children and his new wife, Edenia Kridelbaugh Bowman, with his savings. In 1925, her family moved to San Diego; three years later a third daughter was born.

At the age of nine, Robinson contracted scarlet fever, and the family was quarantined for a month. They celebrated the end of isolation by viewing their first talking motion picture. The celebration was premature, however, as Robinson soon developed rheumatic fever and was bedridden for a year. When she was well enough, she worked with a tutor for a year, covering the required curriculum for the fifth through eighth grades. She was fascinated by the tutor's claim that it had been proven that the square root of two could not be calculated to a point where the decimal began to repeat. Her interest in mathematics continued at San Diego High School; when she graduated with honors in mathematics and science, her parents gave her a slide rule that she treasured and named "Slippy."

At the age of sixteen, Robinson entered San Diego State College. She majored in mathematics and prepared for a teaching career, being aware of no other mathematics career choices. At the beginning of Robinson's sophomore year, her father found his savings depleted by the Depression and committed suicide. With help from her older sister and an aunt, Robinson remained in school. She transferred to the University of California, Berkeley, for her senior year and graduated in 1940.

At Berkeley, she found teachers and fellow students who shared her excitement about mathematics. In December of 1941, she married an assistant professor named Raphael Robinson. At that time she was a teaching assistant at Berkeley, having completed her master's degree in 1941. The following year, however, the school's nepotism rule prevented her from teaching in the mathematics department. Instead, she worked in the Berkeley Statistical Laboratory on military projects. She became pregnant but lost her baby; because of damage to Robinson's heart caused by the rheumatic fever, her doctor warned against future pregnancies. Her hopes of motherhood crushed, Robinson endured a period of depression that lasted until her husband rekindled her interest in mathematics.

In 1947 she embarked on a doctoral program under the direction of Alfred Tarski . In her dissertation, she proved the algorithmic unsolvability of the theory of the rational number field. Her Ph.D. was conferred in 1948. That same year, Tarski discussed an idea about diophantine equations (polynomial equations of several variables, with integer coefficients, whose solutions are to be integers) with Raphael Robinson, who shared it with his wife. By the time she realized it was directly related to the tenth problem on Hilbert's list, she was too involved in the topic to be intimidated by its stature. For the next twenty-two years she attacked various aspects of the problem, building a foundation on which Yuri Matijasevic proved in 1970 that the desired general method for determining solvability does not exist. While working at the RAND Corporation in 1949 and 1950, Robinson developed an iterative solution for the value of a finite two-person zero-sum game. Her only contribution to game theory is still considered a fundamental theorem in the field.

Robinson's heart damage was surgically repaired in 1961, but her health remained impaired. Her fame from the Hilbert problem solution resulted in her appointment as a full professor at Berkeley in 1976, although she was expected to carry only one-fourth of the normal teaching load. Eight years later she developed leukemia and died on July 30, 1985.

Further Reading

"Julia Bowman Robinson, 1919-1985," in Notices of the American Mathematical Society, November, 1985, pp. 738-742.

Reid, Constance, "The Autobiography of Julia Robinson," in The College Mathematics Journal, January, 1986, pp. 2-21.

Smorynski, C., "Julia Robinson, In Memoriam," in The Mathematical Intelligencer, spring 1986, pp. 77-79. □