In mathematical logic, Russell's paradox (also known as Russell's antinomy) is a set-theoretic paradox published by the British philosopher and mathematician, Bertrand Russell, in 1901.Russell, Bertrand, "Correspondence with Frege}. In Gottlob Frege Philosophical and Mathematical Correspondence. Translated by Hans Kaal., University of Chicago Press, Chicago, 1980.Russell, Bertrand. The Principles of Mathematics. 2d. ed. Reprint, New York: W. W. Norton & Company, 1996. (First published in 1903.) Russell's paradox shows that every set theory that contains an unrestricted comprehension principle leads to contradictions.Irvine, A. D., H. Deutsch (2021). "Russell's Paradox". Stanford Encyclopedia of Philosophy (Spring 2021 Edition), E. N. Zalta (ed.),
According to the unrestricted comprehension principle, for any sufficiently well-defined property, there is the set of all and only the objects that have that property. Let R be the set of all sets that are not members of themselves (sometimes called "the Russell set"). If R is not a member of itself, then its definition entails that it is a member of itself; yet, if it is a member of itself, then it is not a member of itself, since it is the set of all sets that are not members of themselves. The resulting contradiction is Russell's paradox. In symbols:
Russell also showed that a version of the paradox could be derived in the axiomatic system constructed by the German philosopher and mathematician Gottlob Frege, hence undermining Frege's attempt to reduce mathematics to logic and calling into question the logicist programme. Two influential ways of avoiding the paradox were both proposed in 1908: Russell's own type theory and the Zermelo set theory. In particular, Zermelo's axioms restricted the unlimited comprehension principle. With the additional contributions of Abraham Fraenkel, Zermelo set theory developed into the standard Zermelo–Fraenkel set theory (commonly known as ZFC when including the axiom of choice). The main difference between Russell's and Zermelo's solution to the paradox is that Zermelo modified the axioms of set theory while maintaining a standard logical language, while Russell modified the logical language itself. The language of ZFC, with the help of Thoralf Skolem, turned out to be that of first-order logic.
The paradox had already been discovered independently by the German mathematician Ernst Zermelo by 1902, and possibly as early as 1899. However, Zermelo did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other academics at the University of Göttingen. Moreover, Zermelo did not regard the emergence of the paradoxes so much as a crisis as he believed that they could be avoided if mathematicians confine themselves to a limited number of established principles (axioms). At the end of the 1890s, Georg Cantor – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction (to Cantor's theorem), as he told Hilbert and Richard Dedekind by letter. Hilbert also formulated his own paradox, which relied on reasoning similar to Cantor's diagonal argument. According to Hilbert, it even initiated Ernst Zermelo's version of Russell's paradox.
Informal presentation Most sets commonly encountered are not members of themselves. Call a set "normal" if it is not a member of itself, and "abnormal" if it is a member of itself. Clearly every set must be either normal or abnormal. For example, consider the set of all squares in a plane. This set is not itself a square in the plane, thus it is not a member of itself and is therefore normal. In contrast, the complementary set that contains everything which is not a square in the plane is itself not a square in the plane, and so it is one of its own members and is therefore abnormal.
Consider the set of all normal sets, R, and try to determine whether R is normal or abnormal. If R were normal, it would be contained in the set of all normal sets (itself), and therefore be abnormal; on the other hand if R were abnormal, it would not be contained in the set of all normal sets (itself), and therefore be normal. This leads to the conclusion that R is neither normal nor abnormal: Russell's paradox.
Formal presentation The term "naive set theory" is used in various ways. In one usage, naive set theory is a formal theory, that is formulated in a first-order language with a binary non-logical predicate , and that includes the axiom of extensionality:
and the axiom schema of unrestricted comprehension:
for any predicate with as a free variable inside . Substitute for to get
Then by existential instantiation (reusing the symbol ) and universal instantiation we have
a contradiction. Therefore, this naive set theory is inconsistent.
Philosophical implications Prior to Russell's paradox (and to other similar paradoxes discovered around the time, such as the Burali-Forti paradox), a common conception of the idea of set was the "extensional concept of set", as recounted by von Neumann and Morgenstern:R. Bunn, Infinite Sets and Numbers (1967), pp.176–178. Ph.D dissertation, University of British Columbia
In particular, there was no distinction between sets and proper classes as collections of objects. Additionally, the existence of each of the elements of a collection was seen as sufficient for the existence of the set of said elements. However, paradoxes such as Russell's and Burali-Forti's showed the impossibility of this conception of a set, by examples of collections of objects that do not form sets, despite all said objects being existent.
Set-theoretic responses From the principle of explosion of classical logic, any proposition can be proved from a contradiction. Therefore, the presence of contradictions like Russell's paradox in an axiomatic set theory is disastrous; since if any formula can be proved true it destroys the conventional meaning of truth and falsity. Further, since set theory was seen as the basis for an axiomatic development of all other branches of mathematics, Russell's paradox threatened the foundations of mathematics as a whole. This motivated a great deal of research around the turn of the 20th century to develop a consistent (contradiction-free) set theory.
In 1908, Ernst Zermelo proposed an axiomatization of set theory that avoided the paradoxes of naive set theory by replacing arbitrary set comprehension with weaker existence axioms, such as his axiom of separation (Aussonderung). (Avoiding paradox was not Zermelo's original intention, but instead to document which assumptions he used in proving the well-ordering theorem.)P. Maddy, "Believing the Axioms I" (1988). Association for Symbolic Logic. Modifications to this axiomatic theory proposed in the 1920s by Abraham Fraenkel, Thoralf Skolem, and by Zermelo himself resulted in the axiomatic set theory called ZFC. This theory became widely accepted once Zermelo's axiom of choice ceased to be controversial, and ZFC has remained the canonical axiomatic set theory down to the modern day.
ZFC does not assume that, for every property, there is a set of all things satisfying that property. Rather, it asserts that given any set X, any subset of X definable using first-order logic exists. The object R defined by Russell's paradox above cannot be constructed as a subset of any set X, and is therefore not a set in ZFC. In some extensions of ZFC, like von Neumann–Bernays–Gödel set theory, objects like R are called proper classes.
ZFC is silent about types, although the cumulative hierarchy has a notion of layers that resemble types. Zermelo himself never accepted Skolem's formulation of ZFC using the language of first-order logic. As José Ferreirós notes, Zermelo insisted instead that "propositional functions (conditions or predicates) used for separating off subsets, as well as the replacement functions, can be 'entirely arbitrary [ganz beliebig]"; the modern interpretation given to this statement is that Zermelo wanted to include higher-order quantification in order to avoid Skolem's paradox. Around 1930, Zermelo also introduced (apparently independently of von Neumann), the axiom of foundation, thus—as Ferreirós observes—"by forbidding 'circular' and 'ungrounded' sets, it [ZFC] incorporated one of the crucial motivations of TT [type theory]—the principle of the types of arguments". This 2nd order ZFC preferred by Zermelo, including axiom of foundation, allowed a rich cumulative hierarchy. Ferreirós writes that "Zermelo's 'layers' are essentially the same as the types in the contemporary versions of simple TT [type theory] offered by Gödel and Tarski. The cumulative hierarchy into which Zermelo developed his models can be described as the universe of a cumulative TT in which transfinite types are allowed. (Once an impredicative standpoint is adopted, abandoning the idea that classes are constructed, it is natural to accept transfinite types.) Thus, simple TT and ZFC could be regarded as systems that 'talk' essentially about the same intended objects. The main difference is that TT relies on a strong higher-order logic, while Zermelo employed second-order logic, and ZFC can also be given a first-order formulation. The first-order 'description' of the cumulative hierarchy is much weaker, as is shown by the existence of countable models (Skolem's paradox), but it enjoys some important advantages."
In ZFC, given a set A, it is possible to define a set B that consists of exactly the sets in A that are not members of themselves. B cannot be in A by the same reasoning in Russell's Paradox. This variation of Russell's paradox shows that no set contains everything.
Through the work of Zermelo and others, especially John von Neumann, the structure of what some see as the "natural" objects described by ZFC eventually became clear: they are the elements of the von Neumann universe, V, built up from the empty set by transfinitely iterating the power set operation. It is thus possible again to reason about sets in a non-axiomatic fashion without running afoul of Russell's paradox, namely by reasoning about the elements of V. Whether it is appropriate to think of sets in this way is a point of contention among the rival points of view on the philosophy of mathematics.
Other solutions to Russell's paradox, with an underlying strategy closer to that of type theory, include Quine's New Foundations and Scott–Potter set theory. Yet another approach is to define multiple membership relation with appropriately modified comprehension scheme, as in the Double extension set theory.
History