# Symmetric Difference is Associative

## Theorem

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