# Proving union of family set

I am having trouble with the following exercise in Velleman's How To Prove This:

Suppose B is a set and $\mathscr F$ is a family of sets. Prove that $\bigcup\{A\setminus B|A\in \mathscr F\}\subseteq\bigcup(\mathscr F\setminus\mathscr P(B))$, where $\mathscr P$ is a power set.

My attempt: Let x be an arbitrary element, let's assume $x\in\bigcup\{A\setminus B|A\in \mathscr F\}$. It becomes $\exists A(x\in A \land\sim x\in B\land A\in \mathscr F)$; which breaks down to this after existentiating A to D:$$x\in D\land\sim x\in B\land D\in \mathscr F$$ At this point it cannot be broken down any further, so let's look at the conclusion. But this is where I am not sure, it seems that the $\bigcup(\mathscr F\setminus\mathscr P(B))$ is equivalent to :$$\exists C(C\in \mathscr F\land x\in C\land \sim x\subseteq B)$$The 'minus powerset of B' really obstructed me from being sure what this set means; but from the symbols this seems to be what it is saying.

If I am right, it seems that my attempt is almost correct; as one can existential generalise D to C to get $\exists C(C\in \mathscr F\land x\in C\land \sim x\in B)$, but I just can't get $\sim x\subseteq B$ however I tried.

I did find an unofficial solution, but it is equally confusing:

Let x be an arbitrary element of $\bigcup\{A\setminus B|A\in \mathscr F\}$. It follows that there exists a set $a\in \mathscr F$ s.t. $x\in a \setminus B$. Moreover, $\sim (a\subseteq B)$ is true otherwise $a \setminus B$ will be empty. Since $\sim (a\subseteq B)$, so $a\notin \mathscr P(B)$. Since $a\in \mathscr F$ and $a\notin \mathscr P(B)$, so $a\in F\setminus\mathscr P(B)$ and hence $x\in \bigcup \mathscr F\setminus\mathscr P(B)$.

I think he should have said 'there exists SOME set $a\in \mathscr F$ s.t. $x\in a \setminus B$, i.e. an existential generalization, but this is not my biggest confusion.

It is how he jumped from $a\in F\setminus\mathscr P(B)$ to $x\in \bigcup \mathscr F\setminus\mathscr P(B)$. This step doesn't seem justified and I don't see what step did he take. Besides, I am still not quite sure what the logical form of the conclusion is, and this solution doesn't make it any clearer.

Would anyone mind helping me please? Thank you so much!

• "There exists a set …" is completely equivalent to "there exists some set …". Note that $$\bigcup (\mathscr{F}\setminus \mathscr{P}(B)) = \bigcup_{\substack{C \in \mathscr{F} \\ C \not \subset B}} C.$$ – Daniel Fischer May 28 '16 at 12:05
• Sorry you are right, I should have said 'there exists at least one set'. Because surely while 'there exists at least one set' implies 'there exists a set', the latter does not imply the former, and only the former should be the correct definition of $\exists$? – Daniel Mak May 28 '16 at 15:39
• @DanielMak: In mathematical English, the phrasings "there exists a set", "there exists some set" and "there exists at least one set" all mean exactly the same thing -- there's no difference in meaning encoded by them. If you want to say that there exists one and only one one thing with such-and-such property, you're supposed to expresse it as for example "there exists exactly one set" or "there exists a unique set". – Henning Makholm May 28 '16 at 16:36
• @HenningMakholm Sorry my bad, I thought 'there exists a set' does not imply 'there exists at least one set', because the former will not allow more than one set while the latter does; but then I realise even if there is more than one set 'there exists a set' is still true so I was wrong. – Daniel Mak May 28 '16 at 17:23

## 1 Answer

Your unfolding of $x\in \bigcup(\mathscr F\setminus\mathcal P(B))$ is wrong -- it should be $$\exists C\in\mathscr F : C\notin\mathcal P(B) \land x\in C$$ which is the same as $$\exists C \in\mathscr F : C\not\subseteq B \land x\in C$$ Note that this has $C\not\subseteq B$ where you wrote $x\not\subseteq B$.

And this is easy to establish for the $D$ you already know: Tou know that $x\in D$ and $x\notin B$. This implies by definition that $D\not\subseteq B$.

What you wrote would be right for $(\bigcup \mathscr F)\setminus \mathcal P(B)$, but that has different parentheses from your actual goal.

• Thank you so much! I can't believe I didn't realise my attempt has already implied $D\not\subseteq B$, if I did I may have at least suspected that the conclusion should have been $C \not\subseteq B$ instead – Daniel Mak May 28 '16 at 15:34