Russell's Paradox

THE SPECTER OF CONTRADICTION

Formalism has an austere elegance. It appeals to people like G. H. Hardy, Antonin Scalia, and me, who relish that feeling of a nice rigid theory shut tight against contradiction. But it’s not easy to hold to principles like this consistently, and it’s not clear it’s even wise. Even Justice Scalia has occasionally conceded that when the literal words of the law seem to require an absurd judgment, the literal words have to be set aside in favor of a reasonable guess as to what Congress must have meant. In just the same way, no scientist really wants to be bound strictly by the rules of significance, no matter what they say their principles are. When you run two experiments, one testing a clinical treatment that seems theoretically promising and the other testing whether dead salmon respond emotionally to romantic photos, and both experiments succeed with p-values of .03, you don’t really want to treat the two hypotheses the same. You want to approach absurd conclusions with an extra coat of skepticism, rules be damned.

Formalism’s greatest champion in mathematics was David Hilbert, the German mathematician whose list of twenty-three problems, prepared for a lecture in Paris at the 1900 International Congress of Mathematics, set the course for much of twentieth-century math. Hilbert is so revered that any work that touches even tangentially on one of his problems takes on a little extra shine, even a hundred years later. I once met a historian of German culture in Columbus, Ohio, who told me that Hilbert’s predilection for wearing sandals with socks is the reason that fashion choice is still noticeably popular among mathematicians today. I could find no evidence this was actually true, but it suits me to believe it, and it gives a correct impression of the length of Hilbert’s shadow.

Many of Hilbert’s problems fell quickly; others, like number 18, concerning the densest possible packing of spheres, were settled only recently, as we saw in chapter 12. Some are still open, and hotly pursued. Solving number 8, the Riemann Hypothesis, will get you a million-dollar prize from the Clay Foundation. At least once, the great Hilbert got it wrong: in his tenth problem, he asked for an algorithm that would take any equation and tell you whether it had a solution in which all the variables took whole-number values. In a series of papers in the 1960s and ’70s, Martin Davis, Yuri Matijasevic, Hilary Putnam and Julia Robinson showed that no such algorithm existed. (Number theorists everywhere breathed a sigh of relief—it might have been a bit dispiriting had it transpired that a formal algorithm could autosolve the problems we’ve spent years on.)

Hilbert’s second problem was different from the others, because it was not so much a mathematical question as a question about mathematics itself. He began with a full-throated endorsement of the formalist approach to mathematics:

When we are engaged in investigating the foundations of a science, we must set up a system of axioms which contains an exact and complete description of the relations subsisting between the elementary ideas of that science. The axioms so set up are at the same time the definitions of those elementary ideas; and no statement within the realm of the science whose foundation we are testing is held to be correct unless it can be derived from those axioms by means of a finite number of logical steps.

By the time of the Paris lecture, Hilbert had already revisited Euclid’s axioms and rewritten them to remove any trace of ambiguity; at the same time, he had rigorously squeezed out any appeal to geometric intuition. His version of the axioms really does make just as much sense if “point” and “line” are replaced by “frog” and “kumquat.” Hilbert himself famously remarked, “One must be able to say at all times—instead of points, straight lines, and planes— tables, chairs, and beer mugs.” One early fan of Hilbert’s new geometry was the young Abraham Wald, who, while still a student at Vienna, had shown how some of Hilbert’s axioms could be derived from the others, and were thus expendable.

Hilbert was not content to stop with geometry. His dream was to create a purely formal mathematics, where to say a statement was true was precisely to say it obeyed the rules laid down at the beginning of the game, no more, no less. It was a mathematics Antonin Scalia would have liked. The axioms Hilbert had in mind for arithmetic, first formulated by the Italian mathematician Giuseppe Peano, hardly seem the sort of thing about which there could be any interesting questions or controversy. They say things like “Zero is a number,” “If x equals y and y equals z, then x equals z,” and “If the number directly following x is the same as the number directly following y, then x and y are the same.” They’re the truths we hold to be self-evident.

What’s remarkable about these Peano axioms is that from these bare beginnings one can generate a great deal of mathematics. The axioms themselves seem to refer only to whole numbers, but Peano himself showed that, starting from his axioms and proceeding purely by definition and logical deduction, one could define the rational numbers and prove their basic properties. The mathematics of the nineteenth century had been plagued by confusion and crises as widely accepted definitions in analysis and geometry were found to be logically flawed. Hilbert saw formalism as a way of starting over clean, building on a foundation so basic as to be completely incontrovertible.

But a specter was haunting Hilbert’s program—the specter of contradiction. Here’s the nightmare scenario. The community of mathematicians, working together in concert, rebuilds the entire apparatus of number theory, geometry, and calculus, starting from the bedrock axioms and laying on new theorems, brick by brick, each layer glued to the last by the rules of deduction. And then, one day, a mathematician in Amsterdam proves that a certain mathematical assertion is the case, while another mathematician in Kyoto proves that it is not.

Now what? Starting from assertions one cannot possibly doubt, one has arrived at a contradiction. Reductio ad absurdum. Do you conclude that the axioms were wrong? Or that there’s something wrong with the structure of logical deduction itself? And what do you do with the decades of work based on those axioms?

Thus, the second problem among those Hilbert presented to the mathematicians gathered in Paris:

But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms: To prove that they are not contradictory, that is, that a definite number of logical steps based upon them can never lead to contradictory results.

One is tempted simply to assert that such a terrible outcome can’t happen. How could it? The axioms are obviously true. But it was no less obvious to the ancient Greeks that a geometric magnitude must be a ratio of two whole numbers; that’s how their notion of measurement worked, until the whole framework got mugged by the Pythagorean Theorem and the stubbornly irrational square root of 2. Mathematics has a nasty habit of showing that, sometimes, what’s obviously true is absolutely wrong. Consider the case of Gottlob Frege, the German logician who, like Hilbert, was laboring to shore up the logical underpinnings of mathematics. Frege’s focus was not number theory, but the theory of sets. He, too, started from a sequence of axioms, which seemed so obvious as to hardly need stating. In Frege’s set theory, a set was nothing other than a collection of objects, called elements. Often we use curly brackets {} to denote the sets whose elements are thereby enclosed; so that {1,2,pig} is the set whose elements are the number 1, the number 2, and a pig.

When some of those elements enjoy a certain property and others don’t, there’s a set that is the collection of all those elements with the specified property. To make it a little more down to earth: there is a set of pigs, and among those, the ones that are yellow form a set, the set of yellow pigs. Hard to find much to take issue with here. But these definitions are really, really general. A set can be a collection of pigs, or real numbers, or ideas, possible universes, or other sets. And it’s that last one that causes all the problems. Is there a set of all sets? Sure. A set of all infinite sets? Why not? In fact, both of these sets have a curious property: they are elements of themselves. The set of infinite sets, for example, is certainly itself an infinite set; its elements include sets like

{the integers}

{the integers, and also a pig}

{the integers, and also the Eiffel Tower}

and so on and so on. Clearly there’s no end.

We might call such a set ouroboric, after the mythical snake so hungry it chows down on its own tail and consumes itself. So the set of infinite sets is ouroboric, but {1,2,pig} is not, because none of its elements is the set {1,2,pig} itself; all its elements are either numbers or farm animals, but not sets.

Now here comes the punch line. Let NO be the set of all non-ouroboric sets. NO seems like a weird thing to think about, but if Frege’s definition allows it into the world of sets, so must we.

Is NO ouroboric or not? That is, is NO an element of NO? By definition, if NO is ouroboric, then NO cannot be in NO, which consists only of non-ouroboric sets. But to say NO is not an element of NO is precisely to say NO is non-ouroboric; it does not contain itself.

But wait a minute—if NO is non-ouroboric, then it is an element of NO, which is the set of all non-ouroboric sets. Now NO is an element of NO after all, which is to say that NO is ouroboric.

If NO is ouroboric, it isn’t, and if it isn’t, it is.

This, more or less, was the content of a letter the young Bertrand Russell wrote to Frege in June 1902. Russell had met Peano in Paris at the International Congress—whether he attended Hilbert’s talk isn’t known, but he was certainly on board with the program of reducing all of mathematics to a pristine sequence of deductions from basic axioms. Russell’s letter starts out like a fan letter to the older logician: “I find myself in full accord with you on all main points, especially in your rejection of any psychological element in logic and in the value you attach to a conceptual notation for the foundations of mathematics and of formal logic, which, incidentally, can hardly be distinguished.”

But then: “I have encountered a difficulty only on one point.”

And Russell explains the quandary of NO, now known as Russell’s paradox.

Russell closes the letter by expressing regret that Frege had not yet published the second volume of his Grundgesetze (“Foundations”). In fact, the book was finished and already in press when Frege received Russell’s letter. Despite the respectful tone (“I have encountered a difficulty,” not “Hi, I’ve just borked your life’s work”), Frege understood at once what Russell’s paradox meant for his version of set theory. It was too late to change the book, but he hurriedly appended a postscript recording Russell’s devastating insight.