Union Distributes over Union/Sets of Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$ and $B$ denote sets of sets.


Then:

$\displaystyle \bigcup \left({A \cup B}\right) = \left({\bigcup A}\right) \cup \left({\bigcup B}\right)$

where $\displaystyle \bigcup A$ denotes the union of $A$.


Proof

Let $\displaystyle s \in \bigcup \left({A \cup B}\right)$.

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 \left\{{x: \exists X \in A: x \in X}\right\}$

If $X \in B$, then:

$s \in \left\{{x: \exists X \in B: x \in X}\right\}$

Thus by definition of union of set of sets, either:

$\displaystyle s \in \bigcup A$

or:

$\displaystyle s \in \bigcup B$

So by definition of set union:

$\displaystyle s \in \left({\bigcup A}\right) \cup \left({\bigcup B}\right)$

So by definition of subset:

$\displaystyle \bigcup \left({A \cup B}\right) \subseteq \left({\bigcup A}\right) \cup \left({\bigcup B}\right)$


Now let $\displaystyle s \in \left({\bigcup A}\right) \cup \left({\bigcup B}\right)$.

By definition of set union, either:

$\displaystyle s \in \bigcup A$

or:

$\displaystyle s \in \bigcup B$

That is, by definition of union of set of sets, either:

$s \in \left\{{x: \exists X \in A: x \in X}\right\}$

or:

$s \in \left\{{x: \exists X \in B: x \in X}\right\}$

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:

$\displaystyle s \in \bigcup \left({A \cup B}\right)$

Similarly if $x \in X$ such that $X \in B$.

So by definition of subset:

$\displaystyle \left({\bigcup A}\right) \cup \left({\bigcup B}\right) \subseteq \bigcup \left({A \cup B}\right)$


Hence by definition of equality of sets:

$\displaystyle \bigcup \left({A \cup B}\right) = \left({\bigcup A}\right) \cup \left({\bigcup B}\right)$

$\blacksquare$