How does ZF fixes Russell's paradox?

[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.

 

[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!)

 

[Hurkyl]

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.