GetWiki
Russell's paradox
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
Russell's paradox
please note:
 the content below is remote from Wikipedia
 it has been imported raw for GetWiki
{{short descriptionParadox in the foundations of mathematics}} the content below is remote from Wikipedia
 it has been imported raw for GetWiki
factoids  

text{Let } R = { x mid x not in x } text{, then } R in R iff R not in R
In 1908, two ways of avoiding the paradox were proposed, Russell's type theory and the Zermelo set theory, the first constructed axiomatic set theory. Zermelo's axioms went well beyond Gottlob Frege's axioms of extensionality and unlimited set abstraction, and evolved into the nowstandard Zermeloâ€“Fraenkel set theory (ZFC). 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 (the language of ZFC, with the help of Thoralf Skolem, turned out to be firstorder logic) while Russell altered the logical language itself.BOOK, A.A. Fraenkel, Y. BarHillel, A. Levy, Foundations of Set Theory, 1973, Elsevier, 9780080887050, 156â€“157, Informal presentation
Let us call a set "abnormal" if it is a member of itself, and "normal" otherwise. For example, take the set of all squares in the plane. That set is not itself a square in the plane, and therefore is not a member of the set of all squares in the plane. So it is "normal". On the other hand, if we take the complementary set that contains all non(squares in the plane),{{efnAs opposed to (nonsquares) in the plane, which is the complement with the universe of "things in the plane".}} that set is itself not a square in the plane and so should be one of its own members as it is a non(square in the plane). It is "abnormal".Now we consider the set of all normal sets, R. Determining whether R is normal or abnormal is impossible: if R were a normal set, it would be contained in the set of normal sets (itself), and therefore be abnormal; and 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
Define Naive Set Theory (NST) as the theory of predicate logic with a binary predicate in and the following axiom schema of unrestricted comprehension:
exists y forall x (x in y iff varphi(x))
for any formula varphi with only the variable x free.Substitute x notin x for varphi(x). Then by existential instantiation (reusing the symbol y) and universal instantiation we have
y in y iff y notin y
a contradiction. Therefore, NST is inconsistent.ENCYCLOPEDIA, Russell's Paradox, The Stanford Encyclopedia of Philosophy, 2014, Zalta, Edward N.,weblink Irvine, Andrew David, Deutsch, Harry, Settheoretic responses
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). 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 firstorder 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 firstorder 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 higherorder 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 higherorder logic, while Zermelo employed secondorder logic, and ZFC can also be given a firstorder formulation. The firstorder 'description' of the cumulative hierarchy is much weaker, as is shown by the existence of denumerable models (Skolem paradox), but it enjoys some important advantages."BOOK, JosÃ© FerreirÃ³s, Labyrinth of Thought: A History of Set Theory and Its Role in Modern Mathematics, 2008, Springer, 9783764383503, 2nd, Â§ Zermelo's cumulative hierarchy pp. 374378, 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 nonaxiomatic 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 ScottPotter set theory.History
Russell discovered the paradox in May or June 1901.{{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=9783110174380 accessdate=20160222}} 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".Russell 1920:136 In a 1902 letter,{{citation url=https://books.google.com/books?id=4ktC0UrG4V8C&pg=PA253 page=253 year=1997 title=The Frege reader isbn=9780631194453 author=Gottlob Frege, Michael Beaney accessdate=20160222}}. Also van Heijenoort 1967:124â€“125 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:{{efnIn the following, p. 17 refers to a page in the original Begriffsschrift, and page 23 refers to the same page in van Heijenoort 1967}}{{efnRemarkably, this letter was unpublished until van Heijenoort 1967â€”it appears with van Heijenoort's commentary at van Heijenoort 1967:124â€“125.}}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 1903:101Russell wrote to Frege about the paradox just as Frege was preparing the second volume of his Grundgesetze der Arithmetik.cf van Heijenoort's commentary before Frege's Letter to Russell in van Heijenoort 1967:126. 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,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.279, translation by Michael Beaney and proposed a solution that Russell would endorse in his Principles of Mathematics,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 functions 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. but was later considered by some to be unsatisfactory.Livio states that "While Frege did make some desperate attempts to remedy his axiom system, he was unsuccessful. The conclusion appeared to be disastrous...." 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 coursesofvalues. 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 functionasconceptinextension 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 1955": "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) For his part, Russell had his work at the printers and he added an appendix on the doctrine of types.Russell mentions this fact to Frege, cf van Heijenoort's commentary before Frege's (1902) Letter to Russell in van Heijenoort 1967:126Ernst Zermelo in his (1908) A new proof of the possibility of a wellordering (published at the same time he published "the first axiomatic set theory")van Heijenoort's commentary before Zermelo (1908a) Investigations in the foundations of set theory I in van Heijenoort 1967:199 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 settheoretic 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 wellordering but only in a suitable restriction of the notion of set".van Heijenoort 1967:190â€“191. In the section before this he objects strenuously to the notion of 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). 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.B. Rang and W. Thomas, "Zermelo's discovery of the 'Russell Paradox'", Historia Mathematica, v. 8 n. 1, 1981, pp. 15â€“22. {{doi10.1016/03150860(81)900021}}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 itcannot 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. (Tractatus LogicoPhilosophicus, 3.333)Russell and Alfred North Whitehead wrote their threevolume 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 firstorder 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 reallife situations and may be easier to understand for nonlogicians. 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:{ class="wikitable" valign="top"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:

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 selfevident.
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 don't.
The question is: should these master catalogues list themselves? The 'Catalogue of all catalogues that list themselves' is no problem. If the librarian doesn't 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 don't list themselves', the librarian cannot include it in its own listing, because then it would include itself, and so belongs to 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
Russelllike 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.
The er that s all (and only those) who don't themselves,
Sometimes the "all" is replaced by "all ers".An example would be "paint":
The painter that paints all (and only those) that don't paint themselves.
or "elect"
The elector (representative), that elects all that don't elect themselves.
Paradoxes that fall in this scheme include:  The barber with "shave".
 The original Russell's paradox with "contain": The container (Set) that contains all (containers) that don't contain themselves.
 The Grellingâ€“Nelson paradox with "describer": The describer (word) that describes all words, that don't describe themselves.
 Richard's paradox with "denote": The denoter (number) that denotes all denoters (numbers) that don't denote themselves. (In this paradox, all descriptions of numbers get an assigned number. The term "that denotes all denoters (numbers) that don't denote themselves" is here called Richardian.)
Related paradoxes
 The liar paradox and Epimenides paradox, whose origins are ancient
 The Kleeneâ€“Rosser paradox, showing that the original lambda calculus is inconsistent, by means of a selfnegating statement
 Curry's paradox (named after Haskell Curry), which does not require negation
 The smallest uninteresting integer paradox
 Girard's paradox in type theory
See also
 Basic Law V
 Cantor's diagonal argument
 Hilbert's first problem
 "On Denoting", one of Russell's first attempts at critiquing Frege
 Quine's paradox
 Selfreference
 Strange loop
 Universal set
Notes
{{notelist}}References
{{reflist30em}} {{citationlast=Potterfirst=Michaeldate=15 January 2004title=Set Theory and its Philosophypublisher=Clarendon Press (Oxford University Press)isbn=9780199269730}}
 {{citationlast=van Heijenoortfirst=Jeanauthorlink=Jean van Heijenoortdate=1967title=From Frege to GÃ¶del: A Source Book in Mathematical Logic, 18791931, (third printing 1976)publisher=Harvard University Presspublicationplace=Cambridge, Massachusettsisbn=0674324498}}
 {hide}citationlast=Liviofirst=Marioauthorlink=Mario Liviodate=6 January 2009title=Is God a Mathematician?publisher=Simon & Schusterpublicationplace=New Yorkisbn=9780743294058
External links
{{WikiversityRussell's paradox}} IEP, parruss, Russell's Paradox,
 {{MathWorld title=Russell's Antinomy id=RussellsAntinomy }}
 Russell's Paradox at CuttheKnot
 Stanford Encyclopedia of Philosophy: "Russell's Paradox" â€“ by A. D. Irvine.
 content above as imported from Wikipedia
 "Russell's paradox" does not exist on GetWiki (yet)
 time: 4:20am EDT  Thu, Jun 27 2019
 "Russell's paradox" does not exist on GetWiki (yet)
 time: 4:20am EDT  Thu, Jun 27 2019
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
Culture
© 2019 M.R.M. PARROTT  ALL RIGHTS RESERVED