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!

  • 2
    $\begingroup$ "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.$$ $\endgroup$ – Daniel Fischer May 28 '16 at 12:05
  • $\begingroup$ 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$? $\endgroup$ – Daniel Mak May 28 '16 at 15:39
  • 1
    $\begingroup$ @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". $\endgroup$ – Henning Makholm May 28 '16 at 16:36
  • $\begingroup$ @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. $\endgroup$ – Daniel Mak May 28 '16 at 17:23

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.

  • $\begingroup$ 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 $\endgroup$ – Daniel Mak May 28 '16 at 15:34

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.