Damascene Philosophy

ParadoxesVII

Russell's paradox

Consider the set of all sets that do not contain themselves. Does it contain itself? If it does, it doesn't. If it doesn't, it does. In 1901 this nearly broke mathematics.

Reading time
4 min
Difficulty
Deep
Branch
Logic
First posed
Bertrand Russell, 1901, in a letter to Gottlob Frege, 1902; discovered independently by Ernst Zermelo
R R ∈ R ? yes → then nono → then yes
R is the set of all sets that do not contain themselves. Does R contain itself?

The puzzle

A set is a collection of things. Some sets contain themselves as members; most do not. The set of all cats is not itself a cat, so it does not contain itself. But the set of all things that are not cats is not a cat, so it does contain itself. So does the set of all sets.

Now consider the set R of all sets that do not contain themselves. Does R contain itself?

If R contains itself, then it is a set that contains itself, so by definition it does not belong in R. Contradiction. If R does not contain itself, then it is a set that does not contain itself, so by definition it belongs in R. Contradiction again.

In 1902 Bertrand Russell wrote to the German logician Gottlob Frege, pointing out that this contradiction could be derived in Frege's system, which was meant to provide a secure logical foundation for all of arithmetic. The second volume of Frege's great work was already at the printer. He added an appendix acknowledging that the foundation of his life's work had collapsed.

Why it matters

The paradox showed that the natural, intuitive idea of a set, any collection defined by any property, is inconsistent. Since almost all of modern mathematics is built on set theory, this was a crisis.

The responses shaped twentieth-century logic and mathematics: axiomatic set theory, type theory, and eventually the theory of computation. Every mathematics student today learns set theory in a form designed specifically to avoid Russell's paradox.

Key terms

  • SetIn mathematics, a collection of things considered as a single object, defined by its members.
  • Naive comprehensionThe principle that for any condition, there is a set of exactly the things that meet it. Russell's paradox shows that it leads to contradiction.
  • Type theoryA family of logical systems that sort objects into levels, or types, so that a collection can only contain things of a lower type. Russell devised it to block his paradox.
  • ZFCZermelo-Fraenkel set theory with the axiom of choice: the standard foundation of modern mathematics, which avoids Russell's paradox by restricting which sets can be formed.
  • Self-referenceA sentence, set or system referring to itself. Many paradoxes, such as the liar and Russell's, arise from it.

Proposed solutions

Proposed solution I

Axiomatic set theory (ZF)

Not every property defines a set. Sets must be built up step by step from simpler sets, according to precise axioms.

Proposed solution II

Type theory

Objects come in a hierarchy of types. A set can only contain things of lower type, so no set can contain itself.

Proposed solution III

Accept some inconsistency

Naive set theory may be inconsistent, but with a paraconsistent logic it need not collapse.

Each solution, tested

Axiomatic set theory (ZF)

How it resolves the paradox
Ernst Zermelo proposed in 1908, and Abraham Fraenkel and others refined, a set of axioms that replace naive comprehension with a weaker 'separation' principle: you can only form a set of things that satisfy a property from within an existing set. There is no set of all sets, and so no Russell set. Zermelo-Fraenkel set theory with the axiom of choice (ZFC) is the standard foundation of mathematics today.
Why it doesn’t fully work
The axioms can seem ad hoc, chosen to block known paradoxes rather than from a clear underlying idea. And Gödel's results show we can never prove, within the system itself, that it is free of contradiction.
What defenders say
Defenders point to the 'iterative conception' of sets, in which sets are formed in stages, each from members already available, which gives the axioms a natural motivation.

Type theory

How it resolves the paradox
Russell's own response, developed with Alfred North Whitehead in Principia Mathematica (1910 to 1913), arranged everything in levels: individuals, sets of individuals, sets of sets of individuals, and so on. The question 'does this set contain itself?' cannot even be asked. Type theory has had a second life in computer science, where types prevent programs from mixing incompatible kinds of data.
Why it doesn’t fully work
Russell's system was complicated and required an axiom of reducibility that many found unjustified. Ordinary mathematical reasoning seems to cross type boundaries freely.

Accept some inconsistency

How it resolves the paradox
Some logicians, notably Graham Priest, argue that the natural concept of a set really is inconsistent, and that the right response is to use a logic in which contradictions do not imply everything. Then naive set theory can be studied without disaster.
Why it doesn’t fully work
Most mathematicians regard inconsistency as unacceptable in a foundation for mathematics, and prefer the well-tested consistency of ZFC.

Who argued what

  • Axiomatic set theory (ZF) Ernst Zermelo, Abraham Fraenkel, John von Neumann
  • Type theory Bertrand Russell, Alfred North Whitehead, Per Martin-Löf
  • Accept some inconsistency Graham Priest, Zach Weber

Variations

The barber

In a village, the barber shaves all and only those men who do not shave themselves. Who shaves the barber? If he shaves himself, he does not; if he does not, he does. Russell used this as a popular illustration. Unlike the set version, the barber has a simple solution: no such barber can exist. The set version is harder because naive set theory seemed to guarantee that the set R exists.

The catalogue

A librarian compiles a catalogue of all catalogues that do not list themselves. Should it list itself? The same contradiction appears.

Grelling's paradox

Call an adjective 'autological' if it describes itself ('short' is short, 'English' is English) and 'heterological' if it does not ('long' is not long). Is 'heterological' heterological? If yes, it describes itself, so it is autological. If no, it does not describe itself, so it is heterological.

Go deeper

Frege's reply

Frege's reply to Russell in June 1902 is a famous document of intellectual honesty. He wrote that Russell's discovery had left him thunderstruck, since it shook the basis on which he had intended to build arithmetic. He tried to repair his system in an appendix, but the repair was later shown to fail too. Frege never fully recovered the project.

Related ideas

Paradox

The liar paradox

'This sentence is false.' If it is true, it is false. If it is false, it is true. A single short sentence seems to break logic.

Paradox

Zeno's paradoxes

Achilles can never catch a tortoise with a head start, because each time he reaches where it was, it has moved on. Motion itself, Zeno argued, is impossible.

Paradox

The sorites paradox

One grain of sand is not a heap. Adding one grain never turns a non-heap into a heap. So, by that logic, a million grains are not a heap either.

Paradox

The unexpected hanging

A judge says a prisoner will be hanged next week on a day that will come as a surprise. The prisoner proves it cannot happen. Then it happens, and he is surprised.

Further reading and sources

Open questions

  • Is there a set of everything?
  • If our intuitive idea of a collection is inconsistent, can we trust our other intuitions?
  • Can mathematics ever be proven free of contradiction?

All paradoxes · Take me somewhere · Print this page