The Cartesian product is one of the most important constructions in set theory. It owes its name to René Descartes, who introduced the Cartesian coordinate system, making it possible to associate each point in the plane with an ordered pair of real numbers.
This operation lets us move beyond isolated sets and build ordered structures, providing the rigorous foundation for the notions of relation, function, graph, and multidimensional spaces.
Table of Contents
- Formal Definition
- Basic Properties
- Distributive Properties
- Geometric Interpretation
- Cartesian Product of Several Sets
- Relations and Functions
- A Closer Look at Cardinality
- Solved Exercises
- 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 \times B = \{(a, b) \mid a \in A \land b \in B\} \]
The pair \((a, b)\) is ordered: the order of the components matters. Indeed:
\[(a, b) = (c, d) \quad \iff \quad a = c \ \text{and} \ b = d\]
A classic example
Let \(A = \{1, 2\}\) and \(B = \{x, y\}\). Then:
\[ A \times B = \{(1,x), (1,y), (2,x), (2,y)\} \]
Remark: what exactly is an ordered pair?
Intuitively, an ordered pair is just “two elements taken in a certain order”. But in set theory, where everything must be built starting from the single notion of set, we need a precise definition. The most widely adopted is Kuratowski’s:
\[ (a, b) := \{\, \{a\},\ \{a, b\} \,\} \]
One can prove that with this definition the characteristic property \((a,b) = (c,d) \iff a = c \land b = d\) holds, which is in the end the only thing we ask of an “ordered pair”. In practical computations this construction is never used: it serves only to guarantee that the Cartesian product is a well-defined object inside the theory.
Basic Properties
If \(A\) and \(B\) are finite sets, the cardinality of the Cartesian product is given by:
\[ |A \times B| = |A| \cdot |B| \]
Moreover, the Cartesian product is empty precisely when at least one of the two factors is:
\[ A \times B = \varnothing \quad \iff \quad A = \varnothing \ \text{or} \ B = \varnothing \]
In particular, \( A \times \varnothing = \varnothing \times A = \varnothing \).
In general, the Cartesian product is not commutative. More precisely:
\[ A \times B = B \times A \quad \iff \quad A = B \ \text{or} \ A = \varnothing \ \text{or} \ B = \varnothing \]
A simple monotonicity with respect to inclusion also holds: if \(A \subseteq A'\) and \(B \subseteq B'\), then \(A \times B \subseteq A' \times B'\). The check is immediate: if \((a,b) \in A \times B\), then \(a \in A \subseteq A'\) and \(b \in B \subseteq B'\), so \((a,b) \in A' \times B'\).
Distributive Properties
The Cartesian product distributes over the main set-theoretic operations:
- \( A \times (B \cap C) = (A \times B) \cap (A \times C) \)
- \( A \times (B \cup C) = (A \times B) \cup (A \times C) \)
- \( A \times (B \setminus C) = (A \times B) \setminus (A \times C) \)
Proof of distributivity over intersection. Let \((a,x)\in A\times(B\cap C)\). Then \(a\in A\) and \(x\in B\cap C\), that is, \(x\in B\) and \(x\in C\). Hence \((a,x)\in A\times B\) and \((a,x)\in A\times C\), so \((a,x)\in (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\). Therefore \(a\in A\), \(x\in B\), and \(x\in C\), so \(x\in B\cap C\) and \((a,x)\in A\times(B\cap C)\).
Proof of distributivity over union. Let \((a,x)\in A\times(B\cup C)\). Then \(a\in A\) and \(x\in B\cup C\), i.e. \(x\in B\) or \(x\in C\). Hence \((a,x)\in A\times B\) or \((a,x)\in A\times C\), so \((a,x)\in (A\times B)\cup(A\times C)\).
Conversely, let \((a,x)\in (A\times B)\cup(A\times C)\). Then \(a\in A\) and (\(x\in B\) or \(x\in C\)), thus \(a\in A\) and \(x\in B\cup C\), that is, \((a,x)\in A\times(B\cup C)\).
Warning: a common mistake
A frequent temptation is to write
\[ (A \cup C) \times (B \cup D) \stackrel{?}{=} (A \times B) \cup (C \times D) \]
but this identity fails in general. A single counterexample suffices: take \(A = C = \{1\}\), \(B = \{2\}\), \(D = \{3\}\). Then \((A \cup C) \times (B \cup D) = \{1\} \times \{2,3\} = \{(1,2), (1,3)\}\), while \((A \times B) \cup (C \times D) = \{(1,2)\} \cup \{(1,3)\} = \{(1,2),(1,3)\}\). In this particular case the equality happens to hold, but if we take \(A = \{1\}\), \(C = \{2\}\), \(B = \{3\}\), \(D = \{4\}\), we obtain:
\[ (A \cup C) \times (B \cup D) = \{1,2\} \times \{3,4\} = \{(1,3),(1,4),(2,3),(2,4)\} \]
\[ (A \times B) \cup (C \times D) = \{(1,3)\} \cup \{(2,4)\} = \{(1,3),(2,4)\} \]
The two sets are clearly different: the first one also contains the “mixed pairs” \((1,4)\) and \((2,3)\). On the other hand, the following identity does hold and is easy to prove:
\[ (A \cap C) \times (B \cap D) = (A \times B) \cap (C \times D) \]
Geometric Interpretation
When \(A, B \subseteq \mathbb{R}\), the Cartesian product \(A \times B\) corresponds to a region of the Cartesian plane \(\mathbb{R}^2\).
Examples
- \([0,1] \times [0,1]\) is the closed unit square
- \(\mathbb{R} \times \mathbb{R}\) represents the entire Cartesian plane
Cartesian Product of Several Sets
The definition extends naturally to several sets. Given \(n\) sets \(A_1, \dots, A_n\):
\[ A_1 \times A_2 \times \cdots \times A_n = \{(a_1,a_2,\dots,a_n) \mid a_i \in A_i \ \forall i=1,\dots,n\} \]
In particular, the \(n\)-dimensional Euclidean space is defined as:
\[ \mathbb{R}^n = \underbrace{\mathbb{R} \times \mathbb{R} \times \cdots \times \mathbb{R}}_{n \text{ times}} \]
Remark: is the product associative?
Strictly speaking, the sets \((A \times B) \times C\) and \(A \times (B \times C)\) are not equal: the first contains elements of the form \(((a,b),c)\), the second elements of the form \((a,(b,c))\). There is, however, a natural bijection between the two (and with \(A \times B \times C\), understood as the set of ordered triples):
\[ ((a,b),c) \ \longleftrightarrow \ (a,b,c) \ \longleftrightarrow \ (a,(b,c)) \]
For this reason, in practice associativity is taken for granted and one simply writes \(A \times B \times C\) without parentheses.
Relations and Functions
A relation between two sets \(A\) and \(B\) is any subset of the Cartesian product:
\[ R \subseteq A \times B \]
A function \(f: A \to B\) is a particular kind of relation that assigns to each element of \(A\) exactly one element of \(B\):
\[ \forall a \in A, \ \exists! \, b \in B \quad \text{such that} \ (a,b) \in f \]
Real-valued functions of a real variable
A function \(f: \mathbb{R} \to \mathbb{R}\) can be identified with its graph:
\[ G_f = \{(x, f(x)) \mid x \in \mathbb{R}\} \subseteq \mathbb{R} \times \mathbb{R} \]
Geometrically, the graph must satisfy the vertical line test: every vertical line meets the graph in at most one point.
How many functions are there?
The set of all functions from \(A\) to \(B\) is denoted \(B^A\). For finite sets the following formula holds:
\[ |B^A| = |B|^{|A|} \]
There is a nice parallel with \(|A \times B| = |A| \cdot |B|\): in the Cartesian product one chooses two components, one in \(A\) and one in \(B\); for functions \(A \to B\) one chooses a value in \(B\) for each of the \(|A|\) elements of \(A\), which explains the exponent.
A Closer Look at Cardinality
For finite sets, the formula \(|A \times B| = |A| \cdot |B|\) is very intuitive: it just amounts to counting pairs. For infinite sets, however, things are more subtle and the results are often surprising.
A celebrated theorem of Georg Cantor states that there exists a bijection between the points of a line and the points of a plane:
\[ |\mathbb{R} \times \mathbb{R}| = |\mathbb{R}| \]
Informally: the plane contains “as many points as” a line. The same holds for three-dimensional space, and more generally for \(\mathbb{R}^n\) with \(n \geq 1\): all these sets have the same cardinality, denoted by \(\mathfrak{c}\) (the cardinality of the continuum).
This result is less paradoxical than it sounds: the equality concerns only the “number of points” as a set, not the geometric dimension or the topological structure. From a geometric standpoint, a line and a plane remain very different objects.
Solved Exercises
Exercise 1. Let \(A = \{a, b\}\) and \(B = \{1, 2, 3\}\). Determine \(A \times B\) and its cardinality.
Solution: \( A \times B = \{(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)\} \). Cardinality: \(|A \times B| = 2 \times 3 = 6\).
Exercise 2. Show that \(A \times B \neq B \times A\) using \(A = \{1,2\}\) and \(B = \{3\}\).
Solution: \(A \times B = \{(1,3), (2,3)\}\), \(B \times A = \{(3,1), (3,2)\}\). The two sets are different.
Exercise 3. Let \(A = \{1,2,3\}\). Compute \(|A \times A \times A|\) and interpret the result.
Solution: \( |A \times A \times A| = 3 \times 3 \times 3 = 27 \). It represents all the ordered triples whose entries belong to \(\{1,2,3\}\).
Exercise 4. Consider the relation \(R = \{(x,y) \in \mathbb{N} \times \mathbb{N} \mid x \leq y\}\). Is it a function? Justify your answer.
Solution: No, it is not a function. To be a function, every \(x \in \mathbb{N}\) would need to have a unique image; instead, each \(x\) is related to infinitely many values of \(y\) (all natural numbers greater than or equal to \(x\)). For instance \((1,1), (1,2), (1,3) \in R\), so the uniqueness condition fails.
Exercise 5. Decide whether the following relation is a function from \(A = \{1,2,3\}\) to \(B = \{a,b\}\): \[f = \{(1,a), (2,b), (3,a)\}\]
Solution: Yes, it is a function, since every element of \(A\) is associated with exactly one element of \(B\).
Exercise 6. Prove that \( (A \cap C) \times (B \cap D) = (A \times B) \cap (C \times D) \).
Solution: Let \((x,y) \in (A \cap C) \times (B \cap D)\). Then \(x \in A \cap C\) and \(y \in B \cap D\), that is, \(x \in A\), \(x \in C\), \(y \in B\), \(y \in D\). Hence \((x,y) \in A \times B\) and \((x,y) \in C \times D\), so \((x,y) \in (A \times B) \cap (C \times D)\). Conversely, if \((x,y) \in (A \times B) \cap (C \times D)\), then \(x \in A\), \(y \in B\), \(x \in C\), \(y \in D\); therefore \(x \in A \cap C\), \(y \in B \cap D\), and so \((x,y) \in (A \cap C) \times (B \cap D)\).
Exercise 7. Find a counterexample showing that, in general, \( (A \cup C) \times (B \cup D) \neq (A \times B) \cup (C \times D) \).
Solution: Take \(A = \{1\}\), \(B = \{2\}\), \(C = \{3\}\), \(D = \{4\}\). Then \((A \cup C) \times (B \cup D) = \{1,3\} \times \{2,4\} = \{(1,2),(1,4),(3,2),(3,4)\}\), whereas \((A \times B) \cup (C \times D) = \{(1,2),(3,4)\}\). The “mixed pairs” \((1,4)\) and \((3,2)\) belong to the first set but not to the second.
Exercise 8. Let \(A, B, C\) be sets with \(A \neq \varnothing\). Prove that, if \(A \times B = A \times C\), then \(B = C\).
Solution: We show \(B \subseteq C\) (the reverse inclusion is symmetric). Let \(b \in B\). Since \(A \neq \varnothing\), there exists \(a \in A\), so \((a,b) \in A \times B\). By hypothesis \(A \times B = A \times C\), hence \((a,b) \in A \times C\), i.e. \(b \in C\). The assumption \(A \neq \varnothing\) is essential: if \(A = \varnothing\), then \(A \times B = A \times C = \varnothing\) for any \(B\) and \(C\), and the conclusion fails.
Conclusion
The Cartesian product is much more than a mere operation on sets: it is the fundamental tool that allows us to build the notions of relation, function, and geometric space in a rigorous way. Thanks to this construction, modern mathematics is able to move from the idea of a “set” to the rich structures we use every day in analysis, algebra, and geometry.