cartesian product

Suppose that \( A , B \) are set, 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 \} \]