# Cartesian Product of Unions

## Theorem

$\paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2} = \paren {S_1 \times T_1} \cup \paren {S_2 \times T_2} \cup \paren {S_1 \times T_2} \cup \paren {S_2 \times T_1}$

### Corollary

$A \times \paren {B \cup C} = \paren {A \times B} \cup \paren {A \times C}$
$\paren {B \cup C} \times A = \paren {B \times A} \cup \paren {C \times A}$

### General Result

Let $I$ and $J$ be indexing sets.

Let $\family {A_i}_{i \mathop \in I}$ and $\family {B_j}_{j \mathop \in J}$ be families of sets indexed by $I$ and $J$ respectively.

Then:

$\displaystyle \paren {\bigcup_{i \mathop \in I} A_i} \times \paren {\bigcup_{j \mathop \in J} B_j} = \bigcup_{\tuple {i, j} \mathop \in I \times J} \paren {A_i \times B_j}$

where:

$\displaystyle \bigcup_{i \mathop \in I} A_i$ denotes the union of $\family {A_i}_{i \mathop \in I}$ and so on
$\times$ denotes Cartesian product.

## Proof

 $\displaystyle$  $\displaystyle \tuple {x, y} \in \paren {S_1 \cup S_2} \times \paren {T_1 \cup T_2}$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle$  $\displaystyle \paren {x \in S_1 \lor x \in S_2}$ $\displaystyle$ $\land$ $\displaystyle \paren {y \in T_1 \lor y \in T_2}$ Definition of Cartesian Product and Definition of Set Union $\displaystyle \leadstoandfrom \ \$ $\displaystyle$  $\displaystyle \paren {\paren {x \in S_1 \lor x \in S_2} \land y \in T_1}$ $\displaystyle$ $\lor$ $\displaystyle \paren {\paren {x \in S_1 \lor x \in S_2} \land y \in T_2}$ Rule of Distribution $\displaystyle \leadstoandfrom \ \$ $\displaystyle$  $\displaystyle \paren {x \in S_1 \land y \in T_1}$ $\displaystyle$ $\lor$ $\displaystyle \paren {x \in S_2 \land y \in T_1}$ $\displaystyle$ $\lor$ $\displaystyle \paren {x \in S_1 \land y \in T_2}$ $\displaystyle$ $\lor$ $\displaystyle \paren {x \in S_2 \land y \in T_2}$ Rule of Distribution $\displaystyle \leadstoandfrom \ \$ $\displaystyle$  $\displaystyle \tuple {x, y} \in \paren {S_1 \times T_1} \cup \paren {S_2 \times T_2} \cup \paren {S_1 \times T_2} \cup \paren {S_2 \times T_1}$ Definition of Cartesian Product and Definition of Set Union

$\blacksquare$