# Nothing contains everything

"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

• Pardon me if this question is dumb but where is our mistake then, the first or the latter? – Damjan Babić Jan 20 '16 at 21:21
• 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. – JMoravitz Jan 20 '16 at 21:24
• 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? – Damjan Babić Jan 20 '16 at 21:29
• @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. – Noah Schweber Jan 20 '16 at 21:48
• @JMoravitz That's true, but my recollection is that the early parts of Halmos work without a fixed background theory. – 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?

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