1
$\begingroup$

This is Velleman's exercise 3.4.20.a:

Suppose $F$ and $G$ are families of sets. Prove that $(\bigcup F) \setminus (\bigcup G) \subseteq \bigcup (F \setminus G)$.

This is my proof but I'm suspicious of it being correct:

Proof. Suppose $x$ is an arbitrary element of $(\bigcup F) \setminus (\bigcup G)$. Therefore we can choose some $A \in F$ such that $x \in A$. And for all A ∈ G, x ∉ A. Now suppose ∀A ∈ F\G(x ∉ A). Thus whether A ∈ G or A ∉ G we get x ∉ A which is a contradiction. Therefore ∃A ∈ F\G(x ∈ A). Since x was arbitrary, $(\bigcup F) \setminus (\bigcup G) \subseteq \bigcup (F \setminus G)$.

Please tell me if my proof is wrong plus how to fix it (preferably write a proof in Velleman's expository style).

Thanks in advance.

$\endgroup$
  • $\begingroup$ The notation here is somewhat awkward. When you write $\cup F$, is $F$ what you are indexing over or is it a representative set. Some possible alternatives: $\bigcup_{A\in F}A$ or $\bigcup_{i\in I}F_i$. $\endgroup$ – Michael Burr Aug 17 '17 at 17:37
  • $\begingroup$ It's the exact notation used by the book! ⋃F means the union of the family of sets F i.e. {x | ∃A ∈ F(x ∈ A)}. $\endgroup$ – Heptapod Aug 17 '17 at 17:39
  • $\begingroup$ Which I think it would be the first alternative that you mentioned. $\endgroup$ – Heptapod Aug 17 '17 at 17:45
  • $\begingroup$ Proof. Let $x \in \cup F / \cup G$ be arbitrary, and let $A$ be an element of $F$ containing $x$ It follows that $x \notin \cup G$ and thus forall $B \in G$, we have $x \notin B$. It follows that $A \in (F / G) $ and thus $x \in \cup (F / G) $ $\endgroup$ – mm8511 Aug 17 '17 at 17:52
0
$\begingroup$

You fixed $A$ earlier in the argument, but then proceeded to use the symbol $A$ to stand for an arbitrary element in $G$. You should use a different letter. Also, I don't understand the line "Thus whether $A\in G$ or $A\not\in G$ we get $x\not\in A$ which is a contradiction." Are you saying that $x\not\in A$ for all $A\not\in G$?

Here's how I would go about the proof:

Suppose $x\in(\cup F)\setminus(\cup G)$. Then $x\in\cup F$, so there exists $A\in F$ satisfying $x\in A$. Since $x\not\in\cup G$ and $x\in A$, we know that $A\not\in G$. Therefore $A\in F\setminus G$, which implies that $x\in A \subseteq \cup (F\setminus G)$. $\square$

I know you're following the notation of your textbook, but I would much prefer to use $\mathscr{F}$ and $\mathscr{G}$ instead of $F$ and $G$. The psychological difference between using script letters for sets of sets, capital letters for sets of elements, and lower case letters for elements is helpful. (Even though, technically, everything is a set.) Then it would read:

Given families of sets $\mathscr{F}$ and $\mathscr{G}$, we have $(\cup\mathscr{F})\setminus(\cup\mathscr{G}) \subseteq \cup(\mathscr{F}\setminus\mathscr{G})$.

Proof:

Suppose $x\in(\cup \mathscr{F})\setminus(\cup \mathscr{G})$. Then $x\in\cup\mathscr{F}$, so there exists $F\in\mathscr{F}$ satisfying $x\in F$. Since $x\not\in\cup\mathscr{G}$ and $x\in F$, we know that $F\not\in\mathscr{G}$. Therefore $F\in \mathscr{F}\setminus\mathscr{G}$, which implies that $x\in F \subseteq \cup (\mathscr{F}\setminus\mathscr{G})$. $\square$

$\endgroup$
  • $\begingroup$ "Thus whether A∈G or A∉G we get x∉A which is a contradiction" was very wrong of me! That happened because I used the same symbol...! Could you please tell me what's wrong with the proof in below: Suppose x ∈ ∪(F \ G). Then we can choose some A ∈ F \ G such that x ∈ A. Since A ∈ F \ G, A ∈ F and A ∈/ G. Since x ∈ A and A ∈ F, x ∈ ∪F. Since x ∈ A and A ∈/ G, x ∈ ∪ / G. Therefore x ∈ (∪F) \ (∪G). $\endgroup$ – Heptapod Aug 17 '17 at 17:53
  • $\begingroup$ The proof given above is for this: ∪(F \ G) ⊆ (∪F)(∪G). $\endgroup$ – Heptapod Aug 17 '17 at 17:55
  • $\begingroup$ @Heptapod I'm happy to help! That proof is correct until you say "Since $x\in A$ and $A\not\in G$, then $x\not\in \cup G$". This is a false statement. The reason you're having trouble here is that you're trying to prove something that's false. Consider $F=\{(0,2)\}$ and $G=\{\{1\}\}$. Then $F\setminus G=\{(0,2)\}$, so $1\in (0,2)=\cup(F\setminus G)$. However $1\in \{1\}=\cup G$ as well. Thus $x\not\in(\cup F)\setminus(\cup G)$ because $(\cup F)\setminus(\cup G)=(0,2)\setminus\{1\}=(0,1)\cup(1,2)$. $\endgroup$ – John Griffin Aug 17 '17 at 18:01
  • $\begingroup$ I can see it now, that's great! I'm self-studying the book so your help means a lot to me. Thanks again. $\endgroup$ – Heptapod Aug 17 '17 at 18:06

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.