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.


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

The result Union Distributes over Intersection, along with Intersection Distributes over Union, 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=Union_Distributes_over_Intersection&oldid=744605"