Set Intersection Distributes over Set Difference

From ProofWiki
Jump to navigation Jump to search

Theorem

Set intersection is distributive over set difference.


Let $R, S, T$ be sets.


Then:

$\left({R \setminus S}\right) \cap T = \left({R \cap T}\right) \setminus \left({S \cap T}\right)$
$R \cap \left({S \setminus T}\right) = \left({R \cap S}\right) \setminus \left({R \cap T}\right)$

where:

$R \setminus S$ denotes set difference
$R \cap T$ denotes set intersection.


Proof

\(\ds \left({R \cap T}\right) \setminus \left({S \cap T}\right)\) \(=\) \(\ds \left({\left({R \cap T}\right) \setminus S}\right) \cup \left({\left({R \cap T}\right) \setminus T}\right)\) De Morgan's Laws: Difference with Intersection
\(\ds \) \(=\) \(\ds \left({\left({R \cap T}\right) \setminus S}\right) \cup \varnothing\) Set Difference of Intersection with Set is Empty Set
\(\ds \) \(=\) \(\ds \left({R \cap T}\right) \setminus S\) Union with Empty Set
\(\ds \) \(=\) \(\ds \left({R \setminus S}\right) \cap T\) Intersection with Set Difference is Set Difference with Intersection

$\Box$


Then:

\(\ds R \cap \left({S \setminus T}\right)\) \(=\) \(\ds \left({S \setminus T}\right) \cap R\) Intersection is Commutative
\(\ds \) \(=\) \(\ds \left({S \cap R}\right) \setminus \left({T \cap R}\right)\) from above
\(\ds \) \(=\) \(\ds \left({R \cap S}\right) \setminus \left({R \cap T}\right)\) Intersection is Commutative

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Set_Intersection_Distributes_over_Set_Difference&oldid=353144"