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
logical 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/path type
equivalence classquotientquotient type
inductioncolimitinductive type, W-type, M-type
higher inductionhigher colimithigher inductive type
-0-truncated higher colimitquotient inductive type
coinductionlimitcoinductive 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, (idempotent) 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

Idea

Russell’s paradox is a famous paradox of set theory1 that was observed around 1902 by Ernst Zermelo2 and, independently, by the logician Bertrand Russell. The paradox received instantly wide attention as it lead to a contradiction in Frege’s monumental “Foundations of Arithmetic” (1893/1903) whose second volume was just about to go to print when Frege was informed about the inconsistency by Russell.

The paradox entangles a concept with its own extension in a vicious circle. The attempt to overcome this circularity in set formation had a huge impact on subsequent forms of axiomatic set theory and in the aftermath mathematical logic became heavily focussed on consistency proofs for fully specified formal theories: the paradoxes triggered a shift in the foundation of mathematics away from the mathematics to the foundation itself.

Doch zur Sache selbst! Herr Russell hat einen Widerspruch aufgefunden, der nun dargelegt werden mag.3

Statement

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 classical liar paradox (“this sentence is false”), to Gödel’s incompleteness theorem, and to the halting problem — all use a diagonalization argument 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.

References

Zermelo’s observation which is mentioned in a footnote of his 1908 paper on the well-ordering theorem is analyzed in

Russell indicated the contradiction leading to the inconsistency of G. Frege’s system of “Grundgesetze der Arithmetik” in a famous letter to the latter on June 16th 1902 which together with Frege’s reply is reprinted pp.124-128 in

For an account of Russell’s encounter with the paradox:

The first published account is presumably in the appendix of

Russell discusses the paradox extensively in chapter X of

The influence of Poincaré‘s views shows in

See also

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

category: paradox

  1. naive material set theory that is!

  2. Zermelo was apparently led to the paradox by considering a purported proof of Ernst Schröder in his Algebra der Logik (1890) that Boole’s concept of a universal class 1 was contradictory. Interestingly, the solution suggested by Schröder is reminiscent of type theory or even nested universes where a universal class 1 recurs at each level.

  3. Frege (1903, p.253).

  4. This solution proposed by J. von Neumann in the 1920s can be viewed as related to ideas of G. Cantor. The latter knew about similar phenomena concerning “the set of all sets” (in fact, Russell hit upon the paradox in a reflection on Cantor’s proof of the inexistence of a largest cardinal number), and had already pointed out in 1885 in a review of Frege’s “Grundlagen der Arithmetik” that not every concept has an extension. Therefore Cantor proposed in letters to Dedekind and Jourdain to differentiate between ‘consistent multiplicities’ (“compossible” multiplicities one could say) where things can coexist or compose to a consistent whole - ‘ensemble’ (fr.) which correspond to sets in the usual sense and, as completed collections, can in turn be elements in other sets, from ‘inconsistent multiplicities’ whose elements cannot consistently completed to a whole and cannot be member of other collections due to this lack of ‘unity’.