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.

  • $\begingroup$ "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. $\endgroup$ – hardmath Sep 26 '17 at 18:18
  • $\begingroup$ 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. $\endgroup$ – Rusty Sep 26 '17 at 18:25
  • $\begingroup$ 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. $\endgroup$ – hardmath Sep 26 '17 at 18:30
  • $\begingroup$ 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. $\endgroup$ – Rusty Sep 26 '17 at 18:32
  • $\begingroup$ If $S$ is "a certain claim", then how could it also be a set? $\endgroup$ – hardmath Sep 26 '17 at 18:33

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

  • $\begingroup$ 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$. $\endgroup$ – Rusty Sep 26 '17 at 18:44
  • $\begingroup$ @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$). $\endgroup$ – Hurkyl Sep 26 '17 at 18:50
  • $\begingroup$ 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$? $\endgroup$ – 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 \}$


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


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.