# Axiom of Separation & Russell's Paradox

I've looked through the discussions of Russell's paradox and the Axiom of Separation to aid in my question but I'm still stuck. Here's the problem:

The Axiom of Separation, I'm told, allows us to define, for every set $A$, the set $\{x|x \in A \land x \notin x\}.$ Call this $S$.

I need to show that from the assumption that either $S \in S \lor S \notin S$ what follows is that $S \notin A.$

But I'm having trouble not getting the contradiction.

Here's what I've done. Assuming that $S \in S$, that means that, given the definition of $S$, that $S\in A \land S\notin S.$ So it's true that $S\in A$ and that $S \notin S$. But if the latter is true, then either $S\notin A \lor S\in S$ is true. But this contradicts what my original assumption.

Does anyone have tips about how to go about the proof? I'm missing something, I just don't know what I'm doing wrong. So, I cannot seem to infer that no contradiction but only that $S \notin A$ follows from my assumption.

• "I'm having trouble not getting the contradiction." We don't avoid Russell's Paradox by adding more axioms. We avoid Russell's Paradox by not imputing the existence of a set whose elements are exactly the sets that don't contain themselves as elements. – hardmath Sep 26 '17 at 18:18
• I understand that, but I'm asking how I'm supposed to not be able to derive a contradiction from a particular disjunct given what the Axiom of Separation tells me. I'm just not sure how to give that proof. – Rusty Sep 26 '17 at 18:25
• I think you have a fundamental misunderstanding. You have $A$ and $S$ ambiguously identified as axioms and or sets. If you can derive a contradiction, then adding more axioms doesn't prevent you from deriving a contradiction. So for what exactly did you want "to give that proof"? The purpose of the Axiom of Separation is not to prevent Russell's Paradox, if that is what you are thinking. – hardmath Sep 26 '17 at 18:30
• As as I say, I'm told that the A.O.S tells me that a certain claim, call it S, is true. To block Russell's paradox, I'm being told to show that on the assumption that either $S \in S \lor S\notin S$ that no contradiction falls out of S. – Rusty Sep 26 '17 at 18:32
• If $S$ is "a certain claim", then how could it also be a set? – hardmath Sep 26 '17 at 18:33

## 3 Answers

I assume the setup of your question is intended to be

Let $A$ be a set. Define $S = \{ x \mid x \in A \wedge x \notin x \}$....

In the argument that follows, you want the contradiction you arrived at! The argument you give is predicated on the assumption that $S \in S$. By derivating a contradiction, you conclude the assumption is false; that is, you conclude $S \notin S$.

No further contradiction follows; when expanding out the meaning of $S \notin S$ and simplifying, you ultimately arrive at the conclusion $S \notin A$.

• I thought that I would have to assume that in order to prove that $S \notin A$ from a disjunction I would have to assume that one disjunct, namely that $S \in S$, derive $S \notin A$ and assume the other disjunct, that $S \notin S$ and derive again that $S \notin A$. – Rusty Sep 26 '17 at 18:44
• @Adam: If you insist on that exact form of argument, then predicated on the assumption $S \in S$, once you've derived a contradiction, you can apply the principle of explosion to conclude anything (including $S \notin A$). – Hurkyl Sep 26 '17 at 18:50
• OH! Is this the proof? Assume: $S \in S \lor S \notin S$ (to derive $S\notin A$) Well, if I assume the first disjunct, that $S \in S$, then it's true that $S \in A \land S \notin S$. But this is a contradiction. So, if my assumed disjunction is true it is in virtue of the second disjunct being true, i.e., that $S \notin S$ is true. This means that it's true that $S \notin A$ or $S \in S$. But if that second disjunct is true, then $S \in S$ is false and thus $S \notin A$? – Rusty Sep 26 '17 at 18:53

Hint: You have set A and subset S of A such that $\forall x:[x\in S \iff x\in A \land x\notin x]$. First, prove by contradiction that $A\notin S$. Then prove by contradiction that $S\notin S$. Finally, prove that $S\notin A$.

The issue is to show that the Axiom of Separation avoid the reproduction of the Russell's Paradox.

The "Russell's argument" applied with Separation amounts to concluding with the innocuous $S \notin A$.

By Separation, we have that, for any set $A$, the set:

$S = \{ x \mid x \in A \text { and } x \notin x \}$

exists.

Assume that $S \in A$, and reason by cases.

Firts possibility (i): $S \in S$.

By definition of $S$, we have $S \in \{ x \mid x \in A \text { and } x \notin x \}$. The syntax of $\{ x \mid \varphi(x) \}$ is so that $a \in \{ x \mid \varphi(x) \}$ iff $\varphi(a)$.

Thus, we have that $S \in A$ and $S \notin S$, and thus we have:

if $S \in S$, then $S \notin S$.

Consider nowe (ii): if $S \notin S$, we have that $S \in A$ and $S \notin S$.

So $S$ satisfies the condition of the above definition of $S$, i.e. (again from $\varphi(a)$ to $a \in \{ x \mid \varphi(x) \}$) we have $S \in \{ x \mid x \in A \text { and } x \notin x \}$, that means: $S \in S$.

Nowe we have proved:

if $S \notin S$, then $S \in S$.

From the two results above, we conclude with:

$S \in S$ iff $S \notin S$,

and this is a contradicition.

But this is the general schema of a proof by contradiction: having assumed $S \in A$ and having derived a contradiction, we conclude that our original assumption is untenable, and we have proved the denial of our assumption:

$S \notin A$.