Set Difference is Subset of Union of Differences

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R, S, T$ be sets.


Then:

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

where:

$S \subseteq T$ denotes subset
$S \setminus T$ denotes set difference
$S \cup T$ denotes set union.


Proof

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


\(\displaystyle R \setminus S\) \(=\) \(\displaystyle R \cap \overline S\) Set Difference as Intersection with Complement
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cap \overline S}\right) \cap \mathbb U\) Intersection with Universe
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cap \overline S}\right) \cap \left({\overline T \cup T}\right)\) Union with Complement
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({T \cap R \cap \overline S}\right)\) Intersection Distributes over Union
\(\displaystyle \) \(\subseteq\) \(\displaystyle \left({R \cap \overline T}\right) \cup \left({T \cap \overline S}\right)\) Union of Intersections‎
\(\displaystyle \) \(=\) \(\displaystyle \left({R \setminus T}\right) \cup \left({T \setminus S}\right)\) Set Difference as Intersection with Complement

$\blacksquare$