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.


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 known as

The result Intersection Distributes over Union, along with Union Distributes over Intersection, are together known as:

the distributive laws (of set theory)
the distributive properties (of set theory).


Also see


Sources

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