The Cartesian Product of Sets

# The Cartesian Product of Sets

 Definition: Let $A$ and $B$ be sets. Then the Cartesian Product of $A$ and $B$ denoted $A \times B$ is defined to be the set of ordered pairs $(a, b)$ where $x \in A$ and $y \in B$, that is $A \times B = \{ (x, y) : x \in A \: \mathrm{and} \: y \in B \}$.

Note that the definition of $A \times B$ requires that each pair of elements is ordered in the sense that for each $(x, y) \in A \times B$ we MUST have that $x \in A$ and $y \in B$.

For example, consider the following sets:

(1)
\begin{align} \quad A = \{ a, b, c \} \end{align}
(2)
\begin{align} \quad B = \{ x, y \} \end{align}

Then we have that:

(3)
\begin{align} \quad A \times B = \{ (a, x), (a, y), (b, x), (b, y), (c, x), (c, y) \} \end{align}

Note that the first element in each ordered pair is an element of $A$ and the second element in each ordered pair is an element of $B$. The pair $(x, a) \not \in A \times B$ though since $x \not \in A$ AND $a \not \in B$. While the order of elements in a set does not matter, the order of a list - or in this case, the order of our pair or any $n$-tuple is indeed important.

For a more geometric interpretation for the Cartesian product of two sets of real numbers, consider the following sets:

(4)
\begin{align} \quad A = \{ x : x \in \mathbb{R} \: \mathrm{and} \: 1 \leq x \leq 2 \} \end{align}
(5)
\begin{align} \quad B = \{ y : y \in \mathbb{R} \: \mathrm{and} \: 3 \leq y \leq 4 \} \end{align}

If we regard each ordered pair $(x, y)$ as a point on the Cartesian coordinate system, $\mathbb{R}^2$, then we have that:

(6)
\begin{align} \quad A \times B = \{ (x, y) \in \mathbb{R}^2 : 1 \leq x \leq 2 \: \mathrm{and} \: 3 \leq y \leq 4 \} \end{align}

Geometrically this can be represented with the following illustration: Of course, we can construct the Cartesian product of more than two sets in a similar manner. Let $A_1, A_2, ..., A_n$ be a collection of sets. Then the Cartesian product of these sets with this prescribed order as the set of ordered $n$-tuples:

(7)
\begin{align} \quad A_1 \times A_2 \times ... \times A_n = \{ (x_1, x_2, ..., x_n) : x_i \in A_i \: \mathrm{for \: each} \: i = 1, 2, ..., n \} \end{align}