Intersection Distributes over Union

From ProofWiki
Jump to: navigation, search

Theorem

Set intersection is distributive over set union:

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


Family of Sets

Let $I$ be an indexing set.

Let $\left \langle {A_\alpha} \right \rangle_{\alpha \mathop \in I}$ be a indexed family of subsets of a set $S$.

Let $B \subseteq S$.


Then:

$\displaystyle \bigcup_{\alpha \mathop \in I} \left({A_\alpha \cap B}\right) = \left({\bigcup_{\alpha \mathop \in I} A_\alpha}\right) \cap B$

where $\displaystyle \bigcup_{\alpha \mathop \in I} A_\alpha$ denotes the union of $\left \langle {A_\alpha} \right \rangle_{\alpha \mathop \in I}$.


General Result

Let $S$ and $T$ be sets.

Let $\mathcal P \left({T}\right)$ be the power set of $T$.

Let $\mathbb T$ be a subset of $\mathcal P \left({T}\right)$.


Then:

$\displaystyle S \cap \bigcup \mathbb T = \bigcup_{X \mathop \in \mathbb T} \left({S \cap X}\right)$


Proof

\(\displaystyle \) \(\) \(\displaystyle x \in R \cap \left({S \cup T}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(\iff\) \(\displaystyle x \in R \land \left({x \in S \lor x \in T}\right)\) $\quad$ Definitions of Union and Intersection $\quad$
\(\displaystyle \) \(\iff\) \(\displaystyle \left ({x \in R \land x \in S}\right) \lor \left({x \in R \land x \in T}\right)\) $\quad$ Conjunction is Left Distributive over Disjunction $\quad$
\(\displaystyle \) \(\iff\) \(\displaystyle x \in \left({R \cap S}\right) \cup \left({R \cap T}\right)\) $\quad$ Definitions of Union and Intersection $\quad$

$\blacksquare$


Demonstration by Venn Diagram

IntDistOverUnion1.png IntDistOverUnion2.png

In the left hand diagram, $R$ is depicted in yellow and $S \cup T$ is depicted in blue.

Their intersection $R \cap \left({S \cup T}\right)$ where they overlap is depicted in green.


In the right hand diagram, $\left({R \cap S}\right)$ is depicted in yellow and $\left({R \cap T}\right)$ is depicted in blue.

Their intersection, where they overlap, is depicted in green.

Their union is the total shaded area: yellow, blue and green.


As can be seen by inspection, the areas are the same.


Also known as

This result and Union Distributes over Intersection are together known as the Distributive Laws.


Also see


Sources