Intersection is Subset of Union of Intersections with Complements

From ProofWiki
Jump to navigation Jump to search


Let $R, S, T$ be sets.


$S \cap T \subseteq \paren {R \cap S} \cup \paren {\overline R \cap T}$

where $\overline R$ denotes the complement of $R$.


Let $x \in S \cap T$.

Then by definition of set intersection, $x \in S \land x \in T$.

From Conjunction implies Disjunction of Conjunctions with Complements, it follows that:

$\paren {x \in S \land \psi} \lor \paren {x \in T \land \neg \psi}$

where $\psi$ is any arbitrary statement.

Let $\psi$ be the statement $x \in R$.


$\paren {x \in S \land x \in T} \implies \paren {x \in S \land x \in R} \lor \paren {x \in T \land x \notin R}$

By definition of subset, set intersection, set union and set complement, it follows that:

$S \cap T \subseteq \paren {R \cap S} \cup \paren {\overline R \cap T}$


Illustration by Venn Diagram

A Venn diagram illustrating this result is given below:


The red field marks $R \cap S$.

The blue field marks $\overline R \cap T$.

The purple field marks $S \cap T$, where both the red and blue are seen to intersect with the purple field.