The Cartesian product is a fundamental construction in set theory. Given two sets \(A\) and \(B\), it enables us to form a new set whose elements are ordered pairs, that is, pairs in which not only the elements themselves matter, but also the order in which they appear.
This idea underlies many central notions of mathematics. Relations between sets, functions, graphs of functions, and Cartesian spaces can all be described rigorously by means of the Cartesian product.
The name recalls the Cartesian plane and the work of René Descartes. In the Cartesian plane, every point is associated with an ordered pair of real numbers; in the same way, the Cartesian product formalises the idea of forming all possible ordered pairs by choosing the first element from one set and the second from another.
In this article we introduce the definition of the Cartesian product, study its principal properties, and show how this construction naturally leads to the concepts of relation, function, and Cartesian space.
Contents
- Formal definition
- Ordered pairs and the importance of order
- Fundamental properties
- Properties with respect to set operations
- Geometric interpretation
- Cartesian product of several sets
- Relations and functions
- A closer look at cardinality
- Conclusion
Formal definition
Let \(A\) and \(B\) be two sets. The Cartesian product of \(A\) and \(B\), denoted \(A \times B\), is the set of all ordered pairs \((a,b)\) such that the first element belongs to \(A\) and the second element belongs to \(B\).
In symbols:
\[ A \times B = \{(a,b) \mid a \in A \ \text{and} \ b \in B\}. \]
Thus, forming the Cartesian product \(A \times B\) means pairing every element of \(A\) with every element of \(B\), while respecting the order of the components.
Example
Consider the sets
\[ A=\{1,2\}, \qquad B=\{x,y\}. \]
The Cartesian product \(A \times B\) is given by
\[ A \times B=\{(1,x),(1,y),(2,x),(2,y)\}. \]
Every pair has as its first component an element of \(A\) and as its second component an element of \(B\). For instance, \((1,x)\) belongs to \(A \times B\), whereas \((x,1)\) does not belong to \(A \times B\), since \(x\) is not an element of \(A\) and \(1\) is not an element of \(B\).
Ordered pairs and the importance of order
In the Cartesian product, the elements are not merely sets of two elements, but ordered pairs. This means that the position of the components is essential.
Two ordered pairs are equal if and only if their respective components are equal:
\[ (a,b)=(c,d) \quad \Longleftrightarrow \quad a=c \quad \text{and} \quad b=d. \]
In particular, in general
\[ (a,b) \neq (b,a). \]
The equality \((a,b)=(b,a)\) can hold only in the special case in which \(a=b\). For this reason, when working with the Cartesian product, it is not enough to know which elements occur in the pair: one must also know which element occupies the first position and which occupies the second.
Set-theoretic definition of an ordered pair
Intuitively, an ordered pair is a pair of elements written in a specific order. Nevertheless, within set theory it is also possible to define ordered pairs using only the notion of a set.
A classical definition, due to Kuratowski, is the following:
\[ (a,b):=\{\{a\},\{a,b\}\}. \]
This definition plays no role in ordinary calculations, but it is of considerable theoretical importance: it allows ordered pairs to be constructed entirely within set theory, and it guarantees the fundamental property
\[ (a,b)=(c,d) \quad \Longleftrightarrow \quad a=c \quad \text{and} \quad b=d. \]
In this way the Cartesian product is not taken as an intuitive object, but is reduced to a rigorous construction grounded in set theory.
Fundamental properties
The Cartesian product satisfies a number of elementary properties worth establishing from the outset. These follow directly from the definition and from the fact that the elements of \(A \times B\) are ordered pairs.
Cardinality of the Cartesian product
If \(A\) and \(B\) are finite sets, the number of elements of the Cartesian product is given by the product of the cardinalities:
\[ |A \times B|=|A|\cdot |B|. \]
Indeed, to construct an ordered pair \((a,b)\), one may choose the first component in \(|A|\) ways and, for each such choice, the second component in \(|B|\) ways.
For instance, if \(A\) has \(2\) elements and \(B\) has \(3\) elements, then \(A \times B\) has \(2\cdot 3=6\) elements.
Cartesian product with the empty set
The Cartesian product \(A \times B\) is empty if and only if at least one of the two sets \(A\) and \(B\) is empty:
\[ A \times B=\varnothing \quad \Longleftrightarrow \quad A=\varnothing \ \text{or} \ B=\varnothing. \]
Indeed, if \(A=\varnothing\), it is impossible to choose a first component. If \(B=\varnothing\), it is impossible to choose a second component. In either case, no ordered pair can be formed.
In particular:
\[ A \times \varnothing=\varnothing \qquad \text{and} \qquad \varnothing \times A=\varnothing. \]
The Cartesian product is not commutative
In general the Cartesian product is not commutative. That is, in general \(A \times B\) and \(B \times A\) are not the same set.
The reason is that the elements of \(A \times B\) have as first component an element of \(A\) and as second component an element of \(B\), whereas the elements of \(B \times A\) have their components in the opposite order.
For example, if
\[ A=\{1,2\}, \qquad B=\{x\}, \]
then
\[ A \times B=\{(1,x),(2,x)\}, \]
while
\[ B \times A=\{(x,1),(x,2)\}. \]
The two Cartesian products are different, since the ordered pairs \((1,x)\) and \((x,1)\) do not coincide.
More precisely,
\[ A \times B = B \times A \quad \Longleftrightarrow \quad A=B \ \text{or} \ A=\varnothing \ \text{or} \ B=\varnothing. \]
The Cartesian product therefore becomes commutative only in special cases: when the two sets coincide, or when at least one of them is empty.
Monotonicity with respect to inclusion
The Cartesian product is compatible with set inclusion. If
\[ A \subseteq A' \qquad \text{and} \qquad B \subseteq B', \]
then
\[ A \times B \subseteq A' \times B'. \]
Indeed, if \((a,b)\in A \times B\), then \(a\in A\) and \(b\in B\). Since \(A\subseteq A'\) and \(B\subseteq B'\), it follows that \(a\in A'\) and \(b\in B'\). Hence \((a,b)\in A'\times B'\).
This property expresses a natural fact: enlarging the underlying sets also enlarges the Cartesian product.
Properties with respect to set operations
The Cartesian product behaves in a regular manner with respect to certain set operations, such as intersection, union, and difference. The following properties are direct consequences of the definition of the Cartesian product.
Intersection
For all sets \(A\), \(B\), and \(C\):
\[ A \times (B \cap C) = (A \times B) \cap (A \times C). \]
We prove the equality by establishing both inclusions.
Let \((a,x)\in A\times(B\cap C)\). Then \(a\in A\) and \(x\in B\cap C\), so \(x\in B\) and \(x\in C\). It follows that \((a,x)\in A\times B\) and \((a,x)\in A\times C\), that is,
\[ (a,x)\in (A\times B)\cap(A\times C). \]
This establishes that
\[ A\times(B\cap C)\subseteq (A\times B)\cap(A\times C). \]
Conversely, let \((a,x)\in (A\times B)\cap(A\times C)\). Then \((a,x)\in A\times B\) and \((a,x)\in A\times C\), so \(a\in A\), \(x\in B\), and \(x\in C\). Hence \(x\in B\cap C\), and therefore
\[ (a,x)\in A\times(B\cap C). \]
The reverse inclusion is thereby also established, and consequently
\[ A \times (B \cap C) = (A \times B) \cap (A \times C). \]
Union
The Cartesian product is likewise distributive over union:
\[ A \times (B \cup C) = (A \times B) \cup (A \times C). \]
Indeed, a pair \((a,x)\) belongs to \(A\times(B\cup C)\) if and only if \(a\in A\) and \(x\in B\cup C\), that is, if and only if \(a\in A\) and \(x\) belongs to at least one of \(B\) and \(C\).
In the first case \((a,x)\in A\times B\), while in the second \((a,x)\in A\times C\). Consequently,
\[ (a,x)\in (A\times B)\cup(A\times C). \]
The converse argument establishes the reverse inclusion, so the equality follows.
Difference
An analogous property holds for set difference:
\[ A \times (B \setminus C) = (A \times B) \setminus (A \times C). \]
Indeed, a pair \((a,x)\) belongs to \(A\times(B\setminus C)\) if and only if \(a\in A\), \(x\in B\), and \(x\notin C\).
This is equivalent to saying that \((a,x)\in A\times B\) but \((a,x)\notin A\times C\). Hence
\[ (a,x)\in (A\times B)\setminus(A\times C). \]
This yields the identity:
\[ A \times (B \setminus C) = (A \times B) \setminus (A \times C). \]
A common mistake
Care must be taken not to misapply the distributive properties. In general it is not true that
\[ (A \cup C) \times (B \cup D) = (A \times B) \cup (C \times D). \]
Consider, for instance,
\[ A=\{1\}, \qquad C=\{2\}, \qquad B=\{3\}, \qquad D=\{4\}. \]
Then
\[ (A\cup C)\times(B\cup D)=\{1,2\}\times\{3,4\} \]
and hence
\[ (A\cup C)\times(B\cup D)=\{(1,3),(1,4),(2,3),(2,4)\}. \]
On the other hand,
\[ (A\times B)\cup(C\times D)=\{(1,3)\}\cup\{(2,4)\} =\{(1,3),(2,4)\}. \]
The two sets do not coincide: the first also contains the pairs \((1,4)\) and \((2,3)\), which do not belong to the second.
The correct formula for the intersection of two Cartesian products is instead
\[ (A\cap C)\times(B\cap D)=(A\times B)\cap(C\times D). \]
Indeed, a pair belongs to the left-hand side if and only if its first component belongs to both \(A\) and \(C\), and its second component belongs to both \(B\) and \(D\). This is precisely the condition for belonging simultaneously to \(A\times B\) and to \(C\times D\).
Geometric interpretation
When the sets under consideration are subsets of \(\mathbb{R}\), the Cartesian product acquires a natural geometric interpretation in the Cartesian plane.
If \(A\subseteq \mathbb{R}\) and \(B\subseteq \mathbb{R}\), then \(A\times B\) is the set of all points of the plane whose abscissa lies in \(A\) and whose ordinate lies in \(B\):
\[ A\times B=\{(x,y)\in \mathbb{R}^2 \mid x\in A \ \text{and} \ y\in B\}. \]
In this interpretation, the first component of the ordered pair represents the horizontal coordinate, that is, the abscissa, while the second component represents the vertical coordinate, that is, the ordinate.
Examples
The Cartesian product
\[ [0,1]\times[0,1] \]
represents the closed unit square of the plane, consisting of all points \((x,y)\) such that \(0\leq x\leq 1\) and \(0\leq y\leq 1\).
On the other hand,
\[ \mathbb{R}\times\mathbb{R} \]
coincides with the whole Cartesian plane \(\mathbb{R}^2\), since both the first and second components may be chosen freely among all real numbers.
More generally, if \(A\) and \(B\) are real intervals, the Cartesian product \(A\times B\) determines a rectangular region of the plane, which may be open, closed, or unbounded, depending on the type of intervals considered.
Cartesian product of several sets
The definition of the Cartesian product extends naturally to more than two sets. If \(A_1,A_2,\dots,A_n\) are \(n\) sets, their Cartesian product is the set of all ordered \(n\)-tuples
\[ (a_1,a_2,\dots,a_n) \]
such that the first component belongs to \(A_1\), the second belongs to \(A_2\), and so on up to the last component, which belongs to \(A_n\).
In symbols:
\[ A_1\times A_2\times \cdots \times A_n = \{(a_1,a_2,\dots,a_n) \mid a_i\in A_i \ \text{for every} \ i=1,\dots,n\}. \]
Here too the order of the components is essential: the first component must belong to the first set, the second to the second set, and so forth.
Cartesian powers
When all the sets coincide with a single set \(A\), a more compact notation is used. For example:
\[ A^2=A\times A, \qquad A^3=A\times A\times A. \]
More generally, \(A^n\) denotes the Cartesian product of \(A\) with itself \(n\) times:
\[ A^n=\underbrace{A\times A\times \cdots \times A}_{n \ \text{times}}. \]
The elements of \(A^n\) are thus ordered \(n\)-tuples of elements of \(A\).
Cartesian spaces
A particularly important case arises when \(A=\mathbb{R}\). In this way one defines the \(n\)-dimensional real Cartesian space:
\[ \mathbb{R}^n= \underbrace{\mathbb{R}\times\mathbb{R}\times\cdots\times\mathbb{R}}_{n \ \text{times}}. \]
For instance, \(\mathbb{R}^2\) is the Cartesian plane, whose elements are ordered pairs \((x,y)\), while \(\mathbb{R}^3\) is three-dimensional space, whose elements are ordered triples \((x,y,z)\).
Is the Cartesian product associative?
When the Cartesian product is initially defined as an operation on two sets, a certain qualification is required. The sets
\[ (A\times B)\times C \qquad \text{and} \qquad A\times(B\times C) \]
are not literally equal.
Indeed, the elements of \((A\times B)\times C\) have the form
\[ ((a,b),c), \]
whereas the elements of \(A\times(B\times C)\) have the form
\[ (a,(b,c)). \]
These two objects have different formal structures. There is, however, a natural bijective correspondence between them and the ordered triples \((a,b,c)\):
\[ ((a,b),c) \longleftrightarrow (a,b,c) \longleftrightarrow (a,(b,c)). \]
For this reason, when the context is clear, one simply writes
\[ A\times B\times C \]
and interprets it as the set of ordered triples \((a,b,c)\), with \(a\in A\), \(b\in B\), and \(c\in C\).
Relations and functions
One of the principal reasons the Cartesian product is so important is that it allows relations and functions between sets to be defined rigorously.
Relations
Let \(A\) and \(B\) be two sets. A relation between \(A\) and \(B\) is a subset of the Cartesian product \(A\times B\).
In symbols, a relation \(R\) between \(A\) and \(B\) is a set such that
\[ R\subseteq A\times B. \]
This means that the elements of \(R\) are some of the ordered pairs \((a,b)\), with \(a\in A\) and \(b\in B\). When \((a,b)\in R\), we say that \(a\) is related to \(b\).
Thus the Cartesian product \(A\times B\) contains all possible ordered pairs, while a relation selects only some of these pairs.
Functions
A function from \(A\) to \(B\) is a particular kind of relation between \(A\) and \(B\). Precisely, a function \(f:A\to B\) is a relation \(f\subseteq A\times B\) such that every element of \(A\) is associated with exactly one element of \(B\).
In symbols:
\[ \forall a\in A, \ \exists! \, b\in B \ \text{such that} \ (a,b)\in f. \]
The symbol \(\exists!\) means “there exists a unique”. The above condition therefore asserts two things simultaneously:
- for every \(a\in A\) there exists at least one element \(b\in B\) associated with \(a\);
- such an element \(b\) is unique.
The first condition excludes the possibility that some element of \(A\) is left without an image. The second condition excludes the possibility that a single element of \(A\) is associated with two or more distinct elements of \(B\).
Graph of a function
If \(f:A\to B\) is a function, its graph is the set of ordered pairs formed by each element of the domain and its image:
\[ G_f=\{(a,f(a))\mid a\in A\}. \]
The graph of \(f\) is thus a subset of the Cartesian product \(A\times B\):
\[ G_f\subseteq A\times B. \]
For real functions of a real variable, that is, functions \(f:\mathbb{R}\to\mathbb{R}\), the graph is a subset of the Cartesian plane:
\[ G_f=\{(x,f(x))\mid x\in\mathbb{R}\}\subseteq \mathbb{R}\times\mathbb{R}. \]
In this way the Cartesian product provides the link between the set-theoretic definition of a function and its geometric representation in the plane.
The vertical line test
Geometrically, the graph of a real function of a real variable satisfies the vertical line test. This means that, once a value of the independent variable \(x\) is fixed, there can exist at most one corresponding value of the dependent variable \(y\).
In particular, if \(f:\mathbb{R}\to\mathbb{R}\), then every vertical line \(x=a\), with \(a\in\mathbb{R}\), meets the graph of the function in exactly one point.
If, instead, a vertical line met the graph in two distinct points, then two different values of \(y\) would be associated with the same value \(a\), and the relation would no longer be a function.
How many functions are there between two finite sets?
If \(A\) and \(B\) are finite sets, the set of all functions from \(A\) to \(B\) is denoted by \(B^A\).
Its cardinality is
\[ |B^A|=|B|^{|A|}. \]
Indeed, to define a function \(f:A\to B\), one must choose an element of \(B\) as the image of each element of \(A\). If \(A\) has \(|A|\) elements and, for each of them, there are \(|B|\) possible choices, the total number of functions is \(|B|^{|A|}\).
This formula must be distinguished from that of the Cartesian product:
\[ |A\times B|=|A|\cdot |B|. \]
In the Cartesian product, one chooses a first component in \(A\) and a second component in \(B\). To construct a function from \(A\) to \(B\), by contrast, one chooses an element of \(B\) for every element of \(A\); for this reason a power appears, rather than a product.
A closer look at cardinality
For finite sets, the cardinality of the Cartesian product is described by the formula
\[ |A\times B|=|A|\cdot |B|. \]
This formula has a very concrete meaning: if \(A\) has a certain number of elements and \(B\) has a certain number of elements, then the Cartesian product \(A\times B\) contains all possible ordered pairs obtained by choosing a first component in \(A\) and a second component in \(B\).
When one passes to infinite sets, however, the notion of cardinality becomes more delicate. In this case the elements can no longer simply be counted one by one; instead, sets are compared by means of bijective correspondences.
Two sets have the same cardinality when there exists a bijective correspondence between them, that is, a function associating with each element of the first set a unique element of the second, such that every element of the second set is the image of exactly one element of the first.
A fundamental result of set theory states that
\[ |\mathbb{R}\times\mathbb{R}|=|\mathbb{R}|. \]
This means that the Cartesian plane \(\mathbb{R}^2\) and the real line \(\mathbb{R}\) have the same cardinality. In other words, from the point of view of the number of elements, there exists a bijective correspondence between the points of a line and the points of a plane.
The same holds, more generally, for every real Cartesian space \(\mathbb{R}^n\), with \(n\geq 1\):
\[ |\mathbb{R}^n|=|\mathbb{R}|. \]
This cardinality is denoted by \(\mathfrak{c}\) and is called the cardinality of the continuum.
It is important not to confuse cardinality with geometric structure. The fact that \(\mathbb{R}\) and \(\mathbb{R}^2\) have the same cardinality does not mean that a line and a plane are geometrically the same object. They have the same number of points in the set-theoretic sense, but they possess profoundly different geometric and topological properties.
This example shows that the Cartesian product, although a simple construction to define, leads swiftly to some of the deepest questions in mathematics.
Conclusion
The Cartesian product is an essential construction in set theory. Starting from given sets, it allows one to form sets of ordered pairs and, more generally, of ordered \(n\)-tuples.
Its importance stems not merely from the definition itself, but above all from the structures it makes possible to construct. Relations between sets, functions, graphs of functions, and Cartesian spaces can all be described rigorously by means of the Cartesian product.
For this reason, a thorough understanding of the Cartesian product provides a basic tool that recurs throughout mathematics, from algebra to geometry and from analysis to set theory.