3

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.

Git Gud
  • 31,356
Dave Clifford
  • 999
  • Why the down vote? – Git Gud Jan 15 '14 at 10:07
  • 1
    I partially reformatted your question to $\LaTeX$. You should be able to adapt the parts I edited to fix the rest of your question. – Git Gud Jan 15 '14 at 10:12
  • You did not make a mistake. – drhab Jan 15 '14 at 10:14
  • @drhab Do you mean that my reasoning below is wrong? Can you explain? thanks! – Dave Clifford Jan 15 '14 at 10:15
  • This isn't a duplicate, but it answers your problem. – Git Gud Jan 15 '14 at 10:18
  • 1
    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! – drhab Jan 15 '14 at 10:20
  • @drhab I left out a universal quantifier while stating x∈A, which confused myself. Thanks for pointing it out! – Dave Clifford Jan 15 '14 at 10:38

1 Answers1

2

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\;$.

MarnixKlooster ReinstateMonica
  • 5,576