Russell's Paradox

Idea

Russell’s paradox is the contradiction that arises in naive set theory from the unrestricted comprehension scheme. It shows that not every predicate can determine a set.

The paradox is one of the main reasons for the development of axiomatic set theories such as ZF, which only allows for a restricted comprehension.

Statement

In naive set theory, one assumes that for any predicate $P$, there is a set

$$\{x\mid P(x)\}$$

consisting of exactly those objects satisfying $P$.

Now consider the predicate

$$P(x)\equiv x\notin x.$$

By comprehension, this determines a set

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

The question is whether $R\in R$.

• If $R\in R$, then by the definition of $R$ we must have $R\notin R$.
• If $R\notin R$, then again by the definition of $R$ we must have $R\in R$.

Thus

$$R\in R⟺R\notin R,$$

which is a contradiction.

Significance

Russell’s paradox shows that unrestricted comprehension is inconsistent. In other words, naive set theory cannot serve as a consistent foundation for mathematics.

Modern axiomatic set theories avoid the paradox by restricting set formation. In ZF, one does not allow arbitrary comprehension, but only separation, where a subset may be carved out from an already existing set.

Type-theoretic rendering

Informally, unrestricted comprehension may be written in type-theoretic syntax as follows: ¹

$$\frac{P:\mathcal{U}\to \mathrm{Prop}}{\{x\mid P(x)\}\mathbf{set}}\frac{P:\mathcal{U}\to \mathrm{Prop}a\mathbf{set}P(a)}{a\in \{x\mid P(x)\}}\frac{P:\mathcal{U}\to \mathrm{Prop}a\mathbf{set}a\in \{x\mid P(x)\}}{P(a)}$$

Russell’s paradox arises by instantiating this with the predicate $x\notin x$.

History

The paradox was discovered by Bertrand Russell in the early 20th century and showed that systems based on unrestricted comprehension, such as Frege’s logical framework, were inconsistent.

It became one of the central motivations for later axiomatic formulations of set theory.

Footnotes

1. This is only an informal rendering, assuming a suitable logical basis. ↩