In Naive Set Theory, Paul Halmos introduces an arbitrary set $A$ and another set $B = \lbrace{x \in A: x \notin x \rbrace}$. He then asserts that $B \notin A$ because $B \in A$ implies $B \in B$ or $B \notin B$, both of which lead to a contradiction.

My question is how does $B \notin A$ resolve the contradiction? It seems to me that no matter what the condition is, a set is either in another set or not: if $B \notin A$, it still follows that either $B \in B$ or $B \notin B$.

Note: the fact that,

$(*)$ for all $y$, $y \in B$ if and only if ($y \in A$ and $y \notin y$)

is also given as a consequence of the definition of $B$.

  • 2
    $\begingroup$ Halmos doesn't claim that $B\not\in A$ ${\it because}$ $B\in A$ implies $B\in B$ or $B\not\in B$. In other words, the argument is not of the form "$\phi$ implies $\psi$ or $\neg\psi$. Therefore, $\neg\phi$". As you point out, that is crazy. Rather, the argument is this. 1. if $B\in A$, then either $B\in B$ or $B\not\in B$. 2. if $B\in A$ and $B\in B$, then $\bot$. 3. if $B\in A$ and $B\not\in B$, then $\bot$. Therefore, if $B\in A$, then $\bot$. So, $B\not\in A$. $\endgroup$ – GME Jan 26 '14 at 7:16
  • $\begingroup$ @GME: that helps me understand somewhat. However, I still can't see how we know that we can't assume $B \notin A$ and then contrive some other contradiction. Help? $\endgroup$ – math wannabe Feb 4 '14 at 1:38
  • 1
    $\begingroup$ So, here's one way to see that we won't get a contradiction, at least given the assumptions we've made about $A$ and $B$ (which are: $B\not\in A$ and $B = \{x\in A: x\not\in x\}$). Let $A$ and $B$ both be the empty set. Then it's true that $B\not\in A$ and $B = \{x\in A: x\not\in x\}$. Since it's consistent to assume that the empty set exists, it's consistent to assume that there are $A$ and $B$ such that our assumptions hold. $\endgroup$ – GME Feb 4 '14 at 10:12

If $B\in B$ then $B\in A$ and $B\notin B$, which is a contradiction.

If $B\notin B$ then $B\notin A$ or $B\in B$, which is not a contradiction, seeing as $B\notin A$.

  1. Suppose $\forall x:[x\in B \iff x\in A \land x\notin x]$ (the definition of $B$)

  2. Specifying $x=B$ in (1), we obtain $B\in B \iff B\in A \land B\notin B$

  3. Suppose $B\in A$

  4. Suppose $B\in B$

  5. From (2) and (4), we obtain $B\notin B$, and the contradiction $B\in B \land B\notin B$

  6. Thus (4) is false and we have $B\notin B$

  7. From (2), (4) and (6), we obtain $B\in B$, and the contradiction $B\in B \land B\notin B$

  8. Thus (3) is false and we have $B\notin A$

Note that we cannot now obtain $B\in A$, as in the resolution of Russell's Paradox, to get yet another contradiction.


This approach makes a mistake that many people make about logic.

You can't resolve a paradox by introducing more axioms. Ever.

This question mentions one of the many ways that formal logical has tried to reconcile with Russell's paradoxical definition: the introduction of a universal set. In this case the author is using a subset of the universal set, $A$.

Either way, it just begs the question: "does the universal set contain Russell's self contradictory object?"

Maybe the author himself addresses this issue, I don't have the text. But $B \not \in A$ doesn't "resolve a [paradoxical] contradiction", it is simply a statement that follows from the definition of $B$. While a definition may lend insight into ways of resolving RP, adding a definition can never eliminate it; you have to take a different approach if your goal is to resolve RP.

  • 1
    $\begingroup$ $A$ is not assumed to be a universal set in the original posting, so the initial premise (the definition of B) is not contradicted. Naive set theory is inconsistent because it admits the existence of the self-contradictory Russell Set. Several different patches have been applied to naive set theory to disallow the existence of the things like the Russell Set, the simplest being an axiom schema of separation (as in ZFC theory). $\endgroup$ – Dan Christensen Jan 27 '14 at 14:51

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.