Editing Russell's paradox (section)

== 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 |publisher=Walter de Gruyter |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 |publisher=Wiley |access-date=2016-02-22 }}. Also van Heijenoort 1967:124–125</ref> 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 (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]]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 [[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]] 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 [[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, [[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. (''[[Tractatus Logico-Philosophicus]]'', 3.333)
</blockquote>

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 [[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"/>