What is Russell's paradox, and why did it matter?

Russell's paradox is a contradiction at the base of early set theory. Consider the set R of all sets that are not members of themselves. If R is a member of itself, then by its definition it is not. If R is not a member of itself, then it meets the definition and so it is. Either answer produces a contradiction. The Stanford Encyclopedia of Philosophy says Bertrand Russell discovered it in or around 1901, and Wikipedia describes it as published by Russell in 1901. [1] [2]

Early set theory assumed that any well-defined condition determines a set. If the condition is being a teacup, there is a set of all teacups. This is called the naive or unrestricted comprehension principle. It even seemed to cover contradictory conditions, which would simply give the empty set. Russell's paradox shows that every set theory containing this principle leads to contradictions. The Oxford Companion to Philosophy notes that this is paradoxical because it conflicts with the seemingly inescapable view that any coherent condition determines a class. [1] [2] [3]

A familiar illustration is a barber who shaves all and only those villagers who do not shave themselves. If he does not shave himself, he must; if he does, he must not. Scientific American's explanation uses a similar group of barbers. The Stanford entry stresses that the underlying reasoning is entirely general. It does not depend on set membership at all, and follows from a theorem of pure logic. The barber story is only an analogy, and the paradox itself concerns sets or classes. The same source says a parallel form exists for properties: the property of being a property that does not apply to itself seems to apply to itself if and only if it does not. [4] [1] [5]

Russell outlined the problem in a letter to Gottlob Frege, whose Grundgesetze der Arithmetik depended on the unrestricted principle. According to the Stanford entry, Frege responded with dismay and admiration and never recovered from the blow to his life's work. Russell also saw a threat to his own project, and his struggle with it led to major work, including his theory of types. [1]

The theory of types arranges objects in a hierarchy: individual objects, then sets of them, then sets of sets, and so on. Under it, asking whether a set belongs to itself breaks the type rules, so the troublesome set cannot be formed. Russell and Alfred North Whitehead set this out in a three-volume work. Scientific American adds that Ernst Zermelo independently noticed the same contradiction. The Oxford Companion describes standard responses as limiting which classes exist, in a way that is intuitively satisfactory, excludes R, and keeps all the classes mathematicians need. [4] [6] [5] [3]

The Stanford entry says the paradox has since prompted major advances in logic, set theory and the foundations of mathematics. [1]