Intersection Distributes over Union

From ProofWiki
Jump to navigation Jump to search

Theorem

Set intersection is distributive over set union:

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


Family of Sets

Let $I$ be an indexing set.

Let $\family {A_\alpha}_{\alpha \mathop \in I}$ be a indexed family of subsets of a set $S$.

Let $B \subseteq S$.


Then:

$\ds \map {\bigcup_{\alpha \mathop \in I} } {A_\alpha \cap B} = \paren {\bigcup_{\alpha \mathop \in I} A_\alpha} \cap B$

where $\ds \bigcup_{\alpha \mathop \in I} A_\alpha$ denotes the union of $\family {A_\alpha}_{\alpha \mathop \in I}$.


General Result

Let $S$ and $T$ be sets.

Let $\powerset T$ be the power set of $T$.

Let $\mathbb T$ be a subset of $\powerset T$.


Then:

$\ds S \cap \bigcup \mathbb T = \bigcup_{X \mathop \in \mathbb T} \paren {S \cap X}$


Proof

\(\ds \) \(\) \(\ds x \in R \cap \paren {S \cup T}\)
\(\ds \) \(\leadstoandfrom\) \(\ds x \in R \land \paren {x \in S \lor x \in T}\) Definition of Set Union and Definition of Set Intersection
\(\ds \) \(\leadstoandfrom\) \(\ds \paren {x \in R \land x \in S} \lor \paren {x \in R \land x \in T}\) Conjunction is Left Distributive over Disjunction
\(\ds \) \(\leadstoandfrom\) \(\ds x \in \paren {R \cap S} \cup \paren {R \cap T}\) Definition of Set Union and Definition of Set Intersection

$\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 \paren {S \cup T}$ where they overlap is depicted in green.


In the right hand diagram, $\paren {R \cap S}$ is depicted in yellow and $\paren {R \cap T}$ 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.


Examples

$3$ Arbitrarily Chosen Sets

Let:

\(\ds A\) \(=\) \(\ds \set {3, -i, 4, 2 + i, 5}\)
\(\ds B\) \(=\) \(\ds \set {-i, 0, -1, 2 + i}\)
\(\ds C\) \(=\) \(\ds \set {- \sqrt 2 i, \dfrac 1 2, 3}\)


Intersection with Union

\(\ds A \cap \paren {B \cup C}\) \(=\) \(\ds \set {3, -i, 4, 2 + i, 5} \cap \set {-i, 0, -\sqrt 2 i, -1, 2 + i, \dfrac 1 2, 3}\)
\(\ds \) \(=\) \(\ds \set {3, -i, 2 + i}\)


Union of Intersections

\(\ds \paren {A \cap B} \cup \paren {A \cap C}\) \(=\) \(\ds \set {-i, 2 + i} \cup \set 3\)
\(\ds \) \(=\) \(\ds \set {3, -i, 2 + i}\)


Thus it is seen that:

$A \cap \paren {B \cup C} = \paren {A \cap B} \cup \paren {A \cap C}$


Arbitrary Integer Sets

Let:

\(\ds A\) \(=\) \(\ds \set {2, 4, 6, 8, \dotsc}\)
\(\ds B\) \(=\) \(\ds \set {1, 3, 5, 7, \dotsc}\)
\(\ds C\) \(=\) \(\ds \set {1, 2, 3, 4}\)

Then:

$\paren {A \cup B} \cap C = \set {1, 2, 3, 4} = \paren {A \cap C} \cup \paren {B \cap C}$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Intersection_Distributes_over_Union&oldid=669771"