On pp. 6-7 of his Naive Set Theory, Paul Halmos proves a result that I know very well, but I have a hard time following the argument he gives here. This question is about Halmos' argument (and not about the result itself, which I understand well enough).

I'll quote Halmos at length to make sure I don't miss anything. (I'll be as faithful as possible, but I will change his notation slightly, since he uses $\epsilon$ for $\in$, and $\epsilon^\prime$ for $\notin$; I will stick to $\in$ and $\notin$). The excerpt below begins right after he has given the Axiom of specification. (In the excerpt, I'll use boldface to indicate what I'm having trouble with.)

...To indicate the way $B$ is obtained from $A$ and from $S(x)$ it is customary to write $$B = \{x \in A:S(x)\}$$

To obtain an amusing and instructive application of the axiom of specification, consider, in the role of $S(x)$, the sentence $$\mathrm{not}\;(x \in x).$$

It will be convenient, here and throughout, to write $``x \notin A"$ ... instead of $``\mathrm{not}\;(x \in A)"$; in this notation, the role of $S(x)$ is now played by $$x \notin x.$$

It follows that, whatever the set $A$ may be, if $B = \{x\in A:x\notin x\}$, then for all $y$, $$(*)\;\;\;\;\;y\in B\text{ if and only if } (y\in A\text{ 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 imposssible), 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. This completes the proof that $B\in A$ is impossible, so we must have $B\notin A$.

(In the subsequent discussion, Halmos argues that this result means that "there is no universe [of discourse]", etc., etc.)

Now, this is what I don't get. If I replace $y$ with $B$ in $(*)$, I get

$$B\in B \text{ if and only if } (B\in A\text{ and } B\notin B).$$

This means that $B\in B$ and $(*)$ together imply $B\notin B$. Contrary to what Halmos writes, "the assumption $B\in A$" is not needed to draw this conclusion.

What am I missing?

(By the way, I would have worded the second part of the proof a bit differently, namely:

If $B\notin B$, then, by $(*)$ again, the assumptions $B\in A$ and $B\notin B$ jointly imply that $B\in B$.

I mention this only in case this rewording gives a clue about where my confusion lies.)

  • $\begingroup$ There is rigor and clarity lost when you write $x\in x$ as $x$ is both a set and an element of the set, so there is an ambiguity of what $x$ is describing in any instance. This is a linguistic ambiguity, and an equivocation of two completely different notions. In my view. $\endgroup$ – CogitoErgoCogitoSum May 18 '18 at 17:37
  • 3
    $\begingroup$ @CogitoErgoCogitoSum: The very point of this argument is that $x$ is the same thing on both sides -- we're asking whether the set presently being called $x$ is an element of itself. $\endgroup$ – Henning Makholm May 18 '18 at 17:45

You are right that the appeal to $B\in A$ in the bolded part of your quote is not necessary for the conclusion it's trying to draw.

I'd chalk it up to sloppy editing and move on.


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.