Cartesian Product

10 min.   |   Beginner   |   (Hammack 2013)

Ordered Pair

An ordered pair is a list (x,y) of two elements x and y, enclosed in parentheses and separated by a comma.

CautionOrdered Pair: Example

Consider the ordered pair (0,0) referred to as the origin in a two-dimensional coordinate system.

Cartesian Product

Suppose \mathcal{A} and \mathcal{B} are sets.

A cartesian product is simply the multiplication of sets denoted as \mathcal{A} \times \mathcal{B} and defined as

\mathcal{A} \times \mathcal{B} = \{(a,b): a \in \mathcal{A}, \ b \in \mathcal{B} \}

CautionCartesian Product: Example 1

Suppose the following sets \mathcal{A} and \mathcal{B}:

\mathcal{A} = \{a, b, c\}, \ \mathcal{B} = \{1, 2, 3\}

The cartesian product between the two sets is the set \mathcal{A} \times \mathcal{B}:

\mathcal{A} \times \mathcal{B} = \{ (a,1), (a,2), (a,3), (b,1), (b,2), (b,3), (c,1), (c,2), (c,3) \}

CautionCartesian Product: Example 2

Suppose the following sets \mathcal{A}, \mathcal{B} and \mathcal{C}:

\mathcal{A} = \{a, b\}, \ \mathcal{B} = \{1, 2\}, \ \mathcal{C} = \{\text{I}, \text{II}\}

The cartesian product between the three sets is the set \mathcal{A} \times \mathcal{B} \times \mathcal{C}:

\mathcal{A} \times \mathcal{B} \times \mathcal{C} = \{ (a,1,\text{I}), (a,1,\text{II}), (a,2,\text{I}), (a,2,\text{II}), (b,1,\text{I}), (b,1,\text{II}), (b,2,\text{I}), (b,2,\text{II}) \}

Note that ordered triples (x,y,z) are also possible, and can be further generalized to ordered n-tuples (x_1, x_2, \ldots, x_n), where n represents the number of elements in the tuple.

Note Cartesian Product: Concept Check

What is the cardinality of \lvert \mathcal{A} \times \mathcal{B} \times \mathcal{C} \rvert?

\mathcal{A} = \{a, b, c\}, \ \mathcal{B} = \{1, 2\}, \ \mathcal{C} = \{\text{I}, \text{II}, \text{III}\}

16182017

The cardinality of the Cartesian product \mathcal{A} \times \mathcal{B} \times \mathcal{C} is the product of the cardinalities of the individual sets:

\begin{align*} \lvert \mathcal{A} \times \mathcal{B} \times \mathcal{C} \rvert &= \lvert \mathcal{A} \rvert \cdot \lvert \mathcal{B} \rvert \cdot \lvert \mathcal{C} \rvert \\ &= 3 \cdot 2 \cdot 3 \\ &= 18 \end{align*}

Note Cartesian Product: LaTeX

The LaTeX command \times is for the cartesian product symbol \times

Note Cartesian Product: Python

In Python, you can use the itertools library to create a cartesian product between two sets using the product function.

Cartesian Power

A cartesian power is also possible for any integer n as

\begin{align*} \mathcal{A}^n &= \mathcal{A} \times \mathcal{A} \times \ldots \times \mathcal{A} \\ &= \{ (x_1, x_2, \ldots, x_n):x_1,x_2,\ldots,x_n \in \mathcal{A}\} \end{align*}

CautionCartesian Power: Example

One famous cartesian power is \mathbb{R}^2, also known as the cartesian plane or a two-dimensional plane.

\mathbb{R} \times \mathbb{R} = \mathbb{R}^2

\mathbb{R}^3 three-dimensional planes are also possible.

\mathbb{R} \times \mathbb{R} \times \mathbb{R} = \mathbb{R}^3

And we can generalize up to n dimensions.

\mathbb{R} \times \mathbb{R} \times \ldots \times \mathbb{R} = \mathbb{R}^n

In the field of Data Science, both at GW and beyond, we frequently operate in high-dimensional spaces, sometimes encompassing thousands or even millions of dimensions:

\mathbb{R}^{1{,}000} \quad \text{or} \quad \mathbb{R}^{1{,}000{,}000}

Modern machine learning models can reach even greater scales. For instance, GPT-4 is rumored to involve computations in spaces with trillions of parameters:

\mathbb{R}^{1{,}000{,}000{,}000{,}000{,}000}

How can we reason about learning and structure in such vast spaces? The answer lies in the powerful mathematical foundations of Linear Algebra, Calculus, and Optimization, the core tools explored throughout this website.

Note Cartesian Power: Concept Check

What are the elements of \mathcal{A}^3?

\mathcal{A} = \{1,2\}

\{ (1,1), (1,2), (2,1), (2,2) \}\{ (1,1,1), (1,1,2), (1,2,1), (1,2,2), (1,1,1), (1,1,2), (1,2,1), (1,2,2) \}\{ (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) \}\{ (1,(1,1)), (1,(1,2)), (1,(2,1)), (1,(2,2)), (2,(1,1)), (2,(1,2)), (2,(2,1)), (2,(2,2)) \}

The correct answer is \{ (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2) \} because the cartesian product \mathcal{A}^3 consists of all ordered triples where each element of the triple is taken from the set \mathcal{A}.

Since \mathcal{A} has 2 elements, there are 2^3 = 8 possible ordered triples.

Note Cartesian Power: LaTeX

The LaTeX command \mathcal{A}^n or the caret symbol is used to denote powers \mathcal{A}^n.

Note Cartesian Power: Python

In Python, you can use the itertools library to create a cartesian power of specific n order by using the repeat argument of the product function.

Cartesian Product: Exercises

Tip Cartesian Product: Exercise 1

A dataset for the purposes of supervised learning (a machine learning type), usually denoted \mathcal{D} consists of input features x_{i} and target labels y_{i} from i = 1, \ldots, n observations.

\mathcal{D} = \{ (x_i, y_i) \}_{i=1}^{n}

Show that \mathcal{D} is indeed a subset of the cartesian product between the set of features and targets \mathcal{X} \times \mathcal{Y} using set-builder notation.

\mathcal{D} \subseteq \mathcal{X} \times \mathcal{Y}

Tip Cartesian Product: Exercises 2-6

Given the following sets:

\mathcal{A} = \{ \text{d},\text{a}\} \ \ \mathcal{B} = \{ \text{t},\text{a}\} \ \ \mathcal{C} = \{ \text{s},\text{c}, \text{i}\};

write the corresponding sets to the following cartesian products:

2. \mathcal{A}^2
3. \mathcal{A} \times \emptyset
4. \mathcal{A} \times \mathcal{B}
5. \mathcal{B} \times \mathcal{C}
6. \mathcal{A} \times \mathcal{B} \times \mathcal{C}

Hammack, Richard H. 2013. Book of Proof. Richard Hammack.