Intersection Distributes over Union

From ProofWiki
Jump to: navigation, search

Contents

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)$


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 \in \mathbb T} \left({S \cap X}\right)$


Proof

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle x \in R \cap \left({S \cup T}\right)\) \(\iff\) \(\displaystyle x \in R \land \left({x \in S \lor x \in T}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definitions of Union and Intersection          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle \left ({x \in R \land x \in S}\right) \lor \left({x \in R \land x \in T}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Rule of Distribution          
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\iff\) \(\displaystyle x \in \left({R \cap S}\right) \cup \left({R \cap T}\right)\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)          Definitions of Union and Intersection          

$\blacksquare$


Proof of General Result

Intersection Subset of Union

Let $\displaystyle x \in S \cap \bigcup \mathbb T$.

We need to show that $\displaystyle x \in \bigcup_{X \in \mathbb T} \left({S \cap X}\right)$ and then by definition of subset we will have shown that $\displaystyle S \cap \bigcup \mathbb T \subseteq \bigcup_{X \in \mathbb T} \left({S \cap X}\right)$.


So, we have that $\displaystyle x \in S \cap \bigcup \mathbb T$.

By definition of set intersection, $x \in S$ and $\displaystyle x \in \bigcup \mathbb T$.

From $\displaystyle x \in \bigcup \mathbb T$ we know that:

$\exists X \in \mathbb T: x \in X$

and so:

$\displaystyle \exists X \in \mathbb T: x \in S \cap X$

So by definition of set union:

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


So:

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

$\Box$


Union Subset of Intersection

Let $\displaystyle x \in \bigcup_{X \in \mathbb T} \left({S \cap X}\right)$.

We need to show that $\displaystyle x \in S \cap \bigcup \mathbb T$ and then by definition of subset we will have shown that $\displaystyle \bigcup_{X \in \mathbb T} \left({S \cap X}\right) \subseteq S \cap \bigcup \mathbb T$.


So, we have that $\displaystyle x \in \bigcup_{X \in \mathbb T} \left({S \cap X}\right)$.

By definition of set union:

$\exists X \in \mathbb T: x \in S \cap X$


By definition of set intersection, we have that $x \in S$ and $x \in X$.

By definition of set union:

$\displaystyle x \in \bigcup \mathbb T$

So by definition of set intersection, we have that:

$\displaystyle x \in S \cap \bigcup \mathbb T$


So:

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

$\Box$


So we have that:

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

and

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

and so by definition of Equality of Sets:

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

$\blacksquare$


Also see


Sources

Retrieved from "http://www.proofwiki.org/w/index.php?title=Intersection_Distributes_over_Union&oldid=92608"
Personal tools
Namespaces
Variants
Actions
Navigation
ProofWiki.org
ToDo
Toolbox
Google AdSense