Union Distributes over Intersection

From ProofWiki
Jump to navigation Jump to search

Theorem

Set union is distributive over set intersection:

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


Family of Sets

Let $I$ be an indexing set.

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

Let $B \subseteq S$.


Then:

$\ds \map {\bigcap_{\alpha \mathop \in I} } {A_\alpha \cup B} = \paren {\bigcap_{\alpha \mathop \in I} A_\alpha} \cup B$

where $\ds \bigcap_{\alpha \mathop \in I} A_\alpha$ denotes the intersection 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 \cup \bigcap \mathbb T = \bigcap_{X \mathop \in \mathbb T} \paren {S \cup X}$


Proof 1

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

$\blacksquare$


Proof 2

From Intersection Distributes over Union:

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

From the Duality Principle for Sets, exchanging $\cup$ for $\cap$ throughout, and vice versa, reveals the result:

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

$\blacksquare$


Demonstration by Venn Diagram

UnionDistOverInt1.png UnionDistOverInt2.png

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

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

Their union $R \cup \paren {S \cap T}$ is the total shaded area: yellow, blue and green.


In the right hand diagram, $\paren {R \cup S}$ is depicted in yellow and $\paren {R \cup T}$ is depicted in blue.

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


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


Also known as

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


Examples

Arbitrary Integer Sets: $1$

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


Arbitrary Integer Sets: $2$

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


Also see


Sources

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