Symmetric Difference is Associative/Proof 1
Jump to navigation
Jump to search
Theorem
Symmetric difference is associative:
- $R \symdif \paren {S \symdif T} = \paren {R \symdif S} \symdif T$
Proof
We can directly expand the expressions for $R \symdif \paren {S \symdif T}$ and $\paren {R \symdif S} \symdif T$, and see that they come to the same thing.
Expanding the right hand side:
| \(\ds \) | \(\) | \(\ds \paren {R \symdif S} \symdif T\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {\paren {R \cap \overline S} \cup \paren {\overline R \cap S} } \cap \overline T} \cup \paren {\overline {R \symdif S} \cap T}\) | Definition 3 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {\paren {\paren {R \cap \overline S} \cup \paren {\overline R \cap S} } \cap \overline T} \cup \paren {\overline {\paren {\paren {R \cup S} \cap \paren {\overline R \cup \overline S} } } \cap T}\) | Definition 4 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline S \cap \overline T} \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\paren {\overline {\paren {R \cup S} } \cup \overline {\paren {\overline R \cup \overline S} } } \cap T}\) | Intersection Distributes over Union and De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline S \cap \overline T} \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\paren {\paren {\overline R \cap \overline S} \cup \paren {R \cap S} } \cap T}\) | De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline S \cap \overline T} \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\overline R \cap \overline S \cap T} \cup \paren {R \cap S \cap T}\) | Intersection Distributes over Union |
Expanding the left hand side:
| \(\ds \) | \(\) | \(\ds R \symdif \paren {S \symdif T}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline {S \symdif T} } \cup \paren {\overline R \cap \paren {\paren {S \cap \overline T} \cup \paren {\overline S \cap T} } }\) | Definition 3 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline {\paren {\paren {S \cup T} \cap \paren {\overline S \cup \overline T} } } } \cup \paren {\overline R \cap \paren {\paren {S \cap \overline T} \cup \paren {\overline S \cap T} } }\) | Definition 4 of Symmetric Difference | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \paren {\overline {\paren {S \cup T} } \cup \overline {\paren {\overline S \cup \overline T} } } } \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\overline R \cap \overline S \cap T}\) | Intersection Distributes over Union and De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \paren {\paren {\overline S \cap \overline T} \cup \paren {S \cap T} } } \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\overline R \cap \overline S \cap T}\) | De Morgan | |||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {R \cap \overline S \cap \overline T} \cup \paren {R \cap S \cap T} \cup \paren {\overline R \cap S \cap \overline T} \cup \paren {\overline R \cap \overline S \cap T}\) | Intersection Distributes over Union |
From Union is Commutative it is seen that the left hand side and right hand side are the same, and the result is proved.
$\blacksquare$