De Morgan's Laws (Set Theory)/Set Difference/Difference with Union

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S, T_1, T_2$ be sets.


Then:

$S \setminus \paren {T_1 \cup T_2} = \paren {S \setminus T_1} \cap \paren {S \setminus T_2}$

where:

$T_1 \cap T_2$ denotes set intersection
$T_1 \cup T_2$ denotes set union.


Illustration by Venn Diagram

DeMorgan-Minus-Union.png


Proof

\(\ds \) \(\) \(\ds x \in S \setminus \paren {T_1 \cup T_2}\)
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {x \notin \paren {T_1 \cup T_2} }\) Definition of Set Difference
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {\neg \paren {x \in T_1 \lor x \in T_2} }\) Definition of Set Union
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {x \notin T_1 \land x \notin T_2}\) De Morgan's Laws: Conjunction of Negations
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S \land x \notin T_1} \land \paren {x \in S \land x \notin T_2}\) Rules of Idempotence, Commutation and Association
\(\ds \) \(\leadstoandfrom\) \(\ds x \in \paren {S \setminus T_1} \cap \paren {S \setminus T_2}\) Definition of Set Intersection and Definition of Set Difference

By definition of set equality:

$S \setminus \paren {T_1 \cup T_2} = \paren {S \setminus T_1} \cap \paren {S \setminus T_2}$

$\blacksquare$


Source of Name

This entry was named for Augustus De Morgan.


Sources