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$ – André Nicolas Mar 2 '16 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 '16 at 0:07
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$
6
  • $\begingroup$ Regularity is not required to avoid Russell's Paradox. $\endgroup$ – Dan Christensen Mar 6 '16 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$ – Dan Christensen Mar 6 '16 at 4:54
  • 1
    $\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$ – Noah Schweber Mar 6 '16 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$ – Dan Christensen Mar 6 '16 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$ – Noah Schweber Mar 6 '16 at 5:52
2
$\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 A$. (Proof left as an exercise.)

$\endgroup$
0
$\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$
1
  • 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 '16 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.