Russells paradox

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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

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. In both cases we get a contradiction but one of them must be true. 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 story of the barber who shaves everyone who does not shave himself. When you start to think about whether he should shave himself or not you will get puzzled...

After this paradox came up, set theory was formulated axiomatically in a way that avoided this paradox and other related paradoxes. Russell himself, together with Alfred North Whitehead, developed a system of types in his work Principia Mathematica. The most common version of axiomatic set theory in use today is Zermelo-Fraenkel set theory, which avoids the notion of types but restricts the construction of new sets from given ones by certain axioms.

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


See also: