# Meaning of equation (*) in Section 2 page 6 of Naive Set Theory by Paul Halmos

I made it through the first section fine, but I am stuck on section 2 The Axiom of Specification. Particularly the last paragraph that asks

Can it be that $$B\in A$$ ?

The axiom defines $$A$$ as:

Axiom of specification: To every set $$A$$ and to every condition $$S(x)$$ there corresponds a set $$B$$ whose elements are exactly those elements $$x$$ of $$A$$ for which $$S(x)$$ holds

$$B$$ is defined as:

$$B = \{ x \in A : S(x) \}$$

If we consider $$S(x) = x \notin x$$

then $$B = \{ x \in A : x \notin x \}$$ He claims it follows that: note this is equation (*) but that wasn't rendering in the quote so I changed it to (1)

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

The final conclusion is:

If $$B \in B$$ then by (1) the assumption $$B \in A$$ yields $$B \notin B$$ - a contradiction. If $$B \notin B$$ then by (1) again the assumption $$B \in A$$ yields $$B \in B$$ - contradtion again. This completes the proof that $$B \in A$$ is impossible, so that we must have $$B \notin A$$.

I don't understand why if we are considering $$B \in A$$ why the $$S(x)$$ part matters in the proof. Or put another way why if $$B \in A$$ it must be the case that $$B \notin B$$?

• Does (1) really say "$(y \in A : y \notin y)$"? That's not standard notation. – Eric Wofsey Oct 27 '18 at 23:47
• In any case, it's unclear to me what part of the proof you don't understand. Is it just the first sentence of the "final conclusion" paragraph that you don't understand? – Eric Wofsey Oct 27 '18 at 23:58
• @EricWofsey sorry that was a typo in (1) I updated it. It should have been and not :. The part I don't understand is why if we are considering, B is an element of A, how B is an element of B fits into that. – achyrd Oct 28 '18 at 0:07

(i). Assume $$B\in A.$$ Then $$B$$ is either a member of $$A$$ that belongs to itself or a member of $$A$$ that doesn't belong to itself.

Now (I). Suppose $$B\not \in B.$$ Then $$B$$ is a member of $$A$$ that doesn't belong to itself, so it satisfies the sufficient conditions for membership in $$B.$$ So it belongs to $$B$$. So $$B\in B.$$

And (II). Suppose $$B\in B.$$ Then $$B$$ is a member of A that belongs to itself, so it does not satisfy the necessary conditions for membership in $$B.$$ So it does not belong to $$B$$. So $$B \not\in B.$$

(ii). So we find that $$B\in A\implies [B\not \in B\iff B\in B].$$ We conclude that either $$B$$ doesn't exist or $$B \not \in A.$$ And we know that $$B$$ exists.

• So Specification (a.k.a. Comprehension ) implies that every $A$ has a sub$set$ $B$ that is not a member or $A$. Note this is different from Foundation, which asserts that every non-empty $A$ has a $member$ $a$ which is disjoint from $A.$ – DanielWainfleet Oct 28 '18 at 5:55
• Thanks I tried to upvote, but I don't have the rep. This breakdown was helpful – achyrd Oct 28 '18 at 18:05
• On re-reading the last part of my answer, I noticed that if $B$ doesn't exist then we still have $B\not \in A$...... In the absence of Comprehension we could say that IF $B$ exists then $B\not \in A$. – DanielWainfleet Oct 31 '18 at 16:26

That proof is hard to follow. Note:
$$y\notin B$$ $$\iff$$ $$y\notin A$$ or $$y\in y$$.

Since $$B \notin B$$ has been established,
from the above: $$B \notin A$$ or $$B \in B$$.

By the axiom of foundations, $$A = B$$.