Cartesian Product

Imagine a chessboard. Its columns (known as files) are labeled by letters from a to h, its rows (known as ranks) are labeled by numbers from 1 to 8. So, every square is identified by a combination of a letter and a number. The set of squares (or, rather, its identifiers) is obtained from the sets $\{a, \ldots h\}$ and $\{1, \ldots 8\}$ through the operation known as Cartesian product. In fact, every coordinate system can be described as a Cartesian product, so this concept is basic for computer graphics and navigation. Cartesian products are also fundamental for theory of relations, and, so, for database theory.

Definition of Cartesian product

The Cartesian product of two sets creates a set of ordered pairs. For example, suppose we have two sets: $$A = \{1, 2, 3\} \ \text{and} \ B = \{5, 6\}.$$ We select an element from $A$ and pair it with an element from $B$, e.g. $$(1, 5)$$ $-$ the elements are enclosed in parenthesis and separated by a comma.

The order in which the elements of an ordered pair are listed is important.

Unless these two elements are the same, switching their order creates a different ordered pair. So, $(1, 5) \ne (5, 1)$. The Cartesian product is denoted by $\times$: $A \times B$. Thus, we can write: $$A \times B = \{(1, 5), (1, 6), (2, 5), (2, 6), (3, 5), (3, 6)\}.$$

The number of elements in a Cartesian product is equal to the number of elements in each operand set multiplied together. So, if $|A| = 5$, $|B|=2$ , then $|A\times B| = 5 \cdot 2 = 10$.

Cartesian product of 3 or more sets

A Cartesian product can also be formed from more than two sets. For instance, we can form the Cartesian product of 3 sets: $A$, $B$ and $C$, by repeatedly selecting one element from each set to form ordered triples.

To create every possible ordered triple from three sets, we can start by forming the Cartesian product of the sets $A$ and $B$, and then choose one element from the set $C$ as a third element of the ordered triple. Then we repeat this, each time choosing a different element from $C$.

Thus, if $$A=\{a, b\}, \ B = \{c, d, e\} \ \text{and} \ C = \{f, g\},$$then $$A\times B \times C=\{(a,c,f), (a,d,f),(a,e,f), (b,c,f), (b,d,f), \\ (b,e,f), (a,c,g), (a,d,g),(a,e,g), (b,c,g), (b,d,g),(b,e,g)\}.$$

We can further generalize the concept of the Cartesian product and define it for any (of course, any positive integer) number of sets $n$. If $A_{1}, \ldots A_{n}$ are sets, their product $A_{1} \times \ldots \times A_{n}$ will be the set

$$\{(a_{1}, \ldots, a_{n}) | a_{1} \in A_{1}, \ldots a_{n} \in A_{n} \}$$of all ordered collections of $n$ elements where the first element is taken from the first set, the second element from the second set and so on.

We refer to ordered collections having $n$ elements as $n$-tuples. A tuple is any finite ordered collection of elements.

Note that if any of the sets is empty, the Cartesian product of those sets is also empty.

If $A=\{a, b, c, d, e\}$ and $B=\emptyset$, then $A \times B = \emptyset$ and $B \times A=\emptyset$.

Properties of Cartesian product

For two non-empty and unique sets $A$ and $B$, $A \times B$ is not equal to $B \times A$. For example, if $A=\{a,b\}$ and $B=\{0, 1, 2\}$, then $$A \times B = \{(a, 0), (a, 1), (a, 2), (b,0), (b,1), (b,2)\}$$ and $$B \times A = \{(0,a),(0,b),(1,a)(1,b),(2,a),(2,b)\}.$$Here, $A \times B \ne B \times A$.

For two sets $A$ and $B$, the Cartesian products $A \times B$ and $B \times A$ are equal if either of the following condition is satisfied:

• both sets are equal
• $A=\emptyset$ or $B=\emptyset$

Conclusion

In this topic, we have learned about a Cartesian product of two or more sets. The concept of a Cartesian product is widely used in mathematics. For example, we can define the concept of a binary relation using a Cartesian product. Also, the Cartesian product is used very often to denote a set of numerical sets, especially in mathematical analysis.