Cartesian Product of Unions

From ProofWiki
Jump to navigation Jump to search

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

Cartesian product is distributive over union:

$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$


Sources