View source for Russell's paradox

{{Short description|Paradox in set theory}}
In [[Mathematical logic|mathematical logic]], '''Russell's paradox''' (also known as '''Russell's antinomy''') is a [[Paradoxes of set theory|set-theoretic paradox]] published by the {{wipe|United Kingdom}} [[Biography:Philosopher|philosopher]] and [[Biography:Mathematician|mathematician]] [[Biography:Bertrand Russell|Bertrand Russell]] in 1901.<ref>Russell, Bertrand, "Correspondence with Frege}. In Gottlob Frege ''Philosophical and Mathematical Correspondence''. Translated by Hans Kaal., University of Chicago Press,  Chicago, 1980.</ref><ref>Russell, Bertrand. ''[[The Principles of Mathematics]]''. 2d. ed. Reprint, New York: W. W. Norton & Company, 1996. (First published in 1903.)</ref> Russell's paradox shows that every [[Set theory|set theory]] that contains an unrestricted comprehension principle leads to contradictions.<ref>Irvine, A. D., H. Deutsch (2021). "Russell's Paradox". Stanford Encyclopedia of Philosophy (Spring 2021 Edition), E. N. Zalta (ed.), [https://plato.stanford.edu/entries/russell-paradox/]</ref> The paradox had already been discovered independently in 1899 by the German mathematician [[Biography:Ernst Zermelo|Ernst Zermelo]].<ref>Bernhard Rang, Wolfgang Thomas: Zermelo's Discovery of the "Russell Paradox", Historia Mathematica 8.</ref> However, Zermelo did not publish the idea, which remained known only to [[Biography:David Hilbert|David Hilbert]], [[Biography:Edmund Husserl|Edmund Husserl]], and other academics at the University of Göttingen. At the end of the 1890s, [[Biography:Georg Cantor|Georg Cantor]] – considered the founder of modern set theory – had already realized that his theory would lead to a contradiction, as he told Hilbert and [[Biography:Richard Dedekind|Richard Dedekind]] by letter.<ref>Walter Purkert, Hans J. Ilgauds: ''Vita Mathematica - Georg Cantor'', Birkhäuser, 1985, {{ISBN|3-764-31770-1}}</ref>

According to the unrestricted comprehension principle, for any sufficiently well-defined [[Property (mathematics)|property]], there is the [[Set (mathematics)|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. (This set is 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:
: <math>\text{Let } R = \{ x \mid x \not \in x \} \text{, then } R \in R \iff R \not \in R</math>

Russell also showed that a version of the paradox could be derived in the [[Axiomatic system|axiomatic system]] constructed by the German philosopher and mathematician [[Biography:Gottlob Frege|Gottlob Frege]], hence undermining Frege's attempt to reduce mathematics to logic and calling into question the [[Philosophy:Logicism|logicist programme]]. Two influential ways of avoiding the paradox were both proposed in 1908: Russell's own [[Type theory|type theory]] and the [[Zermelo set theory]]. In particular, Zermelo's axioms restricted the unlimited comprehension principle. With the additional contributions of [[Biography:Abraham Fraenkel|Abraham Fraenkel]], Zermelo set theory  developed into the now-standard [[Zermelo–Fraenkel set theory]] (commonly known as ZFC when including the [[Axiom of choice|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 [[Axiom schema of replacement#History|help of Thoralf Skolem]], turned out to be that of [[First-order logic|first-order logic]].<ref name="FraenkelBar-Hillel1973">{{cite book|author1=A.A. Fraenkel|author2=Y. Bar-Hillel|author3=A. Levy|title=Foundations of Set Theory|year=1973|publisher=Elsevier|isbn=978-0-08-088705-0|pages=156–157}}</ref>

== Informal presentation ==
Most sets commonly encountered are not members of themselves. Let us 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 [[Square|square]]s in a [[Plane (geometry)|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.

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 (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|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 (mathematical logic)|predicate]] <math>\in</math>, and that includes the [[Axiom of extensionality|axiom of extensionality]]:
: <math>\forall x \, \forall y \, ( \forall z \, (z \in x \iff z \in y) \implies x = y)</math>
and the axiom schema of unrestricted comprehension:
: <math> \exists y \forall x (x \in y \iff \varphi(x))</math>
for any formula <math>\varphi</math> with the variable {{mvar|x}} as a free variable inside <math>\varphi</math>. Substitute <math>x \notin x</math> for <math>\varphi(x)</math> to get
: <math> \exists y \forall x (x \in y \iff x \notin x)</math>

Then by [[Existential instantiation|existential instantiation]] (reusing the symbol <math>y</math>) and [[Universal instantiation|universal instantiation]] we have
: <math>y \in y \iff y \notin y ,</math>
a contradiction.  Therefore, this naive set theory is [[Consistency|inconsistent]].<ref>{{cite encyclopedia |title= Russell's Paradox|encyclopedia=The Stanford Encyclopedia of Philosophy |year= 2014 |editor-last= Zalta|editor-first= Edward N.|url=http://plato.stanford.edu/archives/win2014/entries/russell-paradox/|last1= Irvine|first1=Andrew David|last2= Deutsch|first2= Harry }}
</ref>

== 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:<ref>R. Bunn, [https://open.library.ubc.ca/media/stream/pdf/831/1.0100043/1 Infinite Sets and Numbers] (1967), pp.176–178. Ph.D dissertation, University of British Columbia</ref>

{{Blockquote|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 set, by examples of collections of objects that do not form sets, despite all said objects being existent.

== Set-theoretic responses ==
From the [[Philosophy:Principle of explosion|principle of explosion]] of [[Philosophy:Classical logic|classical logic]], ''any'' proposition can be proved from a [[Contradiction|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, [[Biography:Ernst Zermelo|Ernst Zermelo]] proposed an [[Axiomatic system|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|well-ordering theorem]].)<ref name="Maddy">P. Maddy, "[https://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf Believing the Axioms I]" (1988). Association for Symbolic Logic.</ref> Modifications to this axiomatic theory proposed in the 1920s by [[Biography:Abraham Fraenkel|Abraham Fraenkel]], [[Biography:Thoralf Skolem|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|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|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, notably in [[Von Neumann–Bernays–Gödel set theory|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 [[Philosophy:Higher-order logic|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. 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. (Once we have adopted an impredicative standpoint, abandoning the idea that classes are constructed, it is not unnatural to accept transfinite types.) 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 countable models (Skolem's paradox), but it enjoys some important advantages."<ref name="Ferreirós2008">{{cite book|author=José Ferreirós|title=Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics|year=2008|publisher=Springer|isbn=978-3-7643-8350-3|edition=2nd|at=§ Zermelo's cumulative hierarchy pp. 374-378}}</ref>

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 [[Biography:John von Neumann|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|empty set]] by transfinitely iterating the [[Power set|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:Philosophy of mathematics|philosophy of mathematics]].

Other solutions to Russell's paradox, with an underlying strategy closer to that of [[Type theory|type theory]], include Quine's [[Organization:New Foundations|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 ==
Russell discovered the paradox in May<ref>''The Autobiography of Bertrand Russell'', George Allen and Unwin Ltd., 1971, page 147: "At the end of the Lent Term [1901], I went back to Fernhurst, where I set to work to write out the logical deduction of mathematics which afterwards became ''Principia Mathematica''. I thought the work was nearly finished but ''in the month of May'' [emphasis added] I had an intellectual set-back […]. Cantor had a proof that there is no greatest number, and it seemed to me that the number of all the things in the world ought to be the greatest possible. Accordingly, I examined his proof with some minuteness, and endeavoured to apply it to the class of all the things there are. This led me to consider those classes which are not members of themselves, and to ask whether the class of such classes is or is not a member of itself. I found that either answer implies its contradictory".</ref> or June 1901.<ref name="auto">{{citation |url=https://books.google.com/books?id=Xg6QpedPpcsC&pg=PA350 |title=One hundred years of Russell's paradox |author=Godehard Link |page=350 |year=2004 |isbn=978-3-11-017438-0 |access-date=2016-02-22 }}</ref> 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".<ref>Russell 1920:136</ref> In a 1902 letter,<ref>{{citation |url=https://books.google.com/books?id=4ktC0UrG4V8C&pg=PA253 |page=253 |year=1997 |title=The Frege reader |isbn=978-0-631-19445-3 |author=Gottlob Frege, Michael Beaney |access-date=2016-02-22 }}. Also van Heijenoort 1967:124–125</ref> he announced the discovery to [[Biography:Gottlob Frege|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 (mathematics)|function]]:{{efn|In the following, p.&nbsp;17 refers to a page in the original ''Begriffsschrift'', and page 23 refers to the same page in van Heijenoort 1967}}{{efn|Remarkably, this letter was unpublished until van Heijenoort 1967—it appears with van Heijenoort's commentary at van Heijenoort 1967:124–125.}}

{{blockquote|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. Let '''w''' be the predicate: to be a predicate that cannot be predicated of itself. Can '''w''' be predicated of itself? From each answer its opposite follows. Therefore we must conclude that '''w''' 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 1903 ''[[The Principles of Mathematics]]'', where he repeated his first encounter with the paradox:<ref>Russell 1903:101</ref>

{{blockquote|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 his ''Grundgesetze der Arithmetik''.<ref>cf van Heijenoort's commentary before Frege's ''Letter to Russell'' in van Heijenoort 1964:126.</ref> 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,<ref>van Heijenoort's commentary, cf van Heijenoort 1967:126; Frege starts his analysis by this exceptionally honest comment : "Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished.  This was the position I was placed in  by a letter of Mr Bertrand Russell, just when the printing of this volume was nearing its completion" (Appendix of ''Grundgesetze der Arithmetik, vol. II'', in ''The Frege Reader'', p.&nbsp;279, translation by Michael Beaney</ref> and proposed a solution that Russell would endorse in his ''Principles of Mathematics'',<ref>cf van Heijenoort's commentary, cf van Heijenoort 1967:126. The added text reads as follows: "''Note''. The second volume of Gg., which appeared too late to be noticed in the Appendix, contains an interesting discussion of the contradiction (pp. 253–265), suggesting that the solution is to be found by denying that two [[Propositional function|propositional function]]s that determine equal classes must be equivalent. As it seems very likely that this is the true solution, the reader is strongly recommended to examine Frege's argument on the point" (Russell 1903:522); The abbreviation Gg. stands for Frege's ''Grundgezetze der Arithmetik''. Begriffsschriftlich abgeleitet. Vol. I. Jena, 1893. Vol. II. 1903.</ref> but was later considered by some to be unsatisfactory.<ref>Livio states that "While Frege did make some desperate attempts to remedy his axiom system, he was unsuccessful. The conclusion appeared to be disastrous&nbsp;..." Livio 2009:188. But van Heijenoort in his commentary before Frege's (1902) ''Letter to Russell'' describes Frege's proposed "way out" in some detail—the matter has to do with the " 'transformation of the generalization of an equality into an equality of courses-of-values. For Frege a function is something incomplete, 'unsaturated{{'"}}; this seems to contradict the contemporary notion of a "function in extension"; see Frege's wording at page 128: "Incidentally, it seems to me that the expression 'a predicate is predicated of itself' is not exact. ...Therefore I would prefer to say that 'a concept is predicated of its own extension' [etc]". But he waffles at the end of his suggestion that a function-as-concept-in-extension can be written as predicated of its function. van Heijenoort cites Quine: "For a late and thorough study of Frege's "way out", see ''Quine 1956''": "On Frege's way out", ''Mind 64'', 145–159; reprinted in ''Quine 1955b'': ''Appendix. Completeness of quantification theory. Loewenheim's theorem'', enclosed as a pamphlet with part of the third printing (1955) of ''Quine 1950'' and incorporated in the revised edition (1959), 253—260" (cf REFERENCES in van Heijenoort 1967:649)</ref>  For his part, Russell had his work at the printers and he added an appendix on the [[Type theory|doctrine of types]].<ref>Russell mentions this fact to Frege, cf van Heijenoort's commentary before Frege's (1902) ''Letter to Russell'' in van Heijenoort 1967:126</ref>

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")<ref>van Heijenoort's commentary before Zermelo (1908a) ''Investigations in the foundations of set theory'' I in van Heijenoort 1967:199</ref> laid claim to prior discovery of the [[Philosophy:Antinomy|antinomy]] in Cantor's naive set theory. He states: "And yet, even the elementary form that Russell<sup>9</sup> 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".<ref>van Heijenoort 1967:190–191. In the section before this he objects strenuously to the notion of [[Impredicativity|impredicativity]] as defined by Poincaré (and soon to be taken by Russell, too, in his 1908 ''Mathematical logic as based on the theory of types'' cf van Heijenoort 1967:150–182).</ref> Footnote 9 is where he stakes his claim:

{{blockquote|<sup>9</sup>''1903'', 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.<ref>Ernst Zermelo (1908) ''A new proof of the possibility of a well-ordering'' in van Heijenoort 1967:183–198. Livio 2009:191 reports that Zermelo "discovered Russell's paradox independently as early as 1900"; Livio in turn cites Ewald 1996 and van Heijenoort 1967 (cf Livio 2009:268).</ref>}}

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 [[Biography:Edmund Husserl|Edmund Husserl]].<ref>B. Rang and W. Thomas, "Zermelo's discovery of the 'Russell Paradox'", ''Historia Mathematica'', v. 8 n. 1, 1981, pp. 15–22. {{doi|10.1016/0315-0860(81)90002-1}}</ref>

In 1923, [[Biography:Ludwig Wittgenstein|Ludwig Wittgenstein]] proposed to "dispose" of Russell's paradox as follows:

<blockquote>
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 proposition '''F(F(fx))''', in which the outer function '''F''' and the inner function '''F''' must have different meanings, since the inner one has the form '''O(fx)''' and the outer one has the form '''Y(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 of '''F(Fu)''' we write '''(do) : F(Ou) . Ou = Fu'''. That disposes of Russell's paradox. (''[[Philosophy:Tractatus Logico-Philosophicus|Tractatus Logico-Philosophicus]]'', 3.333)
</blockquote>

Russell and [[Biography:Alfred North Whitehead|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|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, [[Biography:Kurt Gödel|Kurt Gödel]] in 1930–31 proved that while the logic of much of ''Principia Mathematica'', now known as first-order logic, is [[Gödel's completeness theorem|complete]], [[Peano axioms|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.<ref name="auto"/>

== Applied versions ==
{{Multiple issues|section=yes|
}}
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|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.

An easy refutation of the "layman's versions" such as the barber paradox seems to be that no such barber exists, or that the barber is not a man, and so can exist without paradox. 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|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 [[Philosophy:Grelling–Nelson paradox|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 (and ''cannot'') exist, it is impossible to say something similar about a meaningfully defined word.

One way that the paradox has been dramatised is as follows: 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. Now 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.

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.

== 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 {{angbr|V}}, that can be applied to its substantive form.

Form the sentence:
: The {{angbr|V}}er that {{angbr|V}}s all (and only those) who do not {{angbr|V}} themselves,

Sometimes the "all" is replaced by "all {{angbr|V}}ers".

An example would be "paint":
: The ''paint''er that ''paint''s all (and only those) that do not ''paint'' themselves.
or "elect"
: The ''elect''or ([[Group representation|representative]]), that ''elect''s all that do not ''elect'' themselves.

In the Season 8 episode of ''The 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.<ref>{{cite web |url=https://www.mprnews.org/story/2016/09/27/play-that-funky-music-no-1-40-years-ago |title=Play That Funky Music Was No. 1 40 Years Ago |website=Minnesota Public Radio |date=September 27, 2016 |access-date=January 30, 2022}}</ref>

Paradoxes that fall in this scheme include:
* [[Barber paradox|The barber with "shave"]].
* The original Russell's paradox with "contain": The container (Set) that contains all (containers) that do not contain themselves.
* The [[Philosophy:Grelling–Nelson paradox|Grelling–Nelson paradox]] with "describer": The describer (word) that describes all words, that do not describe themselves.
* [[Richard's paradox]] with "denote": The denoter (number) that denotes all denoters (numbers) that do not denote themselves. (In this paradox, all descriptions of numbers get an assigned number. The term "that denotes all denoters (numbers) that do not denote themselves" is here called ''Richardian''.)
* "I am lying.", namely the [[Philosophy:Liar paradox|liar paradox]] and [[Philosophy:Epimenides paradox|Epimenides paradox]], whose origins are ancient
* Russell–Myhill paradox

== Related paradoxes ==
* The [[Burali-Forti paradox]], about the [[Order type|order type]] of all well-orderings
* The [[Kleene–Rosser paradox]], showing that the original [[Lambda calculus|lambda calculus]] is inconsistent, by means of a self-negating statement
* [[Curry's paradox]] (named after [[Biography:Haskell Curry|Haskell Curry]]), which does not require [[Negation|negation]]
* The [[Interesting number paradox|smallest uninteresting integer]] paradox
* [[Girard's paradox]] in [[Type theory|type theory]]

== See also ==
* Basic Law V
* {{annotated link|Cantor's diagonal argument}}
* {{annotated link|Gödel's incompleteness theorems}}
* {{annotated link|Hilbert's first problem}}
* "On Denoting"
* {{annotated link|Paradoxes of set theory}}
* [[Philosophy:Quine's paradox|Quine's paradox]]
* [[Self-reference]]
* {{annotated link|Strange loop}}
* {{annotated link|Universal set}}

== Notes ==
{{notelist}}

== References ==
{{reflist}}

== Sources ==
{{refbegin}}
* {{citation |last=Potter |first=Michael |date=15 January 2004 |title=Set Theory and its Philosophy |publisher=Clarendon Press ([[Organization:Oxford University Press|Oxford University Press]]) |isbn=978-0-19-926973-0 }}
* {{citation |last=van Heijenoort |first=Jean |date=1967 |title=From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, (third printing 1976)|publisher=Harvard University Press|publication-place=Cambridge, Massachusetts|isbn=0-674-32449-8}}
* {{citation|last=Livio|first=Mario|author-link=Mario Livio|date=6 January 2009|title=Is God a Mathematician?|publisher=Simon & Schuster|publication-place=New York|isbn=978-0-7432-9405-8
}}
{{refend}}

==External links==
* {{cite web|last=Kaplan|first=Jeffrey|url=https://www.youtube.com/watch?v=ymGt7I4Yn3k|title=Russell's Paradox - a simple explanation of a profound problem|work=YouTube|year=2022|accessdate={{date|2023-11-25}}}}
* {{cite IEP |url-id=par-russ |title=Russell's Paradox}}
* {{cite SEP |url-id=russell-paradox |title=Russell's Paradox |first=Andrew David |last=Irvine |date=2016}}
* {{MathWorld |title=Russell's Antinomy |id=RussellsAntinomy }}
* {{cite web|url=https://www.cut-the-knot.org/selfreference/russell.shtml|title=Russell's Paradox|work=Cut-the-Knot|accessdate={{date|2023-11-25}}}}
* {{cite web|url=https://yurichev.com/news/20211216_Russell/ |title=Russell's (Barber) paradox explanation in Python|accessdate={{date|2023-11-25}}}}

{{Navboxes
|list =
{{Mathematical logic}}
}}

{{DEFAULTSORT:Russell's Paradox}}
[[Category:Paradoxes of naive set theory]]
[[Category:Self-referential paradoxes]]

{{Sourceattribution|Russell's paradox}}