Russell's paradox

Russell's paradox is a paradox found by Bertrand Russell in 1901 which shows that naive set theory in the sense of Cantor is contradictory. Initially, Russell discovered the paradox while studying a foundational work in symbolic logic by Gottlob Frege. While Zermelo was creating his version of set theory, he noticed that this paradox occurred, but thought it was too obvious and never published the inconsistency.

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 the sense of Cantor, M is a well-defined set. Does it contain itself? If we assume that 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, than 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 a contradiction. So this must be a contradiction in the underlying theory.

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 cleaner set theory, has been used twice more with smashing 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 a contradiction discovered by Bertrand Russell in the foundations of set theory.

Set theory was developed by mathematicians in the nineteenth century. In essence, it consists in little more than talking about sets of things--where sets are entirely individuated by their members, but are not themselves those members--and talking about the relationships between objects and sets (membership) or between sets and other sets (subset- or superset-hood; also membership). Set theory was found to be a radically powerful new method of proof, and was quickly applied in a variety of fields.

Toward the end of the century the logician Gottlob Frege appealed to set theory in his attempt to show that mathematics could be reduced to logic (that is, that all mathematical propositions could be stated in logical language, and that all mathematical truths could be proven by logical rules). It was assumed at the time that set theory was just a part of logic. Frege succeeded in reducing mathematics to classical logic plus set theory. While he was in the midst of publishing his work, in 1903, Bertrand Russell sent him a letter communicating a problem he had discovered in Frege's methods.

In set theory it was assumed that:

1. There is a set for any collection of objects you like. For example, you could talk of the set of kings of England; you could also talk of the set of the pope, the number five, and Mars.
2. Sets can be members of sets in the same way other things can be members of sets.
3. Loosely, any (coherent) description you could give determined a set: the set of exactly those things that filled the description. For example, "all the things that are blue" is a set; so is "all the things that have been thought about by men with mustaches, and all of the moments in time at which red-haired women have blinked, and all the sets of all those moments in time."
4. Sets could be members of themselves. For example, the set of all the sets which are not empty. There are nonempty sets; all of those would be in the set of nonempty sets; so the set of nonempty sets would be nonempty; so the set of nonempty sets would be a member of the set of nonempty sets.

Russell made the following discovery: if every description determines a set, then so does the following description: "is a set which is not a member of itself". It should determine exactly the set of all those sets that are not members of themselves. Call this set, whatever its members are, X. Now, is X a member of itself?

Suppose X is not a member of itself. Then X fits the description which determines members of X. Then X is a member of X. But that contradicts the hypothesis: it cannot be that X both is and is not a member of itself.

So suppose X is a member of itself. But by definition, all the members of X are sets which are not members of themselves. Since X is a member of X, X must also be a set which is not a member of itself: X must not be a member of itself.

So if X is a member of itself, it is not; and if it is not, it is. This is Russell's paradox, then: just the set of all sets that are not members of themselves. It is contradictory, and if set theory entails contradictions, one cannot base mathematics on it.

In the light of this discovery, Frege tried but failed to patch up his system. Set theory was completely rebuilt several times (and previous set theory came to be called "Naive Set Theory"), and in any case came no longer to be seen as part of "logic proper." 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."

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