How Separation Resolves Russell's Paradox

DefinitionUnrestricted Comprehension

For each first-order formula $\varphi(x,\vec p)$ in which $S$ does not occur free, naive set theory contains the axiom

\exists S\,\forall x: \bigl(x\in S\iff \varphi(x,\vec p)\bigr).

This is an axiom schema: formulas are not quantified over inside first-order set theory. Each displayed axiom is universally closed over the parameter variables $\vec p$ .

TheoremRussell's Paradox

Unrestricted comprehension is inconsistent. It proves a sentence of the form $P\iff\neg P$ .

Proof

Apply unrestricted comprehension to

\varphi(x):=\neg(x\in x).

Then

\exists R\,\forall x: \bigl(x\in R\iff x\notin x\bigr).

Let $R$ be such a set. Instantiating the universal quantifier at $x:=R$ gives

R\in R\iff R\notin R,

which is of the form $P\iff\neg P$ . Hence unrestricted comprehension is inconsistent. $\blacksquare$

DefinitionAxiom Schema of Separation

For each first-order formula $\varphi(x,\vec p)$ in which $S$ does not occur free,

\forall A\,\exists S\,\forall x: \bigl(x\in S\iff (x\in A\wedge\varphi(x,\vec p))\bigr).

Extensionality makes this $S$ unique, so it may be named

S=\{x\in A\mid \varphi(x,\vec p)\}.

Separation constructs only subsets of an already existing set $A$ . The parameter variables $\vec p$ are universally quantified outside the displayed formula, and $S$ is chosen fresh. The base set $A$ may occur as a parameter in the defining property.

DefinitionRelative Russell Set

Let $A$ be a set. Define

R_A:=\{x\in A\mid x\notin x\}.

Hence

\forall x: \bigl(x\in R_A\iff(x\in A\wedge x\notin x)\bigr). \tag{$\star$}

LemmaThe Relative Russell Set Escapes Its Base Set

\forall A:R_A\notin A.

Proof

Let $A$ be a set. Assume

R_A\in A.

Instantiating $(\star)$ at $x:=R_A$ gives

R_A\in R_A \iff (R_A\in A\wedge R_A\notin R_A).

By the assumption $R_A\in A$ ,

R_A\in R_A\iff R_A\notin R_A,

a contradiction.

Therefore

R_A\notin A.

$\blacksquare$

CorollaryThe Relative Russell Set Is Not Self-Membered

\forall A:R_A\notin R_A.

Proof

Let $A$ be a set. By the lemma,

R_A\notin A.

Instantiating $(\star)$ at $x:=R_A$ gives

R_A\in R_A \iff (R_A\in A\wedge R_A\notin R_A).

Since $R_A\notin A$ , the right-hand side is false. Hence

R_A\notin R_A.

$\blacksquare$

WarningInvalid Specialization

From

\forall A:R_A\notin A,

one must not write "specialize $A:=R_A$ " while treating $R_A$ as unchanged.

The notation $R_A$ depends on the parameter $A$ . Instantiating at $A:=R_A$ yields

R_{R_A}\notin R_A,

not

R_A\notin R_A.

The conclusion $R_A\notin R_A$ follows instead from the defining equivalence $(\star)$ and $R_A\notin A$ .

CorollaryNonexistence of a Universal Set

There is no set $V$ satisfying

\forall x:x\in V.

Proof

Suppose that a set $V$ satisfies

\forall x:x\in V.

By separation, define

R_V:=\{x\in V\mid x\notin x\}.

Since $R_V$ is a set and $V$ contains every set,

R_V\in V.

However, by the lemma,

R_V\notin V.

Contradiction. Therefore no universal set exists. $\blacksquare$

RemarkResolution of Russell's Paradox

Separation does not construct the unrestricted collection

\{x\mid x\notin x\}.

For each set $A$ , it constructs only

R_A=\{x\in A\mid x\notin x\}.

The resulting set satisfies

R_A\notin A \qquad\text{and}\qquad R_A\notin R_A.

The relative construction therefore avoids this contradiction. Notice the distinction: $R_A\subseteq A$ , but $R_A\notin A$ . It is a subset of $A$ , not an element of $A$ . This argument uses no axiom of foundation, and avoiding Russell's contradiction is not a proof that all the axioms of ZF are consistent.