Russell's Paradox and the Axiom of Foundation

Russell's paradox, discovered by Bertrand Russell in 1901, revealed a fatal flaw in naive set theory and motivated the careful axiomatization of set theory through ZFC. The axiom of foundation (or regularity) was introduced partly to prevent certain pathological sets.

TheoremRussell's Paradox

There is no set $R$ such that $R = \{x : x \notin x\}$ . In other words, the collection of all sets that do not contain themselves cannot be a set.

Proof

Suppose for contradiction that such a set $R$ exists. Then we ask: does $R$ contain itself?

Case 1: Suppose $R \in R$ . By definition of $R$ , this means $R$ satisfies the property $R \notin R$ . Contradiction.

Case 2: Suppose $R \notin R$ . Then $R$ satisfies the property $x \notin x$ , so by definition of $R$ , we have $R \in R$ . Contradiction.

Both cases lead to contradiction, so no such set $R$ can exist.

■

This paradox demonstrates that unrestricted comprehension—the principle that any property defines a set—is inconsistent. ZFC avoids this by using the axiom schema of separation (restricted comprehension), which only allows us to form subsets of existing sets.

Remark

In ZFC, Russell's paradox shows that the class of all sets is not itself a set, but rather a proper class. We write $V = \{x : x = x\}$ for the class of all sets, but $V \notin V$ because $V$ is not a set.

The axiom of foundation (regularity) provides additional structure to the set-theoretic universe by eliminating certain pathological sets:

DefinitionAxiom of Foundation

Every non-empty set $A$ contains an element that is disjoint from $A$ :

\forall A(A \neq \emptyset \rightarrow \exists x \in A(x \cap A = \emptyset))

Equivalently, there are no infinite descending membership chains: there is no sequence $\langle x_n : n \in \omega \rangle$ such that $\cdots \in x_2 \in x_1 \in x_0$ .

Foundation has several important consequences:

TheoremConsequences of Foundation

The axiom of foundation implies:

No set contains itself: $\forall x(x \notin x)$
No two-cycles: There are no sets $x, y$ with $x \in y$ and $y \in x$
Uniqueness of the empty set: There is exactly one set with no elements
Well-foundedness: The membership relation $\in$ is well-founded on any set

Proof

We prove (1) as an example. Suppose for contradiction that $x \in x$ for some set $x$ . Consider the set $A = \{x\}$ . By foundation, there exists $y \in A$ such that $y \cap A = \emptyset$ . Since $A = \{x\}$ , we must have $y = x$ . But then:

y \cap A = x \cap \{x\} = \{x\} \neq \emptyset

since $x \in x$ and $x \in \{x\}$ . This contradicts $y \cap A = \emptyset$ .

■

The axiom of foundation is equivalent to the statement that every set has a rank in the cumulative hierarchy:

DefinitionCumulative Hierarchy

Define the von Neumann hierarchy by transfinite recursion:

\begin{align*} V_0 &= \emptyset \\ V_{\alpha+1} &= \mathcal{P}(V_\alpha) \\ V_\lambda &= \bigcup_{\alpha < \lambda} V_\alpha \text{ for limit } \lambda \end{align*}

The rank of a set $x$ is the least ordinal $\alpha$ such that $x \in V_{\alpha+1}$ .

ExampleRanks of Simple Sets

Computing ranks for basic sets:

$\text{rank}(\emptyset) = 0$ since $\emptyset \in V_1 = \mathcal{P}(V_0)$
$\text{rank}(\{\emptyset\}) = 1$ since $\{\emptyset\} \in V_2 = \mathcal{P}(V_1)$
$\text{rank}(\{\emptyset, \{\emptyset\}\}) = 2$
$\text{rank}(\omega) = \omega$ since $\omega = \bigcup_{n \in \omega} V_n$

In general, if $x = \{y_1, \ldots, y_n\}$ , then $\text{rank}(x) = \sup\{\text{rank}(y_i) + 1 : i = 1, \ldots, n\}$ .

Foundation ensures that the universe of sets is built up from the empty set through iterated power set and union operations. This gives set theory a clear hierarchical structure and rules out exotic objects like:

Sets that contain themselves
Infinite descending chains $\cdots \in x_2 \in x_1 \in x_0$
"Quine atoms" that satisfy $x = \{x\}$

Remark

While foundation is a standard axiom of ZFC, some alternative set theories drop it. For instance, Aczel's anti-foundation axiom (AFA) allows non-well-founded sets and has applications in computer science (modeling circular data structures) and formal semantics. However, most mainstream mathematics is conducted in ZFC with foundation.

The interplay between Russell's paradox and foundation illustrates the delicate balance in set theory: we need axioms strong enough to develop mathematics, but restricted enough to avoid contradictions. ZFC achieves this balance, providing a consistent foundation for modern mathematics.