"It follows that, whatever the set $A$ may be, if $B = \{x \in A: x \notin x \}, $ then, for all $y$,

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

Can it be that $B \in A$? We proceed to prove that the answer is no. Indeed, if $B \in A$, then either $B\in B$ also (unlikely, but not obviously impossible), or else $ B\notin B$. If $B\in B$, then, by ( * ), the assumption $B\in A$ yields $B \notin B$ -- a contradiction. If $B \notin B$, then, by ( * ) again, the assumption $B \in A$ yields $B \in B$--a contradiction again."

So this is from Halmos book (Naive Set Theory) under the axiom of specification section. Lets go step by step. If we are to assume that $B \in A$ there are logically only two possible scenarios then either $B\in B$ or else $ B\notin B$ (it is or it isn't). What I don't get is where do these contradictions come from? Why does $B \in A$ yield $B \in B$ if $B \notin B$ (going by ( * )) and vice versa. I can't seem to understand it.


Supposing that $B\in A$ we have two possibilities.

First possibility: $B\in B$

In the case that $B\in B$, by assumption for this possibility, this contradicts what it means to be an element of $B$. We had assumed also that $B\in A$, which our definition of $B$ is that all elements in $B$ are elements of $A$ which are not elements of themselves, i.e. $B\notin B$.

Since it is never true that something both is and isn't an element of something simultaneously, we see that this is an impossible scenario.

Second possibility: $B\notin B$

In the case that $B\notin B$, then this suggests that since we assumed $B\in A$ and $B\not\in B$, by definition of $B$ it is an element of $A$ which is not an element of itself, and therefore should have been an element of $B$. Therefore, $B\in B$. But, we had assumed that $B\not\in B$. Again, since it is impossible for something to simultaneously be and not be an element of something else, this again reaches a contradiction.

Since either possibility yields a contradiction, neither possibility could be true. This implies that there was a mistake in our assumptions somewhere, which implies that our mistake was either in assuming that $B\in A$, or perhaps even further back in assuming that the set $B=\{x\in A~:~x\not\in x\}$ is actually a set.

note the following two facts:

($x\in C$ or $x\notin C$) is always true

($x\in C$ and $x\notin C$) is always false

  • $\begingroup$ Pardon me if this question is dumb but where is our mistake then, the first or the latter? $\endgroup$ – Damjan Babić Jan 20 '16 at 21:21
  • $\begingroup$ So long as $B$ is not an element of $A$, then there is no problem. Technically speaking, you will find that in ZFC, sets are never allowed to be elements of themselves. As such, this definition of $B=\{a\in A~:~a\not\in a\}$ makes it such that $B=A$ since $a\not\in a$ is a redundant statement. $\endgroup$ – JMoravitz Jan 20 '16 at 21:24
  • $\begingroup$ Done a quick google search of "ZFC" and found out what it means. How do I know which axiomatic system my book uses? Is there an official axiomatic system that is internationally accepted? $\endgroup$ – Damjan Babić Jan 20 '16 at 21:29
  • 1
    $\begingroup$ @JMoravitz The OP mentions that they are using Halmos' book Naive set theory; as the title suggests, there is no formal theory in the background. $\endgroup$ – Noah Schweber Jan 20 '16 at 21:48
  • 1
    $\begingroup$ @JMoravitz That's true, but my recollection is that the early parts of Halmos work without a fixed background theory. $\endgroup$ – Noah Schweber Jan 20 '16 at 21:51

Remember the definition of $B$: $$x\in B\iff x\in A\mbox{ and } x\not\in x.$$ So by definition, $$B\in B\iff B\in A\mbox{ and } B\not\in B.$$ So if $B\in A$, then this means $$B\in B\iff B\not\in B.$$ Do you see why this is true?

  • $\begingroup$ Yes, I do. It never came to me to place $B$ in place of $y$. Thank you. $\endgroup$ – Damjan Babić Jan 20 '16 at 21:24

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.