nLab
Russell's paradox

Summary

Russell’s paradox is a paradox of naive material set theory that was first observed by the logician Bertrand Russell. If one assumes a naive, full axiom of comprehension, one can form the set

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

One then asks: is $R\in R$? If so, then $R\notin R$ by definition, whereas if not, then $R\in R$ by definition. Thus we have both $R\in R$ and $R\notin R$, a contradiction.

Related ideas

Russell’s paradox is closely related to the liar paradox (“this sentence is false”), to Gödel’s incompleteness theorem?, and to the halting problem? — all use diagonalization? to produce an object which talks about itself in a contradictory or close-to-contradictory way.

On the other hand, Cantor's paradox can be said to “beta-reduce” to Russell’s paradox when we apply Cantor's theorem to the supposed set of all sets.

Also related:

• Burali-Forti's paradox

Resolutions

There are a number of possible resolutions of Russell’s paradox.

• The “classical” solution, adopted in ZFC and thus by most mainstream mathematicians, is to restrict the axiom of comprehension so as to disallow the formation of the set $R$: one requires that the set being constructed be a subset of some already existing set. The restricted axiom is usually given a different name such as the axiom of separation.

• Essentially the same resolution is used in class theories such as NBG. Here we may write down the definition of $R$, but from $R\notin R$ we may conclude $R\in R$ only if we already know that $R$ is a set; the $x$ in the definition must be a set. So we have no contradiction, but only a proof that $R$ is a proper class.

• In the set theory called New Foundations?, the axiom of comprehension is restricted in a rather different way, by requiring the set-defining formula to be “stratifiable”. Since the formula $x\notin x$ is not stratifiable, the set $R$ cannot be formed. A similar (but more complicated) resolution was developed by Russell himself in his theory of ramified type?s.

• In most structural set theories, there is no need to artificially restrict the set-formation rules: if sets cannot be elements of other sets, then the “definition” of $R$ is just a type error. The same is true in other structural foundational systems such as (modern, non-Russellian) type theory. However, Russell’s paradox can be recreated in structural foundations with inconsistent universes by constructing pure sets within them.

• Alternatively, one can change the underlying logic. Passing to constructive logic does not help: although there is a seeming appeal to excluded middle (either $R\in R$ or $R\notin R$), without using excluded middle we can obtain that $R$ is both not in $R$ and not not in $R$, which is also a contradiction. However, passing to linear logic (or even affine logic?) does help: there is an unavoidable use of contraction in the paradox. There exist consistent linear set theories? with the full comprehension axiom, in which $R\in R$ implies $R\notin R$ and vice versa, but we can never get both $R\in R$ and $R\notin R$ at the same time to produce a paradox.

• Finally, and perhaps most radically, one can decide to allow contradictions, choosing to use a paraconsistent logic. There exist nontrivial paraconsistent set theories with full comprehension in which the set $R$ exists, being both a member of itself and not a member of itself.

References

Discussion of a paradox similar to Russell’s in type theory with W-types is in

• Thierry Coquand, The paradox of trees in Type Theory (1991) (web)

category: paradox