Set Difference is Not Associative

Theorem

For any three sets $R, S, T$:

$R \setminus \left({S \setminus T}\right)$ does not, in general, equal $\left({R \setminus S}\right) \setminus T$

where $R \setminus S$ etc. denotes set difference.

From Set Difference with Union, we have:

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

From Set Difference with Set Difference is Union of Set Difference with Intersection, we have:

$R \setminus \left({S \setminus T}\right) = \left({R \setminus S}\right) \cup \left({R \cap T}\right)$

These appear to be different.

In fact:

$\left({R \setminus S}\right) \setminus T \subseteq R \setminus \left({S \setminus T}\right)$

Thus it is clear that set difference is not associative.

The expression:

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

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

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 = \mathbb U \setminus S$.

Thus we can represent the two expressions as follows.

The first one is easy enough:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({R \setminus S}\right) \setminus T\)	\(=\)	\(\displaystyle \left({R \cap \overline S}\right) \cap \overline T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Set Difference as Intersection with Complement
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle R \cap \overline S \cap \overline T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as Intersection is Associative

The second one is more involved:

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

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

$R \setminus \left({S \setminus T}\right) = \left({\left({R \setminus S}\right) \setminus T}\right) \cup \left({R \cap T}\right)$

Hence the first result, from Subset of Union.

$\blacksquare$

It directly follows from Intersection with Empty Set that:

$R \setminus \left({S \setminus T}\right) = \left({R \setminus S}\right) \setminus T \iff R \cap T = \varnothing$

$\blacksquare$

Also see

• Intersection is Associative
• Union is Associative
• Symmetric Difference is Associative

Sources

• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 1$: Exercise $15$