Russell's paradox

Russell's paradox (also known as Russell's antinomy) is a paradox discovered by Bertrand Russell in 1901 which shows that the naïve 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 (but see Independence from Excluded Middle below).

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.

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."

Applied versions

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 titled "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:

If the "List of all lists that do not contain themselves" contains itself, then 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 refutation of, for example, Barber's paradox seems to be: "Such a barber does not exist". The whole point of Russell'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".

Set-theoretic responses

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.

Other approaches have been proposed, such as New Foundations. One completely overlooked grammatical approach is the same as Prior's solution to the Liar paradox, completely avoiding types and meta-theories. If one insists that grammatically well-formed sets must contain themselves, then Russell's paradox is obviated. In much the same way the listing of the elements a,b,c of a set does not indicate a set. The usual grammatical way to indicate a set is to put brackets around the elements, e.g. the set containing a,b,c is denoted {a,b,c}. Of course the only objection to Prior's solution is that "but I don't want to have to have sets contain themselves!" to which one of an infinite number of replies is "but I don't want to have to put brackets around a list elements to show that they are a set!"

Responses illustrated

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-like paradoxes

As illustrated above for Barbers and Lists, the Russell paradox is not hard to extend. Needed is

• A transitive verb V, that
• can be applied to its substantive form.

Form the sentence

The Ver that Vs all (and only those) who don't V themselves,

Sometimes the "all" is replaced by "all Vers".

An example would be "paint":

The painter that paints all that don't paint themselves.

or "elect"

The elector (representative), that elects all that don't elect themselves.

Paradoxes that fall in this scheme are

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

Independence from Excluded Middle

The paradoxical argument like the one at the start of this article has the form of constructing a purported proposition P which would be true if and only if it were false, entailing that the construction is defective. Often, as is done above, showing the absurdity of such a proposition is based upon the law of excluded middle, by showing that absurdity follows from assuming P true and from assuming it false. Thus, it may be tempting to think that the paradox is avoidable by avoiding the law of excluded middle, as with Intuitionistic logic.

On the contrary, assume P iff not P. Then P implies not P. Hence not P. And hence, again using our assumption in the opposite direction, we infer P. So we have inferred both P and its negation from our assumption, with no use of excluded middle.

Other related paradoxes

• The liar paradox and Epimenides paradox, whose origins are ancient.
• Curry's paradox (named after Haskell Curry, b. 1912), which does not need negation.