# Set Difference is not Associative

## Theorem

Let $R, S, T$ be sets.

The expression:

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

holds exactly when $R \cap T = \O$.

Here $R \setminus S$ denotes set difference.

Thus, set difference is not associative.

## Proof

We assume a universe $\mathbb U$ such that $R, S, T \subseteq \mathbb U$.

We have the identity Set Difference as Intersection with Complement:

$R \setminus S = R \cap \overline S$

where $\overline S$ is the set complement of $S$:

$\overline S = \relcomp {\Bbb U} S$

Thus we can represent the two expressions as follows:

 $\displaystyle \paren {R \setminus S} \setminus T$ $=$ $\displaystyle \paren {R \cap \overline S} \cap \overline T$ Set Difference as Intersection with Complement $\displaystyle$ $=$ $\displaystyle R \cap \overline S \cap \overline T$ Intersection is Associative

For the second:

 $\displaystyle$  $\displaystyle R \setminus \paren {S \setminus T}$ $\displaystyle$ $=$ $\displaystyle R \cap \overline {\paren {S \cap \overline T} }$ Set Difference as Intersection with Complement $\displaystyle$ $=$ $\displaystyle R \cap \paren {\overline S \cup \overline {\paren {\overline T} } }$ De Morgan's Laws: Complement of Intersection $\displaystyle$ $=$ $\displaystyle R \cap \paren {\overline S \cup T}$ Complement of Complement $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S} \cup \paren {R \cap T}$ Intersection Distributes over Union $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap \mathbb U} \cup \paren {R \cap \mathbb U \cap T}$ Intersection with Universe $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap \paren {T \cup \overline T} } \cup \paren {R \cap \paren {S \cup \overline S} \cap T}$ Union with Complement $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap T} \cup \paren {R \cap \overline S \cap \overline T}$ $\, \displaystyle \cup \,$ $\displaystyle$  $\displaystyle \paren {R \cap S \cap T} \cup \paren {R \cap \overline S \cap T}$ Intersection Distributes over Union $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap T} \cup \paren {R \cap \overline S \cap \overline T} \cup \paren {R \cap S \cap T}$ Union is Idempotent $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap \overline T} \cup \paren {R \cap \paren {S \cup \overline S} \cap T}$ Intersection Distributes over Union $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap \overline T} \cup \paren {R \cap \mathbb U \cap T}$ Union with Complement $\displaystyle$ $=$ $\displaystyle \paren {R \cap \overline S \cap \overline T} \cup \paren {R \cap T}$ Intersection with Universe

As can be seen, this full expansion of the second expression can be expressed:

$R \setminus \paren {S \setminus T} = \paren {\paren {R \setminus S} \setminus T} \cup \paren {R \cap T}$

It directly follows from Intersection with Empty Set that:

$R \setminus \paren {S \setminus T} = \paren {R \setminus S} \setminus T \iff R \cap T = \O$

$\blacksquare$