Russell's Paradox

The previous essay ended with a set built by a diagonal rule. Given a set $A$ and a function $f:A\to\mathcal P(A)$, we selected certain elements from $A$. What if we remove that starting set and ask for every object satisfying a description? The difference between those two moves is the story of Russell's paradox.

A tempting rule for making sets

Suppose every clearly stated condition $\varphi(x)$ determines a set containing exactly the objects that satisfy it:

$$\exists S\,\forall x\bigl(x\in S\leftrightarrow\varphi(x)\bigr).$$

This is unrestricted comprehension. Its appeal is easy to understand. We can describe the even positive integers, or the points at distance one from the origin, and then speak of the resulting collections. Yet those examples can already be formed inside known sets: the even integers inside $\mathbb N$, the circle inside the plane. Neither example justifies a rule that ranges over every mathematical object without a prior domain.

It is also too simple to say that Cantor or every nineteenth-century mathematician explicitly adopted the displayed formula as an axiom. It captures a powerful informal expectation of the period: a sufficiently definite property should have a corresponding collection. Russell found a property for which that expectation fails.

Frege's logical project

Gottlob Frege hoped to derive arithmetic from logic. His Begriffsschrift (1879) introduced a precise logical language; the two volumes of Basic Laws of Arithmetic appeared in 1893 and 1903. In that system, a concept applies or does not apply to an object, and its extension is treated as an object in its own right. Frege's Basic Law V says, in effect, that two concepts have the same extension exactly when they apply to the same objects.

Frege's formal system was more specific than the informal comprehension rule above. Still, its rules for extensions were strong enough to reproduce the crucial contradiction. This matters historically: Russell did not merely find a strange phrase in ordinary language. He found that an ambitious formal account of arithmetic could derive incompatible conclusions.

On 16 June 1902 Russell wrote to Frege about the difficulty. Frege's second volume was already in press. Rather than reproduce a long translated letter here, we can state the mathematical point directly.

The set that reverses its answer

Consider the property “does not belong to itself.” Unrestricted comprehension would supply the set

$$R=\{x\mid x\notin x\}.$$

For any object $a$, the proposed definition gives $a\in R$ exactly when $a\notin a$. Substitute $R$ for $a$:

$$R\in R\quad\leftrightarrow\quad R\notin R.$$

If $R$ belongs to itself, it satisfies the condition for not belonging to itself. If it does not belong to itself, it satisfies the condition for belonging. The difficulty is a contradiction in the rule that was supposed to guarantee $R$ as a set. It is not evidence that a particular set happens to have an unusual property.

The argument does not need the law of excluded middle. From the left-to-right implication we can infer $R\notin R$. The reverse implication then gives $R\in R$. Those two conclusions conflict even in intuitionistic logic. Changing the logic may alter other foundational debates, but it does not by itself rescue unrestricted comprehension.

An everyday “barber who shaves exactly those who do not shave themselves” can make the pattern memorable. The barber story is an analogy. The force of Russell's result comes from asking whether the assumed rules of a mathematical theory actually permit the object $R$.

What the contradiction changed

Frege acknowledged the damage in an appendix to the second volume of Basic Laws. His attempt to repair the extension principle did not restore the original project. The paradox also sharpened a question that would shape twentieth-century foundations: which descriptions may be used to form mathematical objects?

Two influential answers will occupy the next essays. Russell and Alfred North Whitehead restricted the grammar of expressions through a hierarchy of types. Ernst Zermelo restricted the existence claim: a property may select a subset of a set already given, without promising a set of everything satisfying the property.

The lesson is narrower and more useful than “definitions are dangerous.” We can still define the even numbers, circles, and countless other sets. We must say what domain a definition ranges over and what principles make the resulting collection available.

Sources

• Russell's letter to Frege, 16 June 1902, transcribed by the Bertrand Russell Archives.
• Frege, Basic Laws of Arithmetic, volumes I–II (1893, 1903); the second volume includes his response to Russell's discovery.
• Russell and Whitehead, Principia Mathematica, Introduction (1910), on the contradictions and the theory of types.