Set Difference with Union

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R, S, T$ be sets.


Then:

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

where:

$R \setminus S$ denotes set difference
$R \cup T$ denotes set union.


Proof

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


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

$\Box$


Then:

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

$\Box$


Then:

\(\displaystyle R \setminus \paren {S \cup T}\) \(=\) \(\displaystyle R \setminus \paren {T \cup S}\) Union is Commutative
\(\displaystyle \) \(=\) \(\displaystyle \paren {R \setminus T} \setminus S\) from above

$\blacksquare$


Sources