Symmetric Difference is Associative

From ProofWiki
Jump to navigation Jump to search

Theorem

Symmetric difference is associative:

$R \symdif \paren {S \symdif T} = \paren {R \symdif S} \symdif T$


Proof 1

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$


Proof 2

There is another way of doing this.


Expanding the right hand side:

\(\ds \) \(\) \(\ds \paren {R \symdif S} \symdif T\)
\(\ds \) \(=\) \(\ds \paren {\paren {\paren {R \cup S} \cap \paren {\overline R \cup \overline S} } \cup T} \cap \paren {\overline {R \symdif S} \cup \overline T}\) Definition 4 of Symmetric Difference
\(\ds \) \(=\) \(\ds \paren {\paren {\paren {R \cup S} \cap \paren {\overline R \cup \overline S} } \cup T} \cap \paren {\overline {\paren {\paren {R \cap \overline S} \cup \paren {\overline R \cap S} } } \cup \overline T}\) Definition 3 of Symmetric Difference
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\paren {\overline {\paren {R \cap \overline S} } \cap \overline {\paren {\overline R \cap S} } } \cup \overline T}\) Union Distributes over Intersection and De Morgan
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\paren {\paren {\overline R \cup S} \cap \paren {R \cup \overline S} } \cup \overline T}\) De Morgan
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\overline R \cup S \cup \overline T} \cap \paren {R \cup \overline S \cup \overline T}\) Union Distributes over Intersection


Expanding the left hand side:

\(\ds \) \(\) \(\ds R \symdif \paren {S \symdif T}\)
\(\ds \) \(=\) \(\ds \paren {R \cup \paren {\paren {S \cup T} \cap \paren {\overline S \cup \overline T} } } \cap \paren {\overline R \cup \overline {S \symdif T} }\) Definition 4 of Symmetric Difference
\(\ds \) \(=\) \(\ds \paren {R \cup \paren {\paren {S \cup T} \cap \paren {\overline S \cup \overline T} } } \cap \paren {\overline R \cup \overline {\paren {\paren {S \cap \overline T} \cup \paren {\overline S \cap T} } } }\) Definition 3 of Symmetric Difference
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \paren {\overline {\paren {S \cap \overline T} } \cap \overline {\paren {\overline S \cap T} } } }\) Union Distributes over Intersection and De Morgan
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \paren {\paren {\overline S \cup T} \cap \paren {S \cup \overline T} } }\) De Morgan
\(\ds \) \(=\) \(\ds \paren {R \cup S \cup T} \cap \paren {R \cup \overline S \cup \overline T} \cap \paren {\overline R \cup \overline S \cup T} \cap \paren {\overline R \cup S \cup \overline T}\) Union Distributes over Intersection


From Intersection is Commutative, it can be seen that the left hand side and right hand side are the same, and the result is proved.

$\blacksquare$


Comment

This illustrates that you can express the symmetric difference of three sets as the union of four intersections (which seems more intuitively obvious) as well as the intersection of four unions (which is not quite so obvious).


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Symmetric_Difference_is_Associative&oldid=744666"