Russell's paradox

Russell's paradox is a paradox uncovered by Bertrand Russell in 1901, which forced a reformulation of set theory. One version of Russell's paradox, known as the barber paradox, considers a town with a male barber who, every day, shaves every man who doesn't shave himself, and no one else. Does the barber shave himself? The scenario as described requires that the barber shave himself if and only if he does not! Russell's Paradox, in its original form considers the set of all sets that aren't members of themselves. Most sets, it would seem, aren't members of themselves – for example, the set of elephants is not an elephant – and so could be said to be "run-of-the-mill." However, some "self-swallowing" sets do contain themselves as members, such as the set of all sets, or the set of all things except Julius Caesar, and so on. Clearly, every set is either run-of-the-mill or self-swallowing, and no set can be both. But then, asked Russell, what about the set S of all sets that aren't members of themselves? Somehow, S is neither a member of itself nor not a member of itself. Russell discovered this strange situation while studying a foundational work in symbolic logic by Gottlob Frege. After he described it, set theory had to be reformulated axiomatically in a way that avoided such problems. Russell himself, together with Alfred North Whitehead, developed a comprehensive system of types in Principia Mathematica. Although this system does avoid troublesome paradoxes and allows for the construction of all of mathematics, it never became widely accepted. Instead, the most common version of axiomatic set theory in use today is the so-called Zermelo-Fraenkel set theory, which avoids the notion of types and restricts the universe of sets to those that can be built up from given sets using certain axioms. Russell's paradox underlies the proof of Gödel's incompleteness theorem as well as Alan Turing's proof of the undecidability of the halting problem.