Cartesian Product of Unions

From ProofWiki
Jump to navigation Jump to search

Theorem

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


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:

$\ds \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:

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

\(\ds \) \(\) \(\ds \tuple {x, y} \in \paren {A \cup B} \times \paren {C \cup D}\)
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in A \lor x \in B}\)
\(\ds \) \(\land\) \(\ds \paren {y \in C \lor y \in D}\) Definition of Cartesian Product and Definition of Set Union
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {\paren {x \in A \lor x \in B} \land y \in C}\)
\(\ds \) \(\lor\) \(\ds \paren {\paren {x \in A \lor x \in B} \land y \in D}\) Rule of Distribution
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \paren {x \in A \land y \in C}\)
\(\ds \) \(\lor\) \(\ds \paren {x \in B \land y \in C}\)
\(\ds \) \(\lor\) \(\ds \paren {x \in A \land y \in D}\)
\(\ds \) \(\lor\) \(\ds \paren {x \in B \land y \in D}\) Rule of Distribution
\(\ds \leadstoandfrom \ \ \) \(\ds \) \(\) \(\ds \tuple {x, y} \in \paren {A \times C} \cup \paren {B \times D} \cup \paren {A \times D} \cup \paren {B \times C}\) Definition of Cartesian Product and Definition of Set Union

$\blacksquare$


Sources