Set Difference is Right Distributive over Set Intersection

From ProofWiki
Jump to navigation Jump to search

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$


Sources