nLab
Russell's paradox

Context

Foundations

Type theory

natural deduction metalanguage, practical foundations

  1. type formation rule
  2. term introduction rule
  3. term elimination rule
  4. computation rule

type theory (dependent, intensional, observational type theory, homotopy type theory)

syntax object language

computational trinitarianism = propositions as types +programs as proofs +relation type theory/category theory

logiccategory theorytype theory
trueterminal object/(-2)-truncated objecth-level 0-type/unit type
falseinitial objectempty type
proposition(-1)-truncated objecth-proposition, mere proposition
proofgeneralized elementprogram
cut rulecomposition of classifying morphisms / pullback of display mapssubstitution
cut elimination for implicationcounit for hom-tensor adjunctionbeta reduction
introduction rule for implicationunit for hom-tensor adjunctioneta conversion
conjunctionproductproduct type
disjunctioncoproduct ((-1)-truncation of)sum type (bracket type of)
implicationinternal homfunction type
negationinternal hom into initial objectfunction type into empty type
universal quantificationdependent productdependent product type
existential quantificationdependent sum ((-1)-truncation of)dependent sum type (bracket type of)
equivalencepath space objectidentity type
equivalence classquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
completely presented setdiscrete object/0-truncated objecth-level 2-type/preset/h-set
setinternal 0-groupoidBishop set/setoid
universeobject classifiertype of types
modalityclosure operator, (idemponent) monadmodal type theory, monad (in computer science)
linear logic(symmetric, closed) monoidal categorylinear type theory/quantum computation
proof netstring diagramquantum circuit
(absence of) contraction rule(absence of) diagonalno-cloning theorem
synthetic mathematicsdomain specific embedded programming language

homotopy levels

semantics

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|xx}. R = \{ x | x \notin x \}.

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

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. See Cantor's paradox for explanation.

Also related:

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 RR: 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 RR, but from RRR \notin R we may conclude RRR \in R only if we already know that RR is a set; the xx in the definition must be a set. So we have no contradiction, but only a proof that RR 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 xxx\notin x is not stratifiable, the set RR 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 RR 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 RRR\in R or RRR\notin R), without using excluded middle we can obtain that RR is both not in RR and not not in RR, 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 RRR\in R implies RRR\notin R and vice versa, but we can never get both RRR\in R and RRR\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 RR 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

category: paradox

Revised on July 19, 2014 17:36:32 by Colin Zwanziger (174.63.87.107)