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

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.


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

$\blacksquare$