Set Union is Self-Distributive/Sets of Sets
Theorem
Let $A$ and $B$ denote sets of sets.
Then:
- $\ds \bigcup \paren {A \cup B} = \paren {\bigcup A} \cup \paren {\bigcup B}$
where $\ds \bigcup A$ denotes the union of $A$.
Proof
Let $\ds s \in \bigcup \paren {A \cup B}$.
Then by definition of union of set of sets:
- $\exists X \in A \cup B: s \in X$
By definition of set union, either:
- $X \in A$
or:
- $X \in B$
If $X \in A$, then:
- $s \in \set {x: \exists X \in A: x \in X}$
If $X \in B$, then:
- $s \in \set {x: \exists X \in B: x \in X}$
Thus by definition of union of set of sets, either:
- $\ds s \in \bigcup A$
or:
- $\ds s \in \bigcup B$
So by definition of set union:
- $\ds s \in \paren {\bigcup A} \cup \paren {\bigcup B}$
So by definition of subset:
- $\ds \bigcup \paren {A \cup B} \subseteq \paren {\bigcup A} \cup \paren {\bigcup B}$
Now let $\ds s \in \paren {\bigcup A} \cup \paren {\bigcup B}$.
By definition of set union, either:
- $\ds s \in \bigcup A$
or:
- $\ds s \in \bigcup B$
That is, by definition of union of set of sets, either:
- $s \in \set {x: \exists X \in A: x \in X}$
or:
- $s \in \set {x: \exists X \in B: x \in X}$
Without loss of generality, let $s \in X$ such that $X \in A$.
Then by Set is Subset of Union:
- $s \in X$ such that $X \in A \cup B$
That is:
- $\ds s \in \bigcup \paren {A \cup B}$
Similarly if $x \in X$ such that $X \in B$.
So by definition of subset:
- $\ds \paren {\bigcup A} \cup \paren {\bigcup B} \subseteq \bigcup \paren {A \cup B}$
Hence by definition of equality of sets:
- $\ds \bigcup \paren {A \cup B} = \paren {\bigcup A} \cup \paren {\bigcup B}$
$\blacksquare$