|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-proposition, mere proposition|
|cut rule||composition of classifying morphisms / pullback of display maps||substitution|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator, (idemponent) monad||modal type theory, monad (in computer science)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
|synthetic mathematics||domain specific embedded programming language|
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
One then asks: is ? If so, then by definition, whereas if not, then by definition. Thus we have both and , 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.
There are a number of possible resolutions of Russell’s paradox.
Russell himself (1903,1908,1910) proposed the introduction of type theory as a solution e.g. in Principia Mathematica (1910) an intricate system of ramified types tracks the variables of propositional functions in order to prevent circular propositions. This is inspired by Poincaré’s ideas on impredicativity and can be viewed as a radical generalisation of Frege’s ontological distinction between an argument as a satured object and a function or concept as an unsaturated object.
The “classical” solution, adopted in ZFC and thus by the mathematical “mainstream”, is to restrict the axiom of comprehension so as to disallow the formation of the set : 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.
Another solution is to distinguish between sets and proper classes (= collections that are “too big” to be sets) as e.g. in NBG “set” theory.4 Here we may write down the definition of , but from we may conclude only if we already know that is a set; the in the definition must be a set. So we have no contradiction, but only a proof that 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 is not stratifiable, the set cannot be formed. This related to Russell’s ideas on ramified types.
In most structural set theories, the featurelessness of the elements of the structural sets secures the consistency of set formation. If sets cannot be elements of other sets, then the “definition” of 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 or ), without using excluded middle we can obtain that is both not in and not not in , 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 implies and vice versa, but we can never get both and 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 exists, being both a member of itself and not a member of itself.
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
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. ↩
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’. ↩