Symmetric Difference is Associative

From ProofWiki
Jump to: navigation, search

Theorem

Symmetric difference is associative:

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


Proof 1

We can directly expand the expressions for $R * \left({S * T}\right)$ and $\left({R * S}\right) * T$, and see that they come to the same thing.

Expanding the RHS:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left({R * S}\right) * T\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right) \cap \overline T}\right) \cup \left({\overline {R * S} \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 3          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right) \cap \overline T}\right) \cup \left({\overline {\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right)} \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 4          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\left({\overline {\left({R \cup S}\right)} \cup \overline {\left({\overline R \cup \overline S}\right)} }\right) \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Intersection Distributes over Union and De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\left({\left({\overline R \cap \overline S}\right) \cup \left({R \cap S}\right)}\right) \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right) \cup \left({R \cap S \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Intersection Distributes over Union          


Expanding the LHS:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle R * \left({S * T}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline {S * T} }\right) \cup \left({\overline R \cap \left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 3          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline {\left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)} }\right) \cup \left({\overline R \cap \left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 4          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \left({\overline {\left({S \cup T}\right)} \cup \overline {\left({\overline S \cup \overline T}\right)} }\right)}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Intersection Distributes over Union and De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \left({\left({\overline S \cap \overline T}\right) \cup \left({S \cap T}\right)}\right)}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cap \overline S \cap \overline T}\right) \cup \left({R \cap S \cap T}\right) \cup \left({\overline R \cap S \cap \overline T}\right) \cup \left({\overline R \cap \overline S \cap T}\right)\) \(\displaystyle \) \(\displaystyle \)          Intersection Distributes over Union          


From Union is Commutative it is seen that the LHS and RHS are the same, and the result is proved.

$\blacksquare$


Proof 2

There is another way of doing this.


Expanding the RHS:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left({R * S}\right) * T\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right) \cup T}\right) \cap \left({\overline {R * S} \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 4          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({\left({\left({R \cup S}\right) \cap \left({\overline R \cup \overline S}\right)}\right) \cup T}\right) \cap \left({\overline {\left({\left({R \cap \overline S}\right) \cup \left({\overline R \cap S}\right)}\right)} \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 3          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\left({\overline {\left({R \cap \overline S}\right)} \cap \overline {\left({\overline R \cap S}\right)} }\right) \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          Union Distributes over Intersection and De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\left({\left({\overline R \cup S}\right) \cap \left({R \cup \overline S}\right)}\right) \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\overline R \cup S \cup \overline T}\right) \cap \left({R \cup \overline S \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          Union Distributes over Intersection          


Expanding the LHS:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle R * \left({S * T}\right)\) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup \left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)}\right) \cap \left({\overline R \cup \overline {S * T} }\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 4          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup \left({\left({S \cup T}\right) \cap \left({\overline S \cup \overline T}\right)}\right)}\right) \cap \left({\overline R \cup \overline {\left({\left({S \cap \overline T}\right) \cup \left({\overline S \cap T}\right)}\right)} }\right)\) \(\displaystyle \) \(\displaystyle \)          Definition of Symmetric Difference: Definition 3          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \left({\overline {\left({S \cap \overline T}\right)} \cap \overline {\left({\overline S \cap T}\right)} }\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          Union Distributes over Intersection and De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \left({\left({\overline S \cup T}\right) \cap \left({S \cup \overline T}\right)}\right)}\right)\) \(\displaystyle \) \(\displaystyle \)          De Morgan          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(=\) \(\displaystyle \) \(\displaystyle \left({R \cup S \cup T}\right) \cap \left({R \cup \overline S \cup \overline T}\right) \cap \left({\overline R \cup \overline S \cup T}\right) \cap \left({\overline R \cup S \cup \overline T}\right)\) \(\displaystyle \) \(\displaystyle \)          Union Distributes over Intersection          


From Intersection is Commutative, it can be seen that the LHS and RHS 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