Set Difference with Set Difference is Union of Set Difference with Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R, S, T$ be sets.


Then:

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

where:

$S \setminus T$ denotes set difference
$S \cup T$ denotes set union
$S \cap T$ denotes set intersection.


Proof

Consider $R, S, T \subseteq \mathbb U$, where $\mathbb U$ is considered as the universe.


\(\displaystyle R \setminus \left({S \setminus T}\right)\) \(=\) \(\displaystyle R \cap \overline {\left({S \cap \overline T}\right)}\) Set Difference as Intersection with Complement
\(\displaystyle \) \(=\) \(\displaystyle R \cap \left({\overline S \cup \overline {\left({\overline T}\right)} }\right)\) De Morgan's Laws
\(\displaystyle \) \(=\) \(\displaystyle R \cap \left({\overline S \cup T}\right)\) Complement of Complement
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cap \overline S}\right) \cup \left({R \cap T}\right)\) Intersection Distributes over Union
\(\displaystyle \) \(=\) \(\displaystyle \left({R \setminus S}\right) \cup \left({R \cap T}\right)\) Set Difference as Intersection with Complement

$\blacksquare$


Sources