How does ZF fixes Russell's paradox?

[quasar987]

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

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 [tex] \{ x \mid P(x) \} [/tex] 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 [tex]\{ x \in A \mid P(x) \}[/tex] is a set, given any existing set A and predicate P.

So [tex]\{ x \in \mathbb{R} \mid x \notin x \}[/tex], [tex]\{ x \in 2^{\mathbb N} \mid x \notin x \}[/tex], 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 [itex]S:=\{X:\mid X \in X\}[/itex], 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:
[tex]\{ f(x) \mid x \in A \}[/tex]


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.