Union of Symmetric Differences

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $R, S, T$ be sets.


Then:

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

where $R * S$ denotes the symmetric difference between $R$ and $S$.


Proof

From the definition of symmetric difference, we have:

$R * S = \left({R \setminus S}\right) \cup \left({S \setminus R}\right)$


Thus, expanding:

\(\displaystyle \left({R * S}\right) \cup \left({S * T}\right)\) \(=\) \(\displaystyle \left({R \setminus S}\right) \cup \left({S \setminus R}\right) \cup \left({S \setminus T}\right) \cup \left({T \setminus S}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({R \setminus S}\right) \cup \left({T \setminus S}\right) }\right) \cup \left({\left({S \setminus R}\right) \cup \left({S \setminus T}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({R \cup T}\right) \setminus S}\right) \cup \left({\left({S \setminus R}\right) \cup \left({S \setminus T}\right)}\right)\) Set Difference is Right Distributive over Union
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({R \cup T}\right) \setminus S}\right) \cup \left({S \setminus \left({R \cap T}\right)}\right)\) De Morgan's Laws: Difference with Intersection
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({R \cup S \cup T}\right) \setminus S}\right) \cup \left({S \setminus \left({R \cap T}\right)}\right)\) Set Difference with Union is Set Difference
\(\displaystyle \) \(=\) \(\displaystyle \left({R \cup S \cup T}\right) \setminus \left({R \cap S \cap T}\right)\) De Morgan's Laws for Difference with Intersection: Corollary

$\blacksquare$


Sources