Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 38 Β· Axioms and Paradoxes

Russell's Paradox

Understand Russell's paradox, why unrestricted set formation breaks set theory, and how separation avoids it, with runnable simulations in Python.

Early set theory was naive: any property you could state defined a set. Given a property P(x), you could form {x : P(x)}, the set of everything that has the property. This is called unrestricted comprehension, and it seems perfectly reasonable. In 1901 Bertrand Russell found a property for which it leads to an outright contradiction. The discovery forced mathematicians to rebuild set theory on careful axioms.

The paradox

Some sets are members of themselves, and most are not. The set of all sets with more than 3 elements has more than 3 elements, so it is a member of itself (if it is a set at all). The set of all cats is not a cat, so it is not a member of itself.

Form the set of all sets that are not members of themselves:

Text
R = { x : x βˆ‰ x }

Is R ∈ R?

  • If R ∈ R, then R satisfies the defining property, so R βˆ‰ R. Contradiction.
  • If R βˆ‰ R, then R satisfies the defining property x βˆ‰ x, so R must be in R. Contradiction.

Both answers fail. The statement R ∈ R ⟺ R βˆ‰ R is a contradiction, and from a contradiction anything follows. So unrestricted comprehension cannot be part of set theory.

Russell communicated the paradox to Gottlob Frege in 1902, just as Frege's logical foundation of arithmetic was going to press. Frege added a famously gracious appendix acknowledging that the foundation of his work had been shaken.

A computer simulation

We can model "a set" as a function that answers membership questions: s(x) is True if x ∈ s. Then R is the function that asks the self-membership question and negates it. Applying R to itself loops forever, as the paradox predicts.

Python Simulate Russell's set as a membership function

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same pattern: the barber

A popular version: in a village the barber shaves exactly those people who do not shave themselves. Who shaves the barber? If he shaves himself, he does not (he only shaves those who don't). If he does not, then he must. Such a barber cannot exist.

We can check this by brute force for a small village. For 3 people there are 2⁹ = 512 possible "shaves" relations. For each, test whether somebody satisfies the barber rule.

Python No barber exists: brute-force check

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The count is zero in every case. The argument that no barber exists uses the same logic as the proof of Cantor's theorem: p ↦ "the people p shaves" cannot match the self-referential set.

How set theory escaped

Mathematicians kept the idea of sets but restricted how sets may be formed.

  • Separation (also called specification): you may only carve out a subset of a set you already have. For a set A and property P, {x ∈ A : P(x)} is a set. Now R_A = {x ∈ A : x βˆ‰ x} is a perfectly fine set, and the same argument now proves a harmless fact: R_A βˆ‰ A. There is no set containing all sets.
  • Types (Russell's own fix): objects, sets of objects, sets of sets of objects, and so on, are kept on different levels, and x ∈ x is not even grammatical.
  • Classes (von Neumann, Bernays, GΓΆdel): "the collection of all sets" exists but is a proper class, too large to be a member of anything.

Zermelo's axioms (1908), later improved by Fraenkel and Skolem, are the standard answer, described in the next lesson.

A safe version in code

With separation, you can always select from a set you already have, and the self-membership test never causes trouble because a set in the Python sense cannot contain itself: Python's frozenset objects are built bottom-up, so x ∈ x is impossible.

Python Separation is safe: filter inside a given set

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The theorem you can prove: for any set A, the set R_A = {x ∈ A : x βˆ‰ x} is not an element of A. So no set contains every set.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is Russell's set R?

    R = {x : x βˆ‰ x}. Asking whether R ∈ R gives a contradiction either way.
  2. 2. Which principle does Russell's paradox show cannot hold in general?

    Unrestricted comprehension says every property defines a set. Russell's property x βˆ‰ x defeats it.
  3. 3. How does the axiom of separation avoid the paradox?

    Separation builds R_A inside A, and then R_A βˆ‰ A, so no universal set results.
  4. 4. In the barber paradox, why can't the barber exist?

    If he shaves himself, he violates the rule that he shaves only non-self-shavers; if not, he must shave himself. Same shape as Russell's argument.

Summary

  • Naive set theory allowed {x : P(x)} for every property P.
  • Russell's set R = {x : x βˆ‰ x} satisfies R ∈ R ⟺ R βˆ‰ R: a contradiction.
  • The barber paradox has the same logical form.
  • Axiomatic set theory replaces unrestricted comprehension with separation: you can only select from a set that already exists.
  • As a result there is no set of all sets; collections that are too big are proper classes.

Next: The ZFC Axioms