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