Intersection Distributes over Symmetric Difference

From ProofWiki
Jump to navigation Jump to search

Theorem

Intersection is distributive over symmetric difference:

$\paren {R * S} \cap T = \paren {R \cap T} * \paren {S \cap T}$
$T \cap \paren {R * S} = \paren {T \cap R} * \paren {T \cap S}$


Proof

From Set Intersection Distributes over Set Difference, we have:

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


So:

\(\displaystyle \paren {R \cap T} * \paren {S \cap T}\) \(=\) \(\displaystyle \paren {\paren {R \cap T} \setminus \paren {S \cap T} } \cup \paren {\paren {S \cap T} \setminus \paren {R \cap T} }\) Definition of Symmetric Difference
\(\displaystyle \) \(=\) \(\displaystyle \paren {\paren {R \setminus S} \cap T} \cup \paren {\paren {S \setminus R} \cap T}\) Set Intersection Distributes over Set Difference
\(\displaystyle \) \(=\) \(\displaystyle \paren {\paren {R \setminus S} \cup \paren {S \setminus R} } \cap T\) Intersection Distributes over Union
\(\displaystyle \) \(=\) \(\displaystyle \paren {R * S} \cap T\) Definition of Symmetric Difference


The second part of the proof is a direct consequence of the fact that Intersection is Commutative.

$\blacksquare$


Sources