Skip to main content

Section 2.1 Cartesian products

When we have two mathematical objects \(x\) and \(y\text{,}\) an ordered pair \((x,y)\) is a way of listing the objects in order, so that \((x,y) \neq (y,x)\text{.}\) The main point is that we want \((x,y) = (u,v)\) to hold if and only if both \(x =u\) and \(y = v\text{.}\) This is in contrast with the sets \(\{x,y\}\) and \(\{u,v\}\text{,}\) where the order does not matter: we have \(\{x,y\} = \{y,x\}\text{.}\)

Here is the way we make this set-theoretically sensible:

Definition 2.1.1.

Let \(S\) and \(T\) be sets, and let \(x \in S\) and \(y \in T\text{.}\) Then we define the ordered pair

\begin{equation*} (x,y) = \{\{x\},\{x,y\}\}\text{.} \end{equation*}

The set of all ordered pairs is the cartesian product:

\begin{equation*} X \times Y = \{(x,y) : (x \in X)\wedge (y \in Y)\}\text{.} \end{equation*}

In other courses, you have probably already seen an example of Cartesian products in the form of the Cartesian plane. If \(\RR\) denotes the set of real numbers, then

\begin{equation*} \RR = \{(x,y) : x,y\in\RR\} = \RR\times \RR\text{.} \end{equation*}

We can take products of very different sets. For example, let \(X = \{1,2,3,4,5,6,7,8\}\) and \(Y = \{\text{Cat},\text{Dog}\}\text{.}\) Then \(X \times Y\) is the set of all pairs of natural numbers between 1 and 8 with either Cat or Dog. Thus typical elements of \(X \times Y \) are \((2,\text{Dog})\text{,}\) \((8,\text{Cat})\text{.}\)

We can also define ordered \(n\)-tuples:

\begin{equation*} (x_1, \dots, x_n) = \{\{x_1\}, \{x_1,x_2\}, \dots, \{x_1, \dots, x_n\}\}\text{,} \end{equation*}

as well as \(n\)-fold cartesian products:

\begin{equation*} A_1 \times \cdots \times A_n =\{(x_1, \dots, x_n) : (\forall i \in \{1,\dots,n\})(x_i \in A_i)\}\text{.} \end{equation*}