Russell's paradox and why sets need axioms

Builds on

Required prerequisites, all the way down: 10

You will learn to

• State the naive comprehension principle and derive Russell's contradiction from it.
• Explain how the separation axiom, which only forms {x ∈ A : P(x)} inside an existing set A, blocks the paradox, and deduce that there is no set of all sets.
• Distinguish naive set theory, a useful informal language, from axiomatic set theory, a precise theory.

Definition

• Naive comprehension: for every property P there is a set {x : P(x)}.
• Russell's set is R = {x : x ∉ x}.
• Separation: for every set A and property P, {x ∈ A : P(x)} is a set.

Theorem

• Naive comprehension is inconsistent: it gives R ∈ R if and only if R ∉ R.
• With separation, for any set A the set {x ∈ A : x ∉ x} is not an element of A; hence no set contains every set.
• Ordinary mathematics can be carried out in axiomatic set theories such as ZFC that avoid the paradox.

Common misconceptions

• Thinking the paradox shows mathematics is inconsistent; it shows naive comprehension is.
• Treating Russell's paradox and the liar paradox as the same argument; they are analogous, not identical.
• Believing ZF avoids the paradox by banning x ∈ x. ZF does prove x ∉ x, but from the separate axiom of foundation; the paradox is blocked by restricting comprehension to separation.

Optional discoveries

• ZFC: axiomatic set theory Zermelo proposed axioms avoiding the paradox in 1908; with the axiom of replacement (Fraenkel, Skolem) and the axiom of choice these became ZFC.Wonder Trail →
• Type theory and propositions as types Russell's own response was a theory of types, which stratifies objects by type; modern type theories descend in part from this idea.
• ← Collections
• ← Sets

Further reading

• Paul R. Halmos, Naive Set Theory (1960)
• Herbert B. Enderton, Elements of Set Theory (1977)