| ||
|---|---|---|
Inmathematical logic,Russell's paradox (also known asRussell's antinomy) is aset-theoretic paradox published by theBritishphilosopher andmathematician,Bertrand Russell, in 1901.[1][2] Russell's paradox shows that everyset theory that contains anunrestricted comprehension principle leads to contradictions.[3]
According to the unrestricted comprehension principle, for any sufficiently well-definedproperty, there is theset of all and only the objects that have that property. LetR be the set of all sets that are not members of themselves. (This set is sometimes called "the Russell set".) IfR 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 theaxiomatic system constructed by the German philosopher and mathematicianGottlob Frege, hence undermining Frege's attempt to reduce mathematics to logic and calling into question thelogicist programme. Two influential ways of avoiding the paradox were both proposed in 1908: Russell's owntype theory and theZermelo set theory. In particular, Zermelo's axioms restricted the unlimited comprehension principle. With the additional contributions ofAbraham Fraenkel, Zermelo set theory developed into the standardZermelo–Fraenkel set theory (commonly known as ZFC when including theaxiom 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 thehelp of Thoralf Skolem, turned out to be that offirst-order logic.[4]
The paradox had already been discovered independently in 1899 by the German mathematicianErnst Zermelo.[5] However, Zermelo did not publish the idea, which remained known only toDavid Hilbert,Edmund Husserl, and other academics at theUniversity of Göttingen. 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, as he told Hilbert andRichard Dedekind by letter.[6]
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 allsquares in aplane. 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 isnot 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 whetherR is normal or abnormal. IfR were normal, it would be contained in the set of all normal sets (itself), and therefore be abnormal; on the other hand ifR were abnormal, it would not be contained in the set of all normal sets (itself), and therefore be normal. This leads to the conclusion thatR is neither normal nor abnormal: Russell's paradox.
The term "naive set theory" is used in various ways. In one usage, naive set theory is a formal theory, that is formulated in afirst-order language with a binary non-logicalpredicate, and that includes theaxiom of extensionality:
and the axiom schema ofunrestricted comprehension:
for any predicate withx as a free variable inside. Substitute for to get
Then byexistential instantiation (reusing the symbol) anduniversal instantiation we have
a contradiction. Therefore, this naive set theory isinconsistent.[7]
Prior to Russell's paradox (and to other similar paradoxes discovered around the time, such as theBurali-Forti paradox), a common conception of the idea of set was the "extensional concept of set", as recounted by von Neumann and Morgenstern:[8]
A set is an arbitrary collection of objects, absolutely no restriction being placed on the nature and number of these objects, the elements of the set in question. The elements constitute and determine the set as such, without any ordering or relationship of any kind between them.
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.
From theprinciple of explosion ofclassical logic,any proposition can be proved from acontradiction. 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 anaxiomatization of set theory that avoided the paradoxes of naive set theory by replacing arbitrary set comprehension with weaker existence axioms, such as hisaxiom of separation (Aussonderung). (Avoiding paradox was not Zermelo's original intention, but instead to document which assumptions he used in proving thewell-ordering theorem.)[9] Modifications to this axiomatic theory proposed in the 1920s byAbraham Fraenkel,Thoralf Skolem, and by Zermelo himself resulted in the axiomatic set theory calledZFC. This theory became widely accepted once Zermelo'saxiom of choice ceased to be controversial, and ZFC has remained the canonicalaxiomatic 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 setX, any subset ofX definable usingfirst-order logic exists. The objectR defined by Russell's paradox above cannot be constructed as a subset of any setX, and is therefore not a set in ZFC. In some extensions of ZFC, likevon Neumann–Bernays–Gödel set theory, objects likeR are calledproper classes.
ZFC is silent about types, although thecumulative 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 'entirelyarbitrary' [ganzbeliebig]"; the modern interpretation given to this statement is that Zermelo wanted to includehigher-order quantification in order to avoidSkolem's paradox. Around 1930, Zermelo also introduced (apparently independently of von Neumann), theaxiom 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."[10]
In ZFC, given a setA, it is possible to define a setB that consists of exactly the sets inA that are not members of themselves.B cannot be inA 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, especiallyJohn von Neumann, the structure of what some see as the "natural" objects described by ZFC eventually became clear: they are the elements of thevon Neumann universe,V, built up from theempty set bytransfinitely iterating thepower 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 ofV. Whether it isappropriate to think of sets in this way is a point of contention among the rival points of view on thephilosophy of mathematics.
Other solutions to Russell's paradox, with an underlying strategy closer to that oftype theory, includeQuine'sNew Foundations andScott–Potter set theory. Yet another approach is to define multiple membership relation with appropriately modified comprehension scheme, as in theDouble extension set theory.
Russell discovered the paradox in May[11] or June 1901.[12] By his own account in his 1919Introduction to Mathematical Philosophy, he "attempted to discover some flaw in Cantor's proof that there is no greatest cardinal".[13] In a 1902 letter,[14] he announced the discovery toGottlob Frege of the paradox in Frege's 1879Begriffsschrift and framed the problem in terms of both logic and set theory, and in particular in terms of Frege's definition offunction:[a][b]
There is just one point where I have encountered a difficulty. You state (p. 17 [p. 23 above]) that a function too, can act as the indeterminate element. This I formerly believed, but now this view seems doubtful to me because of the following contradiction. Letw be the predicate: to be a predicate that cannot be predicated of itself. Canw be predicated of itself? From each answer its opposite follows. Therefore we must conclude thatw is not a predicate. Likewise there is no class (as a totality) of those classes which, each taken as a totality, do not belong to themselves. From this I conclude that under certain circumstances a definable collection [Menge] does not form a totality.
Russell would go on to cover it at length in his 1903The Principles of Mathematics, where he repeated his first encounter with the paradox:[15]
Before taking leave of fundamental questions, it is necessary to examine more in detail the singular contradiction, already mentioned, with regard to predicates not predicable of themselves. ... I may mention that I was led to it in the endeavour to reconcile Cantor's proof....
Russell wrote to Frege about the paradox just as Frege was preparing the second volume of hisGrundgesetze der Arithmetik.[16] 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,[17] and proposed a solution that Russell would endorse in hisPrinciples of Mathematics,[18] but was later considered by some to be unsatisfactory.[19] For his part, Russell had his work at the printers and he added an appendix on thedoctrine of types.[20]
Ernst Zermelo in his (1908)A new proof of the possibility of a well-ordering (published at the same time he published "the first axiomatic set theory")[21] laid claim to prior discovery of theantinomy 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 [J. König, Jourdain, F. Bernstein] 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".[22] Footnote 9 is where he stakes his claim:
91903, pp. 366–368. I had, however, discovered this antinomy myself, independently of Russell, and had communicated it prior to 1903 to Professor Hilbert among others.[23]
Frege sent a copy of hisGrundgesetze 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 theNachlass ofEdmund Husserl.[24]
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(fx) could be its own argument: in that case there would be a propositionF(F(fx)), in which the outer functionF and the inner functionF must have different meanings, since the inner one has the formO(fx) and the outer one has the formY(O(fx)). Only the letter 'F' is common to the two functions, but the letter by itself signifies nothing. This immediately becomes clear if instead ofF(Fu) we write(do) : F(Ou) . Ou = Fu. That disposes of Russell's paradox. (Tractatus Logico-Philosophicus, 3.333)
Russell andAlfred North Whitehead wrote their three-volumePrincipia Mathematica hoping to achieve what Frege had been unable to do. They sought to banish the paradoxes ofnaive 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. WhilePrincipia Mathematica avoided the known paradoxes and allows the derivation of a great deal of mathematics, its system gave rise to new problems.
In any case,Kurt Gödel in 1930–31 proved that while the logic of much ofPrincipia Mathematica, later known as first-order logic, iscomplete,Peano arithmetic is necessarily incomplete if it isconsistent. This is very widely—though not universally—regarded as having shown thelogicist 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.[12]
 | This section has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) (Learn how and when to remove this message)
|
Some versions of this paradox are closer to real-life and may be easier to understand for non-logicians. For example, thebarber paradox supposes a male 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 shaves himself or not, a similar paradox begins to emerge.[25]
An exception may be theGrelling–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 (andcannot) exist, it is impossible to say something similar about a meaningfully defined word.
One way that the paradox has been dramatised is: suppose that every public library has to compile a catalogue of all its books. Since the catalogue is itself one of the library's books, some librarians include it in the catalogue for completeness; while others leave it out as it being one of the library's books is self evident. Next, imagine that all these catalogues are sent to the national library. Some of them include themselves in their listings, others do not. The national librarian compiles two master catalogues—one of all the catalogues that list themselves, and one of all those that do not.[26]
The question is: should these master catalogues list themselves? The 'catalogue of all catalogues that list themselves' is no problem. If the librarian does not include it in its own listing, it remains a true catalogue of those catalogues that do include themselves. If he does include it, it remains a true catalogue of those that list themselves. However, just as the librarian cannot go wrong with the first master catalogue, he is doomed to fail with the second. When it comes to the 'catalogue of all catalogues that do not list themselves', the librarian cannot include it in its own listing, because then it would include itself, and so belong in the other catalogue, that of catalogues that do include themselves. However, if the librarian leaves it out, the catalogue is incomplete. Either way, it can never be a true master catalogue of catalogues that do not list themselves.[26]
As illustrated above for the barber paradox, Russell's paradox is not hard to extend. Take:
Form the sentence:
Sometimes the "all" is replaced by "all⟨V⟩ers".
An example would be "paint":
or "elect"
In theSeason 8 episode ofThe Big Bang Theory, "The Skywalker Intrusion",Sheldon Cooper analyzes the song "Play That Funky Music", concluding that the lyrics present a musical example of Russell's Paradox.[27]
Paradoxes that fall in this scheme include:
