Skip to main content

Section 7.3 The Cartesian Product

You may recall ordered pairs \((a,b)\text{,}\) which are used to represents points in the Cartesian plane. Roughly, ordered pairs are an ordered arrangement of two numbers, i.e. where \((a,b)\) and \((b,a)\) are not considered the same. More generally, we can considered ordered triples \((a,b,c) \text{,}\) or ordered tuples of \(n\) elements, \((x_1, x_2, \dots, x_n)\text{,}\)

Ordered pairs of numbers can be defined in terms of another set operation, called the Cartesian product.

Subsection 7.3.1 Ordered Pairs, Triples, and n-Tuples

Definition 7.3.1.

An ordered pair \((a,b)\text{,}\) is an ordered list of two elements \(a\) and \(b\text{.}\) Two ordered pairs are equal if and only if their corresponding components are equal. In other words, \((a,b) = (c,d)\) are equal if and only if \(a = c\) and \(b = d\text{.}\)

Definition 7.3.2.

An ordered triple \((a,b,c)\) is an ordered list of three elements \(a, b\text{,}\) and \(c\text{.}\) Two ordered triples are equal if and only if their corresponding components are equal.

More generally, we can consider ordered lists with any finite number of elements.

Definition 7.3.3.

Let \(n\) be a positive integer. An ordered \(n\)-tuple \((x_1, x_2, \dots, x_n)\) is an ordered list of \(n\) elements. Two \(n\)-tuples are equal if and only if their corresponding components are equal. In other words,

\begin{equation*} (x_1, x_2, \dots, x_n) = (y_1, y_2, \dots, y_n) \quad \iff \quad x_1 = y_1, x_2 = y_2, \dots, x_n = y_n \end{equation*}

Then, an ordered pair is a 2-tuple, and an ordered triple is a 3-tuple.

Subsection 7.3.2 Cartesian Product

Definition 7.3.4.

Let \(A\) and \(B\) be sets. The Cartesian product of \(A\) and \(B\text{,}\) denoted by \(A \times B\text{,}\) is the set of all ordered pairs with elements in \(A\) as the first element and elements in \(B\) as the second element.

\begin{equation*} \boxed{A \times B = \set{(a,b): a \in A \text{ and } b \in B}} \end{equation*}

Using mathematical logic,

\begin{equation*} (x,y) \in A \times B \quad \iff \quad (x \in A) \land (x \in B) \end{equation*}

In general, the Cartesian product is not commutative. In other words, in general \(A \times B \neq B \times A\) (unless \(A = B\)).

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

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

The definition of the Cartesian product of two sets can be generalized to \(n\) sets.

Definition 7.3.6.

Let \(A_1, A_2, \dots, A_n\) be sets. Then, the Cartesian product \(A_1 \times A_2 \times \dots \times A_n\) is the set of all \(n\)-tuples \((a_1, a_2, \dots, a_n)\) where \(a_1 \in A_1, a_2 \in A_2, \dots, a_n \in A_n\text{.}\) In other words,

\begin{equation*} A_1 \times \dots \times A_n = \set{(a_1, \dots, a_n): a_1 \in A_1, \dots, a_n \in A_n} \end{equation*}

\(\mathbb{R} \times \mathbb{R} = \mathbb{R}^2\) is the familiar Cartesian plane, and \(\mathbb{R} \times \mathbb{R} \times \mathbb{R} = \mathbb{R}^3\) is three-dimensional Euclidean space. In general, \(\mathbb{R}^n\) is the set of all \(n\)-tuples of real numbers.

Subsection 7.3.3 Cardinality of Cartesian Product

The cardinality of a Cartesian product follows almost directly from the multiplication principle.

Subsection 7.3.4 Formalization of the Cartesian Product

In the development of set theory as the foundation of mathematics, mathematicians wanted to formally define ordered tuples in terms of sets. however, sets are not ordered, in that \(\set{a,b}\) and \(\set{b,a}\) both represent the same set.

In 1914, Norbert Wiener (1894-1964), American mathematician, proposed a formal definition of an ordered pair as,

\begin{equation*} (a,b) = \set{\set{\set{a}, \emptyset}, \set{\set{b}}} \end{equation*}

Here, the \(\emptyset\) is associated with the first element, which indicates the ordering of the elements. The nesting of the set \(\set{\set{b}}\) was for more technical reasons.

In around the same time in 1914, Felix Hausdorff (1868-1942), German mathematician, proposed a similar, slightly more intuitive definition,

\begin{equation*} (a,b) = \set{\set{a,1}, \set{b,2}} \end{equation*}

where the 1 and 2 indicate which of \(a\) and \(b\) are the first and second element.

Then, in 1921, Kazimierz Kuratowski (1896-1980) proposed another definition,

\begin{equation*} (a,b) = \set{\set{a}, \set{a,b}} \end{equation*}

This is the currently accepted definition. Here, the first element is in the set with 1 element, and the second is identified by being in the set with 2 elements that is not the first element. If \(a = b\text{,}\) then,

\begin{equation*} (a,b) = \set{\set{a}, \set{a,a}} = \set{\set{a}, \set{a}} = \set{a} \end{equation*}