Russell's Paradox

Most sets do not contain themselves: the set of all teacups is not itself a teacup. But some sets might: the set of all abstract objects is itself an abstract object. Now consider the set R of all sets that do not contain themselves. If R contains itself, then R is a set that does contain itself — but R was defined as the set of sets that do not contain themselves, so R should not contain itself. If R does not contain itself, then R is a set that does not contain itself — and since R contains all such sets, R must contain itself. Either way we reach contradiction.

The paradox is not a curiosity but a foundational crisis. Frege's entire system of logic, on which his version of logicism rested, allowed unrestricted set formation: for any predicate, there is a set of all things satisfying it. Russell's paradox shows this principle is inconsistent. Frege received Russell's letter pointing this out as he was completing the second volume of his Grundgesetze; his response — "a man of science can hardly meet with anything more undesirable than to have the foundation give way just as the work is finished" — remains one of the most poignant sentences in the history of mathematics.

Russell's solution was the theory of types: a hierarchy of logical categories in which sets of one level can only contain members of the level below. A set of individuals is a type-1 set; a set of type-1 sets is a type-2 set; and so on. Cross-level membership — and in particular, self-membership — is ruled out as ill-formed rather than simply false. The paradox-generating question "does R contain itself?" becomes, on this account, a category mistake. The theory of types is technically intricate and has been criticised for its complexity and its apparent departure from "pure" logic, but it achieved its main goal: a consistent system powerful enough to express arithmetic.

Russell discovered the paradox in May 1901 and communicated it to Frege in a letter of June 16, 1902. The paradox and its resolution occupy Appendix B of The Principles of Mathematics (1903). The theory of types is developed more fully in Principia Mathematica (1910–13).