Union as Symmetric Difference with Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ and $B$ be sets.

Then:

$A \cup B = \left({A * B}\right) * \left({A \cap B}\right)$

where:

$A \cup B$ denotes set union
$A \cap B$ denotes set intersection
$A * B$ denotes set symmetric difference


Proof

From the definition of symmetric difference:

$\left({A * B}\right) * \left({A \cap B}\right) = \left({\left({A * B}\right) \cup \left({A \cap B}\right)}\right) \setminus \left({\left({A * B}\right) \cap \left({A \cap B}\right)}\right)$

Also from the definition of Symmetric Difference:

$\left({A * B}\right) \cap \left({A \cap B}\right) = \left({\left({A \cup B}\right) \setminus \left({A \cap B}\right)}\right) \cap \left({A \cup B}\right)$

From Set Difference Intersection with Second Set is Empty Set:

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

Hence:

$\left({\left({A \cup B}\right) \setminus \left({A \cup B}\right)}\right) \cap \left({A \cup B}\right) = \varnothing$


This leaves:

\(\displaystyle \) \(\) \(\displaystyle \left({\left({A * B}\right) \cup \left({A \cap B}\right)}\right) \setminus \left({\left({A * B}\right) \cap \left({A \cap B}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({A * B}\right) \cup \left({A \cap B}\right)}\right) \setminus \varnothing\)
\(\displaystyle \) \(=\) \(\displaystyle \left({A * B}\right) \cup \left({A \cap B}\right)\) Set Difference with Empty Set is Self

Then:

\(\displaystyle \) \(\) \(\displaystyle \left({A * B}\right) \cup \left({A \cap B}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({A \setminus B}\right) \cup \left({B \setminus A}\right) \cup \left({A \cap B}\right)\) Definition 1 of Symmetric Difference
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({A \setminus B}\right) \cup \left({A \cap B}\right)}\right) \cup \left({\left({B \setminus A}\right) \cup \left({A \cap B}\right)}\right)\) Union is Idempotent, Union is Commutative and Union is Associative
\(\displaystyle \) \(=\) \(\displaystyle A \cup B\) Set Difference Union Intersection


Hence the result.

$\blacksquare$