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.