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 $\family {T_i}_{i \mathop \in I}$ be a family of subsets of $T$.


Then:

$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$

where:

$\ds \bigcup_{i \mathop \in I} T_i := \set {x: \exists i \in I: x \in T_i}$

that is, the union of $\family {T_i}_{i \mathop \in I}$.


Proof

Suppose:

$\ds 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:

\(\ds x\) \(\in\) \(\ds S \setminus \bigcap_{i \mathop \in I} T_i\)
\(\ds \leadstoandfrom \ \ \) \(\ds x\) \(\notin\) \(\ds \bigcap_{i \mathop \in I} T_i\) Definition of Set Difference
\(\ds \leadstoandfrom \ \ \) \(\ds \neg \leftparen {\forall i \in I}: \, \) \(\ds x\) \(\in\) \(\ds \rightparen {T_i}\) Definition of Intersection of Family
\(\ds \leadstoandfrom \ \ \) \(\ds \exists i \in I: \, \) \(\ds x\) \(\notin\) \(\ds T_i\) Denial of Universality
\(\ds \leadstoandfrom \ \ \) \(\ds \exists i \in I: \, \) \(\ds x\) \(\in\) \(\ds S \setminus T_i\) Definition of Set Difference: note $x \in S$ from above
\(\ds \leadstoandfrom \ \ \) \(\ds x\) \(\in\) \(\ds \bigcup_{i \mathop \in I} \paren {S \setminus T_i}\) Definition of Union of Family


Therefore:

$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$

$\blacksquare$


Source of Name

This entry was named for Augustus De Morgan.


Sources