Russell's paradox
In the foundations of mathematics, Russell's paradox, discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naïve set theory created by Georg Cantor led to a contradiction. The same paradox had been discovered in 1899 by Ernst Zermelo but he did not publish the idea, which remained known only to David Hilbert, Edmund Husserl, and other members of the University of Göttingen. At the end of the 1890s Cantor himself had already realized that his definition would lead to a contradiction, which he told Hilbert and Richard Dedekind by letter.
According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves. This contradiction is Russell's paradox. Symbolically:
In 1908, two ways of avoiding the paradox were proposed, Russell's type theory and the Zermelo set theory. Zermelo's axioms went well beyond Gottlob Frege's axioms of extensionality and unlimited set abstraction; as the first constructed axiomatic set theory, it evolved into the now-standard Zermelo–Fraenkel set theory. The essential difference between Russell's and Zermelo's solution to the paradox is that Zermelo altered the axioms of set theory while preserving the logical language in which they are expressed, while Russell altered the logical language itself. The language of ZFC, with the help of Thoralf Skolem, turned out to be first-order logic.
Informal presentation
Most sets commonly encountered are not members of themselves. For example, the set of all squares in the plane. This set is not itself a square in the plane, thus it is not a member of itself. Let us call a set "normal" if it is not a member of itself, and "abnormal" if it is a member of itself. The set of squares in the plane is 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 should be one of its own members and is therefore abnormal.Now we 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, and therefore be abnormal; on the other hand if R were abnormal, it would not be contained in the set of all normal sets, and therefore be normal. This leads to the conclusion that R is neither normal nor abnormal: Russell's paradox.
Formal presentation
Define Naive Set Theory as the theory of predicate logic with a binary predicate and the following axiom schema of unrestricted comprehension:for any formula with only the variable x free.
Substitute for. Then by existential instantiation and universal instantiation we have
a contradiction. Therefore, NST is inconsistent.
Set-theoretic responses
From the principle of explosion in 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 theorem can be proven 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. This motivated a great deal of research around the turn of the 20th century to develop a consistent 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. 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 present 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 discussed above cannot be constructed in this fashion, and is therefore not a ZFC set. In some extensions of ZFC, 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 used for separating off subsets, as well as the replacement functions, can be 'entirely arbitrary' ;" 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, the axiom of foundation, thus—as Ferreirós observes— "by forbidding 'circular' and 'ungrounded' sets, it incorporated one of the crucial motivations of TT —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 offered by Gödel and Tarski. One can describe the cumulative hierarchy into which Zermelo developed his models as the universe of a cumulative TT in which transfinite types are allowed. Thus, simple TT and ZFC could now 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 denumerable models, 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 now 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 resolutions to Russell's paradox, more in the spirit of type theory, include the axiomatic set theories New Foundations and Scott-Potter set theory.
History
Russell discovered the paradox in May or June 1901. By his own account in his 1919 Introduction to Mathematical Philosophy, he "attempted to discover some flaw in Cantor's proof that there is no greatest cardinal". In a 1902 letter, he announced the discovery to Gottlob Frege of the paradox in Frege's 1879 Begriffsschrift and framed the problem in terms of both logic and set theory, and in particular in terms of Frege's definition of function:Russell would go on to cover it at length in his 1903 The Principles of Mathematics, where he repeated his first encounter with the paradox:
Russell wrote to Frege about the paradox just as Frege was preparing the second volume of his Grundgesetze der Arithmetik. Frege responded to Russell very quickly; his letter dated 22 June 1902 appeared, with van Heijenoort's commentary in Heijenoort 1967:126–127. Frege then wrote an appendix admitting to the paradox, and proposed a solution that Russell would endorse in his Principles of Mathematics, but was later considered by some to be unsatisfactory. For his part, Russell had his work at the printers and he added an appendix on the doctrine of types.
Ernst Zermelo in his A new proof of the possibility of a well-ordering laid claim to prior discovery of the antinomy in Cantor's naive set theory. He states: "And yet, even the elementary form that Russell9 gave to the set-theoretic antinomies could have persuaded them that the solution of these difficulties is not to be sought in the surrender of well-ordering but only in a suitable restriction of the notion of set". Footnote 9 is where he stakes his claim:
Frege sent a copy of his Grundgesetze der Arithmetik to Hilbert; as noted above, Frege's last volume mentioned the paradox that Russell had communicated to Frege. After receiving Frege's last volume, on 7 November 1903, Hilbert wrote a letter to Frege in which he said, referring to Russell's paradox, "I believe Dr. Zermelo discovered it three or four years ago". A written account of Zermelo's actual argument was discovered in the Nachlass of Edmund Husserl.
In 1923, Ludwig Wittgenstein proposed to "dispose" of Russell's paradox as follows:
The reason why a function cannot be its own argument is that the sign for a function already contains the prototype of its argument, and it
cannot contain itself. For let us suppose that the function F could be its own argument: in that case there would be a proposition F, in which the outer function F and the inner function F must have different meanings, since the inner one has the form O and the outer one has the form Y. Only the letter 'F' is common to the two functions, but the letter by itself signifies nothing. This immediately becomes clear if instead of F we write : F. Ou = Fu. That disposes of Russell's paradox.
Russell and Alfred North Whitehead wrote their three-volume Principia Mathematica hoping to achieve what Frege had been unable to do. They sought to banish the paradoxes of naive set theory by employing a theory of types they devised for this purpose. While they succeeded in grounding arithmetic in a fashion, it is not at all evident that they did so by purely logical means. While Principia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, its system gave rise to new problems.
In any event, Kurt Gödel in 1930–31 proved that while the logic of much of Principia Mathematica, now known as first-order logic, is complete, Peano arithmetic is necessarily incomplete if it is consistent. This is very widely—though not universally—regarded as having shown the logicist program of Frege to be impossible to complete.
In 2001 A Centenary International Conference celebrating the first hundred years of Russell's paradox was held in Munich and its proceedings have been published.
Applied versions
There are some versions of this paradox that are closer to real-life situations and may be easier to understand for non-logicians. For example, the barber paradox supposes a barber who shaves all men who do not shave themselves and only men who do not shave themselves. When one thinks about whether the barber should shave himself or not, the paradox begins to emerge.As another example, consider five lists of encyclopedia entries within the same encyclopedia:
List of articles about people:
| List of articles starting with the letter L:
| List of articles about places:
| List of articles about Japan: | List of all lists that do not contain themselves:
|
While appealing, these layman's versions of the paradox share a drawback: an easy refutation of the barber paradox seems to be that such a barber does not exist, or that the barber has alopecia and therefore doesn't shave. The whole point of Russell's paradox is that the answer "such a set does not exist" means the definition of the notion of set within a given theory is unsatisfactory. Note the difference between the statements "such a set does not exist" and "it is an empty set". It is like the difference between saying "There is no bucket" and saying "The bucket is empty".
A notable exception to the above may be the Grelling–Nelson paradox, in which words and meaning are the elements of the scenario rather than people and hair-cutting. Though it is easy to refute the barber's paradox by saying that such a barber does not exist, it is impossible to say something similar about a meaningfully defined word.
One way that the paradox has been dramatised is as follows:
Applications and related topics
Russell-like paradoxes
As illustrated above for the barber paradox, Russell's paradox is not hard to extend. Take:- A transitive verb
, that can be applied to its substantive form.
Sometimes the "all" is replaced by "all
An example would be "paint":
or "elect"
Paradoxes that fall in this scheme include:
- The barber with "shave".
- The original Russell's paradox with "contain": The container that contains all that don't contain themselves.
- The Grelling–Nelson paradox with "describer": The describer that describes all words, that don't describe themselves.
- Richard's paradox with "denote": The denoter that denotes all denoters that don't denote themselves.
- "I am lying.", namely the liar paradox and Epimenides paradox, whose origins are ancient
- Russell–Myhill paradox
Related paradoxes
- The Kleene–Rosser paradox, showing that the original lambda calculus is inconsistent, by means of a self-negating statement
- Curry's paradox, which does not require negation
- The smallest uninteresting integer paradox
- Girard's paradox in type theory