Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Grades 9–12

Russell's paradox and why sets need axioms

Name: ______________________

Date: ______________________

You will learn to

State the naive comprehension principle and derive Russell's contradiction from it
Recognise Russell's argument as a theorem of pure logic about any relation, and connect it with the barber and with Cantor's diagonal argument
Explain how the separation axiom, which only forms $\{x \in 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

1.
A village barber is supposed to shave exactly those villagers who do not shave themselves. What does the barber argument actually prove?
- A.No village can have such a barber.
- B.The barber must be a woman, or live outside the village.
- C.Logic is inconsistent.
- D.The barber both shaves and does not shave himself.
2.
Which axiom of ZF set theory is responsible for blocking Russell's paradox?
- A.Separation: $\{x \in A : P(x)\}$ exists only inside an existing set $A$
- B.Foundation, which implies that no set is an element of itself
- C.Extensionality: sets with the same elements are equal
- D.The axiom of choice
3.
Let $A = \{\varnothing, \{\varnothing\}\}$ . How many elements does $R_A = \{x \in A : x \notin x\}$ have?
4.
In the proof of Theorem 4 we have $x \in R_A \iff (x \in A \text{ and } x \notin x)$ . We suppose $R_A \in A$ and put $x = R_A$ . Why does the condition “ $x \in A$ ” drop out?
- A.Because we assumed $R_A \in A$ , so “ $R_A \in A$ ” is true.
- B.Because every set is an element of $A$ .
- C.Because of the axiom of foundation.
- D.Because $R_A$ is defined without mentioning $A$ .
5.
On the objects $a, b, c$ , a relation $E$ holds exactly for: $a \mathrel{E} a$ , $a \mathrel{E} b$ , $b \mathrel{E} c$ , $c \mathrel{E} c$ , $c \mathrel{E} a$ . List the elements of the Russell set $D = \{x : \text{not } (x \mathrel{E} x)\}$ .
6.
Which statement best describes the relationship between Russell's paradox and the liar paradox (“this sentence is false”)?
- A.They are analogous — both lead to a statement equivalent to its own negation — but Russell's is a rigorous deduction from a precise principle about sets.
- B.They are the same argument in different words.
- C.They have nothing in common.
- D.Separation solves the liar paradox too.
7.
In Mathlib's model of ZFC, which Lean statement says “there is no set of all sets”?
- A.¬ ∃ U : ZFSet, ∀ x, x ∈ U
- B.∀ U : ZFSet, U ∉ U
- C.¬ ∃ U : ZFSet, U ∈ U
- D.∃ U : Set α, ∀ x : α, x ∈ U
8.
A relation on the objects 0, 1, ..., n-1 is given as a set rel of pairs (x, y), meaning “x E y”. Write russell_set(rel, n), returning the set of x with (x, x) not in rel, and witnesses(rel, n), returning the list of all r whose members {x : (x, r) in rel} are exactly the Russell set. Theorem 2 predicts that witnesses always returns [].
Computational — Practice

Answer key — Russell's paradox and why sets need axioms

1.
If the barber shaves himself, he is someone who shaves himself, so he does not shave himself; if he does not, he must shave himself. Assuming the barber exists leads to a contradiction, so no such barber exists. Russell's paradox has exactly this form, with “ $y$ shaves $x$ ” replaced by “ $x \in y$ ”.
2.
Naive comprehension is replaced by separation, which forms $\{x \in A : P(x)\}$ only inside a given set $A$ . Then Russell's argument proves $\{x \in A : x \notin x\} \notin A$ instead of a contradiction. Foundation, which gives $x \notin x$ , is a separate axiom and is not what blocks the paradox.
3.
$\varnothing \notin \varnothing$ (the empty set has no elements), and $\{\varnothing\} \notin \{\varnothing\}$ (its only element is $\varnothing$ ). So both elements qualify and $R_A = A$ , with $2$ elements. As Theorem 4 says, $R_A = A$ is not an element of $A$ .
4.
We assumed $R_A \in A$ . Putting $x = R_A$ , the conjunct “ $R_A \in A$ ” is true, so $R_A \in R_A \iff R_A \notin R_A$ — a contradiction. Hence the assumption is false and $R_A \notin A$ . Without the assumption, no contradiction arises: that is how separation defuses the paradox.
5.
$a \mathrel{E} a$ and $c \mathrel{E} c$ hold, but $b \mathrel{E} b$ does not, so $D = \{b\}$ . Now compare with the “members” of each object: $\{x : x \mathrel{E} a\} = \{a, c\}$ , $\{x : x \mathrel{E} b\} = \{a\}$ , $\{x : x \mathrel{E} c\} = \{b, c\}$ . None equals $D$ — as Theorem 2 guarantees: the members of $y$ and $D$ always disagree about $y$ itself.
6.
Both use self-reference to produce something equivalent to its own negation, so they are analogous. But the liar concerns truth and language, while Russell's paradox is a valid derivation from naive comprehension, a precise principle about sets — so its conclusion is a theorem: that principle is inconsistent.
7.
A universal set would be a U : ZFSet with ∀ x, x ∈ U; the statement is ¬ ∃ U : ZFSet, ∀ x, x ∈ U. Its proof applies russell_sep_not_mem to U: the Russell set inside U is not in U.
8.
```
def russell_set(rel, n):
    return {x for x in range(n) if (x, x) not in rel}

def witnesses(rel, n):
    target = russell_set(rel, n)
    return [r for r in range(n)
            if {x for x in range(n) if (x, r) in rel} == target]
```
The tests try all 16 relations on two objects, and the list is always empty. The reason is Theorem 2: the members of r and the Russell set always disagree about r itself — if (r, r) is in rel then r is a member of r but not in the Russell set, and vice versa.