# Set Difference is Right Distributive over Set Intersection

## Theorem

Let $R, S, T$ be sets.

Then:

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

where:

$R \cap S$ denotes set intersection
$R \setminus T$ denotes set difference.

That is, set difference is right distributive over set intersection.

## Proof 1

Consider $R, S, T \subseteq \mathbb U$, where $\mathbb U$ is considered as the universe.

 $\displaystyle \left({R \cap S}\right) \setminus T$ $=$ $\displaystyle \left({R \cap S}\right) \cap \complement \left({T}\right)$ Set Difference as Intersection with Complement $\displaystyle$ $=$ $\displaystyle \left({R \cap S}\right) \cap \left({\complement \left({T}\right) \cap \complement \left({T}\right)}\right)$ Intersection is Idempotent $\displaystyle$ $=$ $\displaystyle \left({R \cap \complement \left({T}\right)}\right) \cap \left({S \cap \complement \left({T}\right)}\right)$ Intersection is Associative and Intersection is Commutative $\displaystyle$ $=$ $\displaystyle \left({R \setminus T}\right) \cap \left({S \setminus T}\right)$ Set Difference as Intersection with Complement

$\blacksquare$

## Proof 2

 $\displaystyle x$ $\in$ $\displaystyle \paren {R \cap S} \setminus T$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle R \land x \in S$ Definition of Set Intersection $\, \displaystyle \land \,$ $\displaystyle x$ $\notin$ $\displaystyle T$ Definition of Set Difference $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle R \land x \in S$ Rule of Idempotence $\, \displaystyle \land \,$ $\displaystyle x$ $\notin$ $\displaystyle T \land x \notin T$ Rule of Idempotence $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle R$ Rule of Association $\, \displaystyle \land \,$ $\displaystyle x$ $\in$ $\displaystyle x \in S \land x \notin T$ $\, \displaystyle \land \,$ $\displaystyle x$ $\notin$ $\displaystyle T$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle R$ $\, \displaystyle \land \,$ $\displaystyle x$ $\notin$ $\displaystyle T \land x \in S$ Rule of Commutation $\, \displaystyle \land \,$ $\displaystyle x$ $\notin$ $\displaystyle T$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle R \land x \notin T$ Rule of Association $\, \displaystyle \land \,$ $\displaystyle x$ $\in$ $\displaystyle S \land x \notin T$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle \paren {R \setminus T}$ Definition of Set Difference $\, \displaystyle \land \,$ $\displaystyle x$ $\in$ $\displaystyle \paren {S \setminus T}$ Definition of Set Difference $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle \paren {R \setminus T} \cap \paren {S \setminus T}$ Definition of Set Intersection

$\blacksquare$