Cartesian Product

The Cartesian product is an operation performed between two sets.

Definition

Given two sets \( A \) and \( B \), the Cartesian product \( A \times B \) is the set of all ordered pairs \( (a,b) \), where the first element \( a \) belongs to set \( A \), and the second element \( b \) belongs to set \( B \).

In mathematical notation, the Cartesian product is written as follows:

It is read as "A times B" or "A Cartesian product B".

A Practical Example

To understand how to calculate a Cartesian product, it is helpful to start with a simple example.

Consider two sets \( A \) and \( B \), containing two and three elements, respectively.

The Cartesian product \( A \times B \) is the following set:

Each element of the Cartesian product \( A \times B \) is an ordered pair.

Graphically, the elements of the two sets are connected by these relationships.

Note. The elements of the Cartesian product do not belong to sets \( A \) or \( B \) themselves. They are objects of a different kind: ordered pairs formed from elements of \( A \) and \( B \).

The ordered pairs in the Cartesian product can also be represented as coordinates \( (x,y) \) on a Cartesian plane.

Representing the Cartesian Product

The Cartesian product can be represented in several ways:

• A Cartesian diagram
  In a Cartesian diagram, the elements of set \( A \) are placed on the \( x \)-axis, or horizontal axis, while the elements of set \( B \) are placed on the \( y \)-axis, or vertical axis. Each pair \( (a,b) \) in the Cartesian product \( A \times B \) corresponds to a unique point on the Cartesian plane, with \( x=a \) and \( y=b \).
  
• A double-entry table
  In a double-entry table, the rows contain the elements of the first set \( A \), while the columns contain the elements of the second set \( B \). Each cell of the table, or matrix, contains the ordered pair \( (a,b) \) formed by the corresponding row element and column element.
  

  Note. A tabular representation of the Cartesian product \( A \times B \) is especially useful when the elements of one or both sets are not numbers.

• Tree diagram
  The Cartesian product can also be visualized as a tree. The root represents the starting point. From there, each element of \( A \) creates a branch and a new node. From each of these nodes, further branches extend, one for each element of \( B \). The terminal nodes of the tree, called leaves, represent the ordered pairs \( (a,b) \) in the Cartesian product \( A \times B \).
  

  Note. When the same idea is extended to several sets \( A_1, A_2, \dots, A_k \), the tree becomes deeper. At each level, the number of branches corresponds to the number of elements in the set associated with that level. The final leaves represent the ordered \( k \)-tuples \( (a_1, a_2, \dots, a_k) \). This visualization is particularly useful in computer science for modeling search spaces, automata, and hierarchical data structures.

What Is an Ordered Pair?

An ordered pair \( (a,b) \) is a pair of objects in which \( a \) is the first element and \( b \) is the second element.

An ordered pair is written using parentheses, with the two elements separated by a comma.

The elements \( a \) and \( b \) do not necessarily have to be different.

The order of the elements matters

In an ordered pair, the order of the elements is essential.

Example

The ordered pairs \( (2,4) \) and \( (4,2) \) are different. They contain the same values, but in a different order.

These two ordered pairs represent different coordinates on the Cartesian plane \( (x,y) \).

When are two ordered pairs equal?

Given two ordered pairs \( (a,b) \) and \( (c,d) \), the two pairs are equal only if the first element of the first pair is equal to the first element of the second pair, \( a=c \), and the second element of the first pair is equal to the second element of the second pair, \( b=d \).

The Commutative Property of the Cartesian Product

The Cartesian product is not commutative.

Example

 

 

It is clear that \( A \times B \ne B \times A \), because the order of the elements matters in an ordered pair, unlike in an ordinary set.

The difference becomes especially clear when the two Cartesian products are represented on a Cartesian diagram.

Note. The only case in which \( A \times B = B \times A \) is when \( A = B \). If the two sets \( A \) and \( B \) are identical, the Cartesian product satisfies the commutative property.

The Distributive Property

The Cartesian product of two sets is distributive with respect to union and intersection.

Proof

The Cartesian Product of \( n \) Sets

The Cartesian product is a fundamental operation that extends beyond two sets. It can be applied to any number of sets.

Given \( n \) sets \( A_1, A_2, \dots, A_n \), their Cartesian product, denoted by \( A_1 \times A_2 \times \dots \times A_n \), is the set of all ordered \( n \)-tuples \( (a_1, a_2, \dots, a_n) \) such that each component \( a_i \) belongs to the corresponding set \( A_i \): $$ A_1 \times A_2 \times \dots \times A_n = \{ (a_1, a_2, \dots, a_n) \mid a_i \in A_i, \quad \forall i = 1,2,\dots,n \} $$

In other words, each coordinate of an ordered \( n \)-tuple is chosen from the corresponding set in the sequence.

More generally, when several sets are involved, the elements of the Cartesian product are \( k \)-tuples, that is, ordered sequences of \( k \) elements, with each component taken from a specific set.

Example

Consider the following three sets:

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

$$ B = \{a,b,c\} $$

$$ C = \{X,Y\} $$

Their Cartesian product is:

\[ A \times B \times C = \{ (1,a,X), (1,a,Y), (1,b,X), (1,b,Y), (1,c,X), (1,c,Y), (2,a,X), (2,a,Y), (2,b,X), (2,b,Y), (2,c,X), (2,c,Y) \} \]

The total number of elements in the Cartesian product is simply the product of the cardinalities of the individual sets:

\[ |A \times B \times C| = |A| \cdot |B| \cdot |C| = 2 \times 3 \times 2 = 12 \]

In this case, the Cartesian product contains 12 ordered triples.

In general, when forming the Cartesian product of several sets, the number of resulting tuples is always equal to the product of the sizes of the sets involved.

The Cartesian Product of a Set with Itself

The Cartesian product can also be applied to a set with itself.

If a set \( A \) is multiplied by itself \( k \) times, the result is:

\[ A^k = A \times A \times \dots \times A \]

The elements of \( A^k \) are all possible ordered \( k \)-tuples formed from elements of \( A \). If \( A \) contains \( n \) elements, then the number of elements in \( A^k \) is:

\[ |A^k| = n^k \]

Example

Consider the set:

$$ A = \{1,2,3\} $$

The Cartesian product \( A \times A \) consists of all possible ordered pairs:

$$ A \times A = \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \} $$

Since \( A \) contains \( n = 3 \) elements, the number of ordered pairs in the Cartesian product is:

\[ |A^2| = 3^2 = 9 \]

Instead of writing \( A \times A \), it is common to use the notation \( A^2 \):

$$ A^2 = A \times A = \{ (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3) \} $$

The notation changes, but the meaning remains the same.

Example 2

Now consider the set \( A = \{0,1\} \) and let \( k = 3 \). The Cartesian product \( A^3 \) is:

\[ A^3 = A \times A \times A = \{ (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) \} \]

Since \( A \) contains \( n = 2 \) elements, the number of ordered triples is:

\[ |A^3| = 2^3 = 8 \]

In general, this principle applies to any Cartesian product in which a set is multiplied by itself \( k \) times.

Key Observations

• If a set \( A \) has \( n \) elements and a set \( B \) has \( m \) elements, then each element of \( A \) can be paired with each element of \( B \). This produces exactly \( n \cdot m \) ordered pairs. Therefore, the number of elements in \( A \times B \) is:

\[ |A \times B| = |A| \cdot |B| = n \cdot m \]

Note: This property extends naturally to several sets. If we have \( k \) sets \( A_1, A_2, \dots, A_k \), with respective cardinalities \( n_1, n_2, \dots, n_k \), then their Cartesian product contains:

\[ |A_1 \times A_2 \times \dots \times A_k| = n_1 \cdot n_2 \cdot \dots \cdot n_k \]

This generalization is widely used in combinatorics, probability theory, and several areas of computer science, including state-space exploration and relational databases.