10
$\begingroup$

I am a beginner in mathematics and I was reading a text on Set Theory that talked about how Zermelo's Axiom of Selection "solves" Russel's Paradox.

I understand that the the axiom does not allow constructions of the form $$\{x \:: \text S(x) \}$$ and only allows$$\{x \in \text A \:: \text S(x) \}$$ but how does this change the outcome of the paradox when we have:
$$S = \{x \in \text A \:: \text x \notin \text x \}$$ where $S$ is still the set of all sets that do not contain themselves.

Won't we still get the paradox?

$\endgroup$
2
  • 4
    $\begingroup$ We have not constructed $A$, which presumably is supposed to be the "set" of all sets. So we have not constructed $S$. $\endgroup$ Mar 2, 2016 at 23:53
  • 3
    $\begingroup$ Work through the details and you'll see that the paradox doesn't arise. $S$ is now just the set of all members of $A$ that aren't members of themselves. The closest we come is: $S\in S\iff S\in A \land S\notin S$, so $S\notin A$. (Furthermore, by the axiom of Regularity, $x\notin x$ for all $x$, so $S = A$, thus, again, $S\notin A$.) $\endgroup$
    – BrianO
    Mar 3, 2016 at 0:07

3 Answers 3

5
$\begingroup$

Axiom of regularity (or Foundation) rules out the case $S\in S$.

Otherwise, we would have $S\notin S$. Now does this imply $S\in S$?

The problem with Russel's paradox is it implicitly implies existence of universal set ("set of all sets").

If $A$ is a set and $S=\{x\in A:x\notin x\}$, $S\notin S$ implies either $S\in S$ or $S\notin A$.

In case of Russell's paradox, it is not possible to have $S\notin A$, because $S$ must belong to set of all sets, if that existed, and leads us to paradox $S \in S$. But with our construction such set cannot exist (exactly because existence of such set leads us to Russell's paradox). So paradox does not arise.

$\endgroup$
7
  • $\begingroup$ Regularity is not required to avoid Russell's Paradox. $\endgroup$ Mar 6, 2016 at 4:33
  • $\begingroup$ Russell's Paradox does not imply the existence of universal set. In fact, it can be used to prove the universal set does not exist. $\endgroup$ Mar 6, 2016 at 4:54
  • 2
    $\begingroup$ @DanChristensen That's not quite true - for instance, in NF there is a universal set. Roughly speaking, all Russell's paradox disproves is the axiom (scheme) of full comprehension. As a corollary, this shows that you can have either a universal set (NF) or separation (ZFC), but not both. $\endgroup$ Mar 6, 2016 at 5:11
  • $\begingroup$ @NoahSchweber How does NF block the proving of the the non-existence of the universal set? In regular set theory, it can be done using some equivalent of the ZF Specification (Subset) Axiom. Is that not available in NF? $\endgroup$ Mar 6, 2016 at 5:46
  • 2
    $\begingroup$ @DanChristensen Indeed it is not. NF has stratified comprehension instead of separation: the formula "$x\not\in x$" is not stratified, so that blocks Russell's paradox, while "$x=x$" is stratified, leading to the existence of a universal set. (See en.wikipedia.org/wiki/New_Foundations.) $\endgroup$ Mar 6, 2016 at 5:52
3
$\begingroup$

If we assume the existence of a set $R$ such that $$R=\{x: x\notin x\}$$then we can obtain the contradiction $R\in R $ and $R\notin R$. So, $R$ cannot exist.

To avoid Russell's Paradox then, all we need to do is not assume that, for every unary predicate $P$, there exists a set $S$ such that $$S=\{x:P(x)\}$$

If, however, $A$ is assumed or proven to be a set, then we can assume without fear of contradiction that there exists a subset $S\subset A$ such that $$S=\{x\in A: P(x)\}$$Or equivalently$$S=\{ x: x\in A \text{ and } P(x)\}$$

You can think of $P(x)$ as the criterion for selecting elements from the set $A$ for the subset $S$. The only restriction is that the variable $S$ may not occur in the selection criterion. This is the Axiom of Specification (Selection).

If, for example, we have set $A$, then we can assume that there exists a subset $S\subset A$ such that $$S=\{x\in A: x\notin x\}$$ Or equivalently $$S=\{x:x\in A \text{ and } x\notin x\}$$ Then we would not obtain a contradiction, but we would have $S\notin S$ and $S\notin A$). (Proof left as an exercise.)

$\endgroup$
-1
$\begingroup$

The way that the Axiom of Selection prevent's Russell's Paradox is by preventing you from selecting from all sets. Rather you are selecting from the elements of A. Since $ A \in A $ is forbidden by the Axiom of regularity the paradox can't arise.

$\endgroup$
2
  • 4
    $\begingroup$ The axiom of regularity has nothing to do with it. Without regularity, we may have $A\in A,$ we may have $A\notin A,$ in any case $S\notin A,$ no paradox. $\endgroup$
    – bof
    Mar 3, 2016 at 0:35
  • $\begingroup$ More generally, adding axioms can never resolve an inconsistency. $\endgroup$ Dec 25, 2022 at 5:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .