9.5: Cartesian Product

Definition: Cartesian product

the set of all possible ordered pairs of elements from two given sets \(A\) and \(B\text{,}\) where the first element in a pair is from \(A\) and the second is from \(B\)

Definition: \(A \times B\)

the Cartesian product of \(A\) and \(B\text{:}\) \(A \times B = \{(a,b) \vert a\in A,\; b\in B\} \)

For “small” sets, we can list the elements of the Cartesian product by listing all ways of combining an element from the first with an element from the second.

Example \(\PageIndex{1}\): A Cartesian product of “small” sets.

Suppose \(A = \{ 1, 2 \}\) and \(B = \{ a, b, c \}\text{.}\) Then

\begin{equation*} A \times B = \{ (1,a), (1,b), (1,c), (2,a), (2,b), (2,c) \} \text{.} \end{equation*}

Example \(\PageIndex{2}\): A special subset of a certain Cartesian product.

Let \(\mathbb{N}^+\) represent the positive natural numbers: \(\mathbb{N}^+ = \mathbb{N} \setminus \{0\}\text{.}\) Then we can describe the Cartesian product \(\mathbb{Z} \times \mathbb{N}^+\) as

\begin{equation*} \mathbb{Z} \times \mathbb{N}^+ = \{(m,n) \vert m,n \in \mathbb{Z}, \; n>0 \} \subseteq \mathbb{Z} \times \mathbb{Z} \text{.} \end{equation*}
Consider the subset

\begin{equation*} A = \{(m,n) \in \mathbb{Z} \times \mathbb{N}^+ \vert n \text{ has no divisors in common with } \vert m \vert\} \subseteq \mathbb{Z} \times \mathbb{N}^+\text{.} \end{equation*}
Does \(A\) resemble some more familiar set …?

Extend.

Define \(A \times B \times C = \{(a,b,c) \vert a \in A\text{, } b\in B\text{, } c\in C \}\text{.}\)

Example \(\PageIndex{3}\)

Suppose \(A = \{ 1, 2 \}\text{,}\) \(B = \{ a, b, c \}\text{,}\) \(C = \{ \alpha, \beta \}\text{.}\) Then,
\begin{align*} A \times B \times C = \{ \;\; & (1,a,\alpha), \, (1,a,\beta), \, (1,b,\alpha), \, (1,b,\beta), \, (1,c,\alpha), \, (1,c,\beta), \,\\ & (2,a,\alpha), \, (2,a,\beta), \, (2,b,\alpha), \, (2,b,\beta), \, (2,c,\alpha), \, (2,c,\beta) \;\; \} \end{align*}

Remark \(\PageIndex{1}\)

Technically, there is a difference between the elements of each of the sets

\begin{align*} (A \times B) \times C & = \{((a,b),c) \vert a \in A\text{, } b\in B\text{, } c\in C \} \text{,} \\ A \times (B \times C) & = \{(a,(b,c)) \vert a \in A\text{, } b\in B\text{, } c\in C \} \text{,} \\ A \times B \times C & = \{(a,b,c) \vert a \in A\text{, } b\in B\text{, } c\in C \} \text{,} \end{align*}
but it is rare that anyone actually observes this technicality. Usually, we consider these three sets to be the same set.

We use special notation for Cartesian products of a set with itself.

Definition: \(A^2\)

notation to mean \(A \times A\)

Definition: \(A^3\)

notation to mean \(A \times A \times A\)

Definition: \(A^n\)

notation to mean \(A \times A \times \ldots \times A\) involving \(n\) “factors” of \(A\)

And so on.

Example \(\PageIndex{4}\): Cartesian products in linear algebra.

You have probably already encountered the notation

\begin{align*} \mathbb{R}^2 & = \{(x,y) \vert x,y \in \mathbb{R}\} \text{,}\\ \mathbb{R}^3 & = \{(x,y,z) \vert x,y,z \in \mathbb{R}\} \text{,}\\ & \vdots \\ \mathbb{R}^n & = \{(x_1,x_2,\ldots ,x_n) \vert x_j \in \mathbb{R}\} \text{,}\\ & \vdots \end{align*}
used to represent \(2\)-, \(3\)-, and higher-dimensional (real) vector spaces.