Suppose $F$ and $G$ are families of sets. Suppose $x$ is an arbitrary element of $(\bigcup F)\setminus (\bigcup G)$.

It follows that $x\in \bigcup F$ and $x\not \in \bigcup G$.

Since x∈∪F, therefore there exists A∈F such that x∈A. (1)

Since x∉∪G, x can not be an element of any set in G.

Since x∈A, so A∉G.

Since A∈F and A∉G, so A∈F\G.

Since x∈A and A∈F\G, therefore x∈∪(F\G).

Since x is arbitrary, we can conclude that (∪F)\(∪G)⊆∪(F\G).

Above is my initial attempt on proving it. But starting from (1), I think I have made a mistake. Since the $x$ mentioned above is not an arbitrary element of the chosen $A\in F$, we cannot straightforward conclude that $A\not \in G$ since $x$ is only an arbitrary element of $\left(\bigcup F\right)\setminus \left(\bigcup G\right)$. Perhaps there exists some element in $A$ which is an element of some set in $G$. I am stuck here; I have absolutely no idea about solving it. Please help. Thanks in advance.

  • $\begingroup$ Why the down vote? $\endgroup$ – Git Gud Jan 15 '14 at 10:07
  • 1
    $\begingroup$ I partially reformatted your question to $\LaTeX$. You should be able to adapt the parts I edited to fix the rest of your question. $\endgroup$ – Git Gud Jan 15 '14 at 10:12
  • $\begingroup$ You did not make a mistake. $\endgroup$ – drhab Jan 15 '14 at 10:14
  • $\begingroup$ @drhab Do you mean that my reasoning below is wrong? Can you explain? thanks! $\endgroup$ – Dave Clifford Jan 15 '14 at 10:15
  • 1
    $\begingroup$ Frankly I don't fully understand your reasoning below. You start with an arbitrary $x\in\cup F/\cup G$ and manage to prove that $x\in\cup\left(F/G\right)$. We have $x\in A\in F$ for some $A$ and assumption $A\in G$ would lead to contradiction $x\in A\wedge x\notin A$. Then $x\in A\in F/G$. Perfect reasoning! $\endgroup$ – drhab Jan 15 '14 at 10:20

Just for fun, here is your own correct proof in a calculational format. This makes the $\bigcup$- quantifications explicit, which prevents mistakes.

For every $\;x\;$, \begin{align} & x \in (\bigcup F) \setminus (\bigcup G) \\ \equiv & \qquad \text{"definition of $\;\setminus\;$"} \\ & x \in \bigcup F \;\land\; x \not\in \bigcup G \\ \equiv & \qquad \text{"definition of $\;\bigcup\;$, twice"} \\ & \langle \exists A : x \in A : A \in F \rangle \;\land\; \lnot \langle \exists A : x \in A : A \in G \rangle \\ \equiv & \qquad \text{"logic: DeMorgan on right hand side"} \\ & \langle \exists A : x \in A : A \in F \rangle \;\land\; \langle \forall A : x \in A : A \not\in G \rangle \\ \equiv & \qquad \text{"logic: use right hand side in left hand side quantification"} \\ & \langle \exists A : x \in A : A \in F \land A \not\in G \rangle \;\land\; \langle \forall A : x \in A : A \not\in G \rangle \\ \Rightarrow & \qquad \text{"logic: weaken -- we don't need the right hand side anymore"} \\ & \langle \exists A : x \in A : A \in F \land A \not\in G \rangle \\ \equiv & \qquad \text{"definition of $\;\setminus\;$"} \\ & \langle \exists A : x \in A : A \in F \setminus G \rangle \\ \equiv & \qquad \text{"definition of $\;\bigcup\;$"} \\ & x \in \bigcup (F \setminus G) \\ \end{align} From this the theorem follows by the definition of $\;\subseteq\;$.

  • $\begingroup$ what does 'logic: weaken' mean? $\endgroup$ – Dave Clifford Jan 16 '14 at 11:31
  • 1
    $\begingroup$ @DaveClifford This uses the logic law $\;P \land Q \Rightarrow P\;$, and $\;P\;$ is a weaker statement than $\;P \land Q\;$. Related question: math.stackexchange.com/q/53708/11994. $\endgroup$ – Marnix Klooster Jan 16 '14 at 13:20

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.