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

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S, T_1, T_2$ be sets.


Then:

$S \setminus \paren {T_1 \cap T_2} = \paren {S \setminus T_1} \cup \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-Intersection.png



Corollary

Suppose that $T_1 \subseteq S$.


Then:

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


Proof

\(\ds \) \(\) \(\ds x \in S \setminus \paren {T_1 \cap T_2}\)
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {x \notin \paren {T_1 \cap T_2} }\) Definition of Set Difference
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {\neg \paren {x \in T_1 \land x \in T_2} }\) Definition of Set Intersection
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S} \land \paren {x \notin T_1 \lor x \notin T_2}\) De Morgan's Laws: Disjunction of Negations
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in S \land x \notin T_1}) \lor \paren {x \in S \land x \notin T_2}\) Rule of Distribution
\(\ds \) \(\leadstoandfrom\) \(\ds x \in \paren {S \setminus T_1} \cup \paren {S \setminus T_2}\) Definition of Set Union and Definition of Set Difference

By definition of set equality:

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

$\blacksquare$


Source of Name

This entry was named for Augustus De Morgan.


Sources