De Morgan's Laws (Set Theory)/Set Difference/Family of Sets/Difference with Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ and $T$ be sets.

Let $\left\langle{T_i}\right\rangle_{i \mathop \in I}$ be a family of subsets of $T$.


Then:

$\displaystyle S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \left({S \setminus T_i}\right)$

where:

$\displaystyle \bigcup_{i \mathop \in I} T_i := \left\{{x: \exists i \in I: x \in T_i}\right\}$

that is, the Definition:Union of Family of $\left\langle{T_i}\right\rangle_{i \mathop \in I}$.


Proof

Suppose:

$\displaystyle x \in S \setminus \bigcap_{i \mathop \in I} T_i$

Note that by Set Difference is Subset we have that $x \in S$ (we need this later).

Then:

\(\displaystyle x\) \(\in\) \(\displaystyle S \setminus \bigcap_{i \mathop \in I} T_i\)
\(\displaystyle \iff \ \ \) \(\displaystyle x\) \(\notin\) \(\displaystyle \bigcap_{i \mathop \in I} T_i\) Definition of Set Difference
\(\displaystyle \iff \ \ \) \(\displaystyle \neg (\forall i \in I: x\) \(\in\) \(\displaystyle T_i)\) Definition of Intersection of Family
\(\displaystyle \iff \ \ \) \(\displaystyle \exists i \in I: \neg (x\) \(\in\) \(\displaystyle T_i)\) De Morgan's Laws (Predicate Logic)
\(\displaystyle \iff \ \ \) \(\displaystyle \exists i \in I: x\) \(\in\) \(\displaystyle S \setminus T_i\) Definition of Set Difference: note $x \in S$ from above
\(\displaystyle \iff \ \ \) \(\displaystyle x\) \(\in\) \(\displaystyle \bigcup_{i \mathop \in I} \left({S \setminus T_i}\right)\) Definition of Union of Family


Therefore:

$\displaystyle S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \left({S \setminus T_i}\right)$

$\blacksquare$


Source of Name

This entry was named for Augustus De Morgan.


Sources