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

\(\displaystyle \left({R \cap T}\right) \setminus \left({S \cap T}\right)\) \(=\) \(\displaystyle \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
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({R \cap T}\right) \setminus S}\right) \cup \varnothing\) Set Difference of Intersection with Set is Empty Set
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cap T}\right) \setminus S\) Union with Empty Set
\(\displaystyle \) \(=\) \(\displaystyle \left({R \setminus S}\right) \cap T\) Intersection with Set Difference is Set Difference with Intersection

$\Box$


Then:

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

$\blacksquare$


Sources