# Why does this proof work?

In "Naive Set Theory" of Halmos (page 15) there is a claim that

for each collection $\mathcal{C}$, other than $\emptyset$, there exists a set $V$ such that $x \in V \text{ if and only if } x \in X$ for every $X$ in $\mathcal{C}$

To prove this assertions the author writes

$V = \{ x \in A: x \in X\text{ for every }X \in \mathcal{C}\}$

where $A$ is any particular set in $\mathcal{C}$ and says that

the dependence of $V$ on the artbitrary choice of $A$ is illusory, in fact $V = \{ x: x \in X\text{ for every }X \in \mathcal{C}\}$

Can someone explain me why the dependence on $A$ is illusory? And what is the point of writing it then? As I understand the author proves this due to the axiom of specification, though I can't understand how author just takes arbitrary collection and creates a set $A$ in it that "suddenly" contains elements defined by specification ($x \in X\text{ for every }X \in \mathcal{C}$), as I can show a lot of collections that don't have such set as an element. But the claim about illusion of dependence totally confused me. Please, clarify this for me. I will be very glad to hear any help or hints. Thanks in advance.

• If $x \in X$ for every $X \in \mathcal C$ and $A$ is an element whatever of $\mathcal C$, obviously $x \in A$. As you said, $A$ is needed by Specification ($\mathcal C$ is a collection, and thus not necessarily a set). – Mauro ALLEGRANZA Nov 14 '17 at 16:51
• @MauroALLEGRANZA, can you elaborate the difference between collection and set if there is any? So the proof is just based on the axiom, right? And as $A$ is some set in $\mathcal{C}$, so there are elements that actually exist on which we can apply specification, as $A$ itself together with $\mathcal{C}$ exist, right? And it is enough to define subset $V$ by applying specification on the existing set? If it so, anyway, I can't then understand why the author says that the dependence is illusory. What makes it illusory? Because in the second case elements are not elements of some existing set. – Turkhan Badalov Nov 14 '17 at 17:00

It looks like you're misunderstanding the notation $$V = \{ x \in A: x \in X\text{ for every }X \in \mathcal{C}\}$$ when you write

I can't understand how author just takes arbitrary collection and creates a set $A$ in it that "suddenly" contains elements defined by specification ($x \in X\text{ for every }X \in \mathcal{C}$)

But the set builder notation does not create the set $A$ and it doesn't assert that the elements of $A$ are all the $x$ such that $x\in X$ for every $X\in\mathcal C$.

$V$ consists of exactly those elements of $A$ that satisfy $\forall X\in\mathcal C\;(x\in X)$.

This may end up being all of the elements in $A$, or none of them or some of them; that would just lead to $V$ becoming larger or smaller.

In any case, if there would happen to be an $x$ that satisfies $\forall X\in\mathcal C\;(x\in X)$ but is not in $A$, that $x$ would not become a member of $V$ either. (But in this particular case there cannot be such an $x$, because $A$ is one of the possible $X$ that $x$ must be a member of).

The meaning of the set builder is just an abbreviation for $$V = \{\; x \;\;:\;\; x \in A\text{ and }(x \in X\text{ for every }X \in \mathcal{C})\;\}$$

We write the condition $x\in A$ to the left of the colon simply to visually emphasize that the condition on $x$, "$x \in A\text{ and }(x \in X\text{ for every }X \in \mathcal{C})$" has the particular shape where the Axiom of Specification guarantees that $V$ will exist as a set.

Indeed since $A\in\mathcal C$ it is easy to prove $$x \in A\text{ and }(x \in X\text{ for every }X \in \mathcal{C}) \;\iff\; (x \in X\text{ for every }X \in \mathcal{C})$$ so the only reason to include the $x\in A$ condition at all is to make the Axiom of Specification happy, and the result will be the same no matter which of the sets in $\mathcal C$ we choose to use as $A$.

• "make the Axiom of Specification happy", ahah, thank you very much for the explanation. I really misunderstood the builder notation in this context. And the last part of explanation where you show the redundancy of the condition was really awesome. – Turkhan Badalov Nov 15 '17 at 8:10

The Axiom of Comprehension allows us to assert the existence of the set of all and only those members of a set A that have some specified property. So for any $A \in C$ we have $$\exists V_A=\{x\in A: \forall c\in C\;(x\in c)\}.$$ And since $C\ne \phi$ we have $$\exists A\in C\; \exists V_A=\{x\in A: \forall c\in C\;(x\in c)\}.$$ The "illusion of dependence" is that it seems that $V_A$ depends on $A,$ but in fact $$\forall A,B\in C\;(V_A=V_B=\{x\in C:\;\forall c\in C\;(x\in c)\}).$$

Comprehension is a substitute for the earlier, failed, Axiom of Abstraction (or Unlimited Comprehension) which asserts the existence of a set of all and only those things with a specified property, which is paradoxical. (E.g. Russell's Paradox.) In Comprehension we must first have a set $A,$ from which we can "extract" the set of members of $A$ that have some property.

Different authors use different names for it, such as Specification.

• Another example of "illusory dependence": Let $<$ be a well-order on a set $A.$ Then for $B\subset A$ the restriction of $<$ to $B$ is also a well-order. Proof: For $\phi\ne S\subset B,$ for any $s\in S$ ,let $s'=\{s\}\cup \{t\in S:t<s\}$ and let $M(s)=\min s',$ which exists because $\phi\ne s'\subset A.$ In fact it is easily shown that $\forall s_1,s_2\in S\;(\min s_1=\min s_2=\min S).$ – DanielWainfleet Nov 14 '17 at 19:21
• Did you mean $(x \in c)$ everywhere, instead of $(x \in C)$? – Turkhan Badalov Nov 15 '17 at 8:13
• Yes. Typos. Thanks. – DanielWainfleet Nov 15 '17 at 20:41