# Symmetric Difference is Associative

## Theorem

$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).