Russell's paradox

In 1901, Bertrand Russell published a paradox in set theory, now called Russell's paradox or Russell's antinomy. It demonstrates that any set theory allowing an unrestricted comprehension principle leads to contradictions. This principle states that for any well-defined property, there exists a set containing exactly those objects with that property. Russell defined the set R as the collection of all sets that are not members of themselves.

Informal presentation

If R is not a member of itself, then by its definition it must be a member of itself. Conversely, if it is a member of itself, then it does not meet the definition and therefore is not a member of itself. This contradiction is the core of the paradox.

Set-theoretic responses

Russell also showed that a version of this paradox could be derived within Gottlob Frege's axiomatic system, undermining Frege's project to reduce mathematics to logic and challenging the logicist program. Two major solutions emerged in 1908: Russell's own type theory and Zermelo set theory. Zermelo's axioms restricted the unrestricted comprehension principle.

With later contributions from Abraham Fraenkel, Zermelo set theory evolved into standard Zermelo–Fraenkel set theory (often called ZFC when including the axiom of choice). The key difference between the two solutions is that Zermelo modified set theory's axioms while keeping a standard logical language, whereas Russell altered the logical language itself. The language of ZFC, with help from Thoralf Skolem, became that of first-order logic.

Ernst Zermelo had independently discovered the paradox by 1902, possibly as early as 1899, but did not publish it. It remained known only to David Hilbert, Edmund Husserl, and others at the University of Göttingen.

History

Zermelo did not see the paradoxes as a crisis, believing they could be avoided if mathematicians limited themselves to a set of established axioms. By the late 1890s, Georg Cantor, the founder of modern set theory, had already realized his theory would lead to a contradiction (related to Cantor's theorem), which he communicated to Hilbert and Richard Dedekind by letter. Hilbert also formulated his own paradox, based on reasoning similar to Cantor's diagonal argument, and noted that it prompted Zermelo's version of Russell's paradox.

Informally, most sets are not members of themselves. A set is called "normal" if it is not a member of itself, and "abnormal" if it is. For instance, the set of all squares in a plane is not itself a square, so it is normal. The complementary set of everything that is not a square in the plane is itself not a square, so it is a member of itself and thus abnormal.

Now consider R, the set of all normal sets. If R were normal, it would belong to the set of all normal sets (itself), making it abnormal. If R were abnormal, it would not belong to that set, making it normal. Hence R is neither normal nor abnormal—this is Russell's paradox.

Formal presentation

Formally, naive set theory is a first-order theory with a binary predicate ∈, including the axiom of extensionality and the axiom schema of unrestricted comprehension: for any predicate P with x free, there exists a set y such that ∀x (x ∈ y ↔ P(x)). Substituting P(x) with x ∉ x yields ∃y ∀x (x ∈ y ↔ x ∉ x). By existential and universal instantiation, this leads to a contradiction, showing the theory is inconsistent.

Before Russell's paradox and similar ones like the Burali-Forti paradox, the common conception of a set was the "extensional concept," where no distinction existed between sets and proper classes. The existence of each element in a collection was considered sufficient for the existence of the set of those elements. These paradoxes demonstrated that some collections of objects do not form sets, even though all objects exist.

Because classical logic allows any proposition to be proved from a contradiction (the principle of explosion), contradictions like Russell's paradox are disastrous for an axiomatic set theory—they destroy the conventional meaning of truth and falsity. Since set theory was seen as the foundation for all mathematics, this paradox threatened mathematics as a whole, spurring extensive research around the turn of the 20th century to develop a consistent set theory. In 1908, Ernst Zermelo proposed an axiomatization that avoided the paradoxes by replacing unrestricted set comprehension with weaker existence axioms, such as his axiom of separation (Aussonderung).