# How does ZF fixes Russell's paradox?

1. Jan 1, 2009

### quasar987

In naive set theory, Russell's paradox shows that the "set" $S:=\{X:X \in X\}$ satisfies the weird property $S \in S$ and $S\notin S$.

How does the set theory of Zermelo and Fraenkel get rid of this "paradox"? I.e., which axioms or theorem prohibit S above to be a set?

Thank you.

2. Jan 1, 2009

### Marcaias

It's not that there's an axiom in ZF explicitly preventing Russell's Paradox, but rather ZF *doesn't* include the axiom of comprehension, which is the cause of all the trouble. Instead, it only allows for sets to be "built from" other sets, by union, by image under a function, by power set, and so on, and so on.

In particular, the expression $$\{ x \mid P(x) \}$$ for any old first-order predicate P is no longer necessarily a set, as it would be with comprehension.

Instead, we have the axiom of separation, which guarantees that $$\{ x \in A \mid P(x) \}$$ is a set, given any existing set A and predicate P.

So $$\{ x \in \mathbb{R} \mid x \notin x \}$$, $$\{ x \in 2^{\mathbb N} \mid x \notin x \}$$, and so on are sets, but none of these leads to contradictions (assuming ZF is consistent, of course!)

3. Jan 2, 2009

### Hurkyl

Staff Emeritus
To put things differently... Cantor's set theory said $S:=\{X:\mid X \in X\}$, and Russell's paradox proves S is not a set. Thus contradiction.

In ZF, Russell's paradox still works to prove S is not a set. However, ZF does not (seem to) have a way to prove S is a set, and so there is no contradiction.

Incidentally, don't forget replacement which gives another ZF-legal form of set-builder notation:
$$\{ f(x) \mid x \in A \}$$

The way in which all of this works is remarkedly similar to how formal logic (e.g. first-order, second-order, and so forth) avoids the liar's paradox.