TheInfoList

In the foundations of mathematics, Russell's paradox (also known as Russell's antinomy), a paradox in logic discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naive 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: :$\text R = \ \text 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. 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 (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, 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, consider 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. Clearly every set must be either normal or abnormal. 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 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

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 \left(x \in y \iff \varphi\left(x\right)\right)$ for any formula $\varphi$ with the variable as a free variable inside $\varphi$. Substitute $x \notin x$ for $\varphi\left(x\right)$. 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.

Set-theoretic responses

History

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)
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

Applications and related topics

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. Form the sentence: :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 ''paint''er that ''paint''s all (and only those) that don't ''paint'' themselves. or "elect" :The ''elect''or (representative), that ''elect''s 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''.) * "I am lying.", namely the liar paradox and Epimenides paradox, whose origins are ancient * Russellâ€“Myhill paradox

* The Burali-Forti paradox, about the order type of all well-orderings * The Kleeneâ€“Rosser paradox, showing that the original lambda calculus is inconsistent, by means of a self-negating statement * Curry's paradox (named after Haskell Curry), which does not require negation * The smallest uninteresting integer paradox * Girard's paradox in type theory

* Basic Law V * Cantor's diagonal argument * Hilbert's first problem * "On Denoting" * Quine's paradox * Self-reference * Strange loop * Universal set

Notes

References

Sources

* * *