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 \paren {S \setminus T} = \paren {R \setminus S} \cup \paren {R \cap T}$

where:

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


Corollary

$T \setminus \paren {S \setminus T} = T$


Proof

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


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

$\blacksquare$


Sources