For mathematicians, the only thing more exciting than proving a theorem is proving that it can never be proven. These anti-proofs, if you will, stand firmly against all future progress of humanity and state, “No matter how clever you become, what new branches of thought you invent, you’ll never be able to do this. Sorry about it.” The most famous of these is Kurt Gödel’s 1931 Incompleteness Theorem, but just behind it in the annals of mathematics is the 1970 proof by Yuri Matiyasevich that Hilbert’s famous Tenth Problem will never be solved, a proof that might not have happened without the almost other-worldly mathematical insight of Julia Robinson (1919-1985).
Robinson’s back story is familiar to math nerds everywhere. Take a look at any of her class photos, and she sticks out instantly – round owl glasses perched just beneath straight, unstyled hair and above an oversized mouth, all kept in frame by a thick stalk of a neck. She was, from the first, somebody who didn’t care about what other people thought of her, and never really changed, too wrapped up in her inner world to pay much attention to such slight things as outward appearance. She was also subject to constant ill health. At the age of nine, she caught scarlet fever, and hardly had that subsided when she was hit with a round of rheumatic fever which permanently damaged her heart, followed by chorea, which periodically racked her body with spasms.
At last, she caught up on her schoolwork and went to San Diego High School, where her talent for problem-solving kept her in math and physics classes long after most girls dropped them for more practical avenues of study. She was routinely the only girl in those classes, and the best student as well. Graduating, she received a new slide rule (named “Slippy”) from her parents and started her college career at San Diego State University, where the math department wasn’t much of much. They offered two upper division math courses a semester, and that was it.
She might have stayed in that program had it not been for an encounter with E.T. Bell’s magnificent book Men of Mathematics. In it, Robinson saw at last the full grandeur of mathematics, and by implication, how very much she was missing in SDSU’s limiting environment. She made up her mind to go to Berkeley, where the mathematics department was just being shaped into the powerhouse it would become by Griffith C. Evans.
There, she had at last access to the resources she needed to develop into a full mathematician. She took courses in number theory, the discipline that would define her for the rest of her life, from Raphael M. Robinson, and was enchanted enough by his … mathematical demonstrations … that she married him soon thereafter. Her thesis advisor was Alfred Tarski, who in 1939 had made an important addition to Gödel’s Incompleteness Theorem, which makes this as good a time as any to get into some math!
Gödel’s theorem of 1931 states that, if you have a set of statements which contains only natural numbers, the number zero, the successor, addition, and multiplication operations, the logical operations “and”, “or”, and “not”, and the expressions “for all” and “there exist”, then that set must contain statements that cannot be proved or disproved using the Peano axioms (the axioms for the natural numbers like that a=a, or that a=b implies that b=a).
Natural number theory, then, contains statements that cannot be proven using a general algorithm, a result which leaked into philosophy and caused a small cadre of hasty academics desperate for copy to assert that room for God had been found at last in math. Alfred Tarski was curious about whether the Incompleteness Theorem applied to other sets of numbers, and set his sights on the Reals, which are a much more dense set of numbers than the naturals, and offer a much richer set of analytic tools and theorems. In 1939, he discovered that, in fact, the Real numbers don’t suffer from incompleteness as the naturals do, that you can construct an algorithm for deciding the truth of any real-number based statement.
Real number theory is, in the terms of number theory, “decidable” – you can decide whether a random real number statement is true or not using a general algorithm. Natural number theory is not. What was left to decide was the classic middle ground between Integers and Reals – the Rationals.
Remember that Rational numbers are those which can be represented as a ratio of integers. They contain the integers and natural numbers (5 can be represented as 5/1), and are contained in the Reals, but do not contain those Reals which can’t be represented as fractions – numbers like pi, or the square root of 3. The question was, are the numbers you lose when you move from the Reals to the Rationals enough to make the Rationals as undecidable as the Natural numbers?
This was the problem put to Julia Robinson, who characteristically decided to solve it by referencing an obscure set of theorems which, to all appearances, had nothing to do with the decidability of the Rationals. When her colleagues described her, this was the aspect of her work that all of them hit upon at some point – the “How did you possibly think to look there?” aspect of her mathematical mind. Using a set of arcane theorems, and employing her own innate brilliance, she crafted a function that broke the decidability of the Rationals, rendering them brethren to the Naturals.
This work turned out to be excellent training for Hilbert’s Tenth Problem, the ultimate unsolvability of which she spent two decades attempting to establish, only to have the final stroke of the anti-proof pulled off at last by a 22 year old Russian mathematician in 1970. In 1900, David Hilbert had proposed a list of 23 problems for the new century to grapple with. Solving any one of these is a relatively sure way to mathematical immortality, and today only 3 remain unsolved. Hilbert’s Tenth Problem (hereafter H10) was to find a general algorithm that would determine if a random Diophantine equation with integer coefficients was solvable.
Diophantine Equations are just polynomial equations in several variables for which we only accept integer solutions. x2 + y2 = z2, for example, is a Diophantine Equation in three variables with (3,4,5) as one allowable solution. Hilbert challenges us to develop a general method which tells us whether or not a random Diophantine Equation has an integer solution or not. It doesn’t ask us to find the solution, it just asks us to determine whether or not a solution exists.
Surely, that’s a reasonable request, isn’t it? Just one little general method that says “yes” or “no” each time it’s presented with a new Equation – is that too much to ask?
Spoiler alert: Yes.
It turns out that such a method does not exist, cannot exist, will never exist, and the foundation for proving this was laid down by Julia Robinson. Robinson realized that, to evade being decidable by an algorithm, she would have to construct a Diophantine equation whose roots showed exponential growth. She would need to show, in effect, that exponentiation (raising a number to a variable power) was Diophantine, which meant hunting for an equation A with three parameters a, b, and c and a finite number of unknowns whereby A(a, b, c, x1, x2, …. , xm) = 0 has a solution in (x1, …., xm) if and only if a=bc.
If you found that function, it would let you change an exponential Diophantine equation into a regular Diophantine equation, which would mean that exponentials, with their much nastier qualities, could be brought to bear to break any method that might claim to solve H10. In 1950, she simplified the search through another flash of insight that, to get to her H10-breaking function A, all one really needed was a function B with two parameters, a and b, which has the properties (1) that a < bb, and (2) for any integer value of k, there exists an a and b such that a > bk.
That such a Diophantine relation of exponential growth exists became “The JR Hypothesis” and it was recognized that, should it be proven true, should a Diophantine equation be found that fit those properties, it would admit exponential growth into Diophantine equations, and wreck utterly any hopes of finding an algorithm which determines the solvability of all Diophantines. Robinson proposed the JR Hypothesis in 1950 and had to wait two decades until Yuri Matiyasevich discovered the equation and resultant set which fulfilled the JR Hypothesis and thus rendered H10 definitively unsolvable.
(If you’re curious, he found the solution, of all places, in the Fibonacci sequence an+2 = an+1 + an or 0, 1, 1, 2, 3, 5, 8, 13, 21,… If you define a as the bth even term in the Fibonacci sequence, the resulting set of a and b values matches Robinson’s criteria and grows exponentially as ((3+√(5))/2)n. Since the Fibonacci sequence contains all the numbers which solve the Diophantine Equation x2 – xy – y2 = ± 1, this is a Diophantine set which also happens to display exponential properties.)
Matiyasevich became a mathematics superstar at age 22 for his discovery and, in a tale which isn’t told enough in the history of science, went out of his way to always include Julia Robinson in any mention of the cracking of H10. Their correspondence and occasional joint work represents a relationship of total respect and consideration that serves as a model for young scientists recognizing the work that went before them, and for veteran scientists gracefully acknowledging the gifts of a rising generation.
Formal honors followed in rapid succession, as Robinson became the first woman elected to the National Academy of Sciences in 1976, and the first female president of the American Mathematical Society in 1982. But she’ll always be remembered as the person with the astounding ability to concoct math-breaking functions from the arcane theories of far-flung realms of mathematics, and her own inexplicable numerical genius.
FURTHER READING: Number Theory is not an easy branch of mathematics to jump into the middle of. Unlike analysis or hyperbolic geometry, whose basic ideas one is exposed to during a typical high school career, number theory is very much its own thing, and hardly touched in general math classes beyond the classification of numbers as integers, rationals, or reals. Julia: A Life in Mathematics, by her sister Constance Reid, is an interesting mixture of personal reflections, numerous rare photos, and a set of excellent essays by those who worked with Robinson, explaining her various discoveries with perhaps more rigor and detail than the average reader can quite grasp. If, however, number theory is your bag, Matiyasevich wrote an entire book, Hilbert’s Tenth Problem, which delves deep into the history and ultimate anti-solution of the problem.
