RUSSELL'S PARADOX

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.

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 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 later 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*.

[*Some revisionist historians have argued against this, can someone supply references?]

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 which considers 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 you will get puzzled...

Similarly, Russell's paradox proves that, on Wikipedia, if we had an entry on list of all lists which do not contain themselves, then that list must be either incomplete (if it does not list itself) or incorrect (if it does).

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.

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.