Difference of Unions is Subset of Union of Differences

From ProofWiki
Jump to: navigation, search

Theorem

Let $I$ be an indexing set.

Let $S_\alpha, T_\alpha$ be sets, for all $\alpha \in I$.


Then:

$\displaystyle \left({\bigcup_{\alpha \mathop \in I} S_\alpha}\right) \setminus \left({\bigcup_{\alpha \mathop \in I} T_\alpha}\right) \subseteq \bigcup_{\alpha \mathop \in I} \left({S_\alpha \setminus T_\alpha}\right)$

where $S_\alpha \setminus T_\alpha$ denotes set difference.


Proof

Let $\displaystyle x \in \left({\bigcup_{\alpha \mathop \in I} S_\alpha}\right) \setminus \left({\bigcup_{\alpha \mathop \in I} T_\alpha}\right)$.

Then by definition of set difference:

\(\displaystyle x\) \(\in\) \(\displaystyle \bigcup_{\alpha \mathop \in I} S_\alpha\) $\quad$ $\quad$
\(\displaystyle x\) \(\notin\) \(\displaystyle \bigcup_{\alpha \mathop \in I} T_\alpha\) $\quad$ $\quad$


By definition of set union, it follows that:

\(\displaystyle \exists \beta \in I: x\) \(\in\) \(\displaystyle S_\beta\) $\quad$ $\quad$
\(\displaystyle \neg \exists \beta \in I: x\) \(\in\) \(\displaystyle T_\beta\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \forall \beta \in I: x\) \(\notin\) \(\displaystyle T_\beta\) $\quad$ De Morgan's Laws (Predicate Logic) $\quad$

and so:

$\exists \beta \in I: x \in S_\beta \setminus T_\beta$


Hence:

$\displaystyle x \in \bigcup_{\alpha \mathop \in I} \left({S_\alpha \setminus T_\alpha}\right)$

by defintion of set union.

The result follows by definition of subset.

$\blacksquare$


Sources