Russell's paradox is a paradox discovered by Bertrand Russell in 1901 which shows that the naive set theory of Cantor and Frege is contradictory. Consider the set M to be "The set of all sets that do not contain themselves as members". Formally: A is an element of M if and only if A is not an element of A.

In Cantor's system, M is a well-defined set. Does M contain itself? If it does, it is not a member of M according to the definition. On the other hand, if we assume that M does not contain itself, then it has to be a member of M, again according to the very definition of M. Therefore, the statements "M is a member of M" and "M is not a member of M" both lead to contradictions.

In Frege's system, M corresponds to the concept does not fall under its defining concept. Frege's system also leads to a contradiction: that there is a class defined by this concept, which falls under its defining concept just in case it does not.

Contents

1 History 2 Easy-to-understand version of the Paradox 3 Set-theoretic responses to the Paradox 4 Easy-to-understand version of responses to the Paradox 5 Applications and related topics

History

Exactly when Russell discovered the paradox is not clear. It seems to have been May or June 1901, probably as a result of his work on Cantor's theorem that the number of entities in a certain domain is smaller than the number of subclasses of those entities. In Russell's Principles of Mathematics (not to be confused with the earlier Principia Mathematica) Chapter X, section 100, where he calls it "The Contradiction" he says that he was led to it by analyzing Cantor's proof that there can be no greatest cardinal. He also mentions it in a 1901 paper in the International Monthly , entitled "Recent work in the philosophy of mathematics" Russell mentioned Cantor's proof that there is no largest cardinal and stated that "the master" had been guilty of a subtle fallacy that he would discuss later.

Famously, Russell wrote to Frege about the paradox in June 1902, just as Frege was preparing the second volume of his Grundgesetze . Frege was forced to prepare an appendix in response to the paradox, but this later proved unsatisfactory. It is commonly supposed that this led Frege completely to abandon his work on the logic of classes.

While Zermelo was working on his version of set theory, he also noticed the paradox, but thought it too obvious and never published anything about it! Zermelo's system avoids the difficulty through the famous Axiom of separation (Aussonderung).

Russell, with Alfred North Whitehead, undertook to accomplish Frege's task, this time using a more restricted version of set theory that, they thought, would not admit Russell's Paradox, but would still produce arithmetic. Kurt Gödel later showed that, even if it was consistent, it did not succeed in reducing all mathematics to logic. Indeed this could not be done: arithmetic is "incomplete."

Easy-to-understand version of the Paradox

There are some versions of this paradox which are closer to real-life situations and may be easier to understand for non-logicians: for example, the Barber paradox supposes a barber who shaves everyone who does not shave himself, and no one else. When you start to think about whether he should shave himself or not, the paradox becomes obvious.

Similarly, Russell's paradox proves that an encyclopedia entry entitled "List of all lists that do not contain themselves" must be either incomplete (if it does not list itself) or incorrect (if it does).

As illustrated below, consider five lists of encyclopedia entries within that same encyclopedia:

List of articles about people: Ptolemy VII of Egypt Hermann Hesse Don Nix Biography of Nikola Tesla Gilder

List of articles about computer science: Jar TDI Abstract-Type and Scheme-Definition Language

List of articles about places: Leivonmäki Katase River

List of articles about Japan: Emperor Konin of Japan Katase River

List of all lists that do not contain themselves: List of articles about Japan List of articles about places List of articles about computer science List of articles about people List of all lists that do not contain themselves?

If the "List of all lists that do not contain themselves" contains itself, than it does not belong to itself and should be removed. However, if it does not list itself, then it should be added to itself.

While appealing, these "layman's" versions of the paradox share a drawback: an easy refutal of, e.g., Barber's paradox seem to be: "Such a barber does not exist". The whole point of Russel's paradox is that the answer "such a set does not exist" means that the definition of the notion of "set" within a given theory is unsatisfactory. Notice the subtle difference between the statements: "such a set does not exist" and "such a set is empty", a distinction that often eludes a non-expert.

Set-theoretic responses to the Paradox

After this paradox was described, set theory had to be reformulated axiomatically as axiomatic set theory in a way that avoided this and other related problems. Russell himself, together with Alfred North Whitehead, developed a comprehensive system of types in his work Principia Mathematica. This system does indeed avoid the known paradoxes and allows for the formulation of all of mathematics, but it has not been widely accepted. The most common version of axiomatic set theory in use today is Zermelo-Fraenkel set theory, which avoids the notion of types and restricts the universe of sets to those which can be constructed from given sets using certain axioms. The object M discussed above cannot be constructed like that and is therefore not a set in this theory; it is a proper class.

Easy-to-understand version of responses to the Paradox

Some of the various set-theoretic approaches to address and circumvent Russell's paradox can be illustrated in the context of Wikipedia, respecting the requirement that the content of each entry must be correct according to its entry name, and allowing the possibility of its entire contents to be correctly linked in turn:

• either by self links of entry content to the same entry being discouraged; together with noting that the entity through which all Wikipedia entries are necessarily linked, namely Wikipedia as a whole, is itself not just an entry, but an entire web site. Accordingly, no entry would contain and link to itself; and the entity containing all entries (which don't link to themselves) is identified as the whole Wikipedia;
• or instead by requiring that the name of any entry which concerns listing, inclusion or linking must be explicit and decisive about the inclusion of the entry itself. Names such as list of all lists which do not contain themselves, but including this one itself, and list of all lists which do not contain themselves, except this one could be correctly and legitimately articulated as Wikipedia entries (although doing so is nevertheless not advisable, if their contents may be obtained in Wikipedia more efficiently otherwise).

In context of the Barber example, the latter requirement would ensure the consideration instead, for instance, of a barber who shaves everyone who does not shave himself, as well as the barber himself; perhaps along with a town sheriff who may arrest all those who cannot arrest themselves, with exception of the sheriff.

Applications and related topics

The Barber paradox, in addition to leading to a tidier set theory, has been used twice more with great success: Kurt Gödel proved his incompleteness theorem by formalizing the paradox, and Turing proved the undecidability of the Halting problem (and with that the Entscheidungsproblem) by using the same trick.

Russell's Paradox is closely related to the Liar paradox.