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

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.

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.