# Cartesian Product

cartesian product
Suppose that $$A , B$$ are sets, then we define $$A \times B := \left \lbrace \left ( a , b \right ) : a \in A , b \in B \right \rbrace$$
intersection and cartesian product commute
Given sets $$A , B , C , D$$, then $$\left ( A \times B \right ) \cap \left ( C \times D \right ) = \left ( A \cap C \right ) \times \left ( B \cap D \right )$$

We will prove this true by the definition of set equality.

Suppose that $$\left ( x , y \right ) \in \left ( A \times B \right ) \cap \left ( C \times D \right )$$, which is true iff $$\left ( x , y \right ) \in \left ( A \times B \right )$$, so that $$x \in A$$ and $$y \in B$$.

We also know that $$\left ( x , y \right ) \in \left ( C \times D \right )$$ which is equivalent to $$x \in C$$ and $$y \in D$$

We have $$x \in A \cap C$$ and $$y \in B \cap D$$ which is equivalent to $$\left ( x , y \right ) \in \left ( A \cap C \right ) \times \left ( B \cap D \right )$$.

Thus we've proven that $$\left ( x , y \right ) \in \left ( A \times B \right ) \cap \left ( C \times D \right )$$ if and only if $$\left ( x , y \right ) \in \left ( A \times B \right ) \cap \left ( C \times D \right )$$ as needed.

cartesian product distributes over intersection
Given sets $$A , B , C$$, then $$\left ( A \cap B \right ) \times C = \left ( A \times C \right ) \cap \left ( B \times C \right )$$
We will show their equality directly

So suppose that $$\left ( x , y \right ) \in \left ( A \cap B \right ) \times C$$, which is true iff $$x \in A \cap B$$ and $$y \in C$$, which is true iff $$\left ( x , y \right ) \in A \times C$$ and $$\left ( x , y \right ) \in B \times C$$, which is true iff $$x \in \left ( A \times C \right ) \cap \left ( B \times C \right )$$.

Therefore $$\left ( x , y \right ) \in \left ( A \cap B \right ) \times C$$ if and only if $$x \in \left ( A \times C \right ) \cap \left ( B \times C \right )$$, so $$\left ( A \cap B \right ) \times C = \left ( A \times C \right ) \cap \left ( B \times C \right )$$ as needed.

Set Power
Suppose that $$A$$ is a set, and that $$n \in \mathbb{N}_1$$, then we define $$A ^ n$$ to be the set of all n-tuples of $$A$$, that is : $A^n := \{ (a_1, a_2, ..., a_n): \forall i \in [n], a_i \in A \}$