Cartesian Product Distributes over Union

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

Take the result Cartesian Product of Unions:

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


Put $S_1 = S_2 = A, T_1 = B, T_2 = C$:

\(\ds \) \(\) \(\ds A \times \paren {B \cup C}\)
\(\ds \) \(=\) \(\ds \paren {A \cup A} \times \paren {B \cup C}\) Set Union is Idempotent
\(\ds \) \(=\) \(\ds \paren {A \times B} \cup \paren {A \times C} \cup \paren {A \times C} \cup \paren {A \times B}\) Cartesian Product of Unions
\(\ds \) \(=\) \(\ds \paren {A \times B} \cup \paren {A \times C}\) Set Union is Idempotent

Thus:

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


The other result is proved similarly.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Cartesian_Product_Distributes_over_Union&oldid=569337"