Set Difference Union Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof 1

\(\displaystyle \paren {S \setminus T} \cup \paren {S \cap T}\) \(=\) \(\displaystyle \paren {\paren {S \setminus T} \cup S} \cap \paren {\paren {S \setminus T} \cup T}\) Union Distributes over Intersection
\(\displaystyle \) \(=\) \(\displaystyle S \cap \paren {\paren {S \setminus T} \cup T}\) Set Difference Union First Set is First Set
\(\displaystyle \) \(=\) \(\displaystyle S \cap \paren {S \cup T}\) Set Difference Union Second Set is Union
\(\displaystyle \) \(=\) \(\displaystyle S\) Intersection Absorbs Union

$\blacksquare$


Proof 2

\(\displaystyle \left({S \setminus T}\right) \cup \left({S \cap T}\right)\) \(=\) \(\displaystyle S \setminus \left({T \setminus T}\right)\) Set Difference with Set Difference is Union of Set Difference with Intersection
\(\displaystyle \) \(=\) \(\displaystyle S \setminus \varnothing\) Set Difference with Self is Empty Set
\(\displaystyle \) \(=\) \(\displaystyle S\) Set Difference with Empty Set is Self

$\blacksquare$


Proof 3

By Set Difference is Subset:

$S \setminus T \subseteq S$

By Intersection is Subset:

$S \cap T \subseteq S$

Hence from Union is Smallest Superset:

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


Let $s \in S$.

Either:

$s \in T$, in which case $s \in S \cap T$ by definition of set intersection

or

$s \notin T$, in which case $s \in S \setminus T$ by definition of set difference.

That is, $s \in \left({S \setminus T}\right) \cup \left({S \cap T}\right)$ by definition of set union, and so $S \subseteq \left({S \setminus T}\right) \cup \left({S \cap T}\right)$.


Hence the result by definition of set equality.

$\blacksquare$


Sources