4.3 Cartesian product

Definition of Cartesian product

The Cartesian product is an operation that takes two (or more) sets and produces a new set containing all possible ordered combinations of their elements. If you have a set of shirts and a set of pants, the Cartesian product gives you every possible outfit. This idea underpins coordinate systems, functions, relations, and much of how mathematicians formalize "pairing things together."

Ordered pairs

An ordered pair $(a, b)$ consists of two elements where $a$ comes from set $A$ and $b$ comes from set $B$. The word "ordered" is doing real work here: $(a, b) \neq (b, a)$ unless $a = b$. Think of coordinates on a plane. The point $(2, 5)$ is not the same as $(5, 2)$.

Ordered pairs are the building blocks for defining relations and functions between sets.

Set notation

The Cartesian product of $A$ and $B$ is written:

$A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$

You read this as "A cross B." It means: take every element of $A$, pair it with every element of $B$, and collect all those pairs into a set.

This extends naturally to more than two sets: $A_1 \times A_2 \times \cdots \times A_n$ gives you ordered $n$-tuples instead of pairs.

Visual representation

For finite sets, you can draw a grid. Put the elements of $A$ along one axis and the elements of $B$ along the other. Every intersection point represents one ordered pair.

For example, if $A = \{1, 2\}$ and $B = \{x, y, z\}$, you get a 2-by-3 grid with six points: $(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)$. This is exactly how the Cartesian coordinate plane works, just scaled up to all of $\mathbb{R} \times \mathbb{R}$.

Properties of Cartesian product

Several properties govern how Cartesian products behave. Knowing these saves you from errors and helps you reason about more complex structures.

Cardinality

The number of elements in $A \times B$ equals the product of the sizes of $A$ and $B$:

$|A \times B| = |A| \times |B|$

If $A$ has 3 elements and $B$ has 4, then $A \times B$ has 12 ordered pairs. This extends to multiple sets:

$|A_1 \times A_2 \times \cdots \times A_n| = |A_1| \times |A_2| \times \cdots \times |A_n|$

This property is directly useful in combinatorics and probability when you need to count total possible outcomes.

Non-commutativity

$A \times B \neq B \times A$ in general. The pairs $(a, b)$ and $(b, a)$ are different objects. The only exceptions are when $A = B$ (so both products contain the same pairs) or when either set is empty (both products are then $\emptyset$).

This contrasts with operations like union or intersection, where order doesn't matter. Always pay attention to which set comes first.

Associativity

Strictly speaking, $(A \times B) \times C$ and $A \times (B \times C)$ produce slightly different objects. The first gives pairs like $((a, b), c)$ and the second gives $(a, (b, c))$. However, there's a natural one-to-one correspondence between them, and both correspond to the triple $(a, b, c)$. In practice, mathematicians treat the Cartesian product of multiple sets as producing flat $n$-tuples, so you can write $A \times B \times C$ without worrying about grouping.

Applications in mathematics

Coordinate systems

The Cartesian plane is literally $\mathbb{R} \times \mathbb{R}$: every point $(x, y)$ is an ordered pair of real numbers. Three-dimensional space is $\mathbb{R} \times \mathbb{R} \times \mathbb{R}$, often written $\mathbb{R}^3$. This connection between sets and geometry is what makes analytic geometry possible: you can study geometric shapes using algebraic equations.

Functions and relations

A relation from $A$ to $B$ is any subset of $A \times B$. A function from $A$ to $B$ is a special kind of relation where each element of $A$ is paired with exactly one element of $B$. So when you write $f: A \to B$, you're really picking out a specific subset of $A \times B$ that follows the "one output per input" rule.

Counting and probability

In combinatorics, Cartesian products give you a systematic way to list all possible outcomes. If you roll a die and flip a coin, the sample space is $\{1,2,3,4,5,6\} \times \{H, T\}$, which has $6 \times 2 = 12$ outcomes. This is the formal version of the multiplication principle you've likely already used.

Cartesian product of multiple sets

Ordered n-tuples

An ordered $n$-tuple $(a_1, a_2, \ldots, a_n)$ generalizes ordered pairs to $n$ elements. Each $a_i$ comes from its corresponding set $A_i$. These represent points in $n$-dimensional space and show up throughout linear algebra, statistics, and physics.

Generalization to n dimensions

$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \ldots, a_n) \mid a_i \in A_i \text{ for each } i\}$

When all the sets are the same (say, all equal to $A$), you write $A^n$. For instance, $\mathbb{R}^4$ is the set of all 4-tuples of real numbers. This notation is compact and shows up constantly in higher math and data science.

Cartesian product vs other set operations

Understanding how the Cartesian product differs from union, intersection, and other operations helps you pick the right tool for a given problem.

Union and intersection

• Union $A \cup B$ collects all elements from both sets into one set. No new structure is created.
• Intersection $A \cap B$ picks out elements common to both sets.
• Cartesian product $A \times B$ creates entirely new objects (ordered pairs) that weren't in either original set.

A key distinction: union and intersection keep you in the same "dimension," while the Cartesian product increases dimensionality. Elements of $A \cup B$ are individual elements; elements of $A \times B$ are pairs.

Difference and complement

• Set difference $A \setminus B$ removes from $A$ anything that's also in $B$.
• Complement $A'$ contains everything in the universal set that's not in $A$.

Both of these operations shrink or filter sets. The Cartesian product does the opposite: it combines elements and typically produces a larger set.

Examples and problem-solving

Two-dimensional examples

Coin flips. The sample space for flipping two coins is $\{H, T\} \times \{H, T\} = \{(H,H), (H,T), (T,H), (T,T)\}$. That's 4 outcomes.

Chessboard. A chessboard can be modeled as $\{a, b, c, d, e, f, g, h\} \times \{1, 2, 3, 4, 5, 6, 7, 8\}$, giving 64 squares. Each square is an ordered pair like $(c, 5)$.

Small sets. If $A = \{1, 2\}$ and $B = \{a, b, c\}$, then $A \times B = \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c)\}$ and $|A \times B| = 6$.

Higher-dimensional applications

• 3D space uses $\mathbb{R}^3$ for modeling physical objects and environments.
• RGB color is a Cartesian product of three intensity ranges (typically $\{0, \ldots, 255\}^3$), giving over 16 million possible colors.
• Multifactor experiments in science treat each combination of factor levels as a point in a Cartesian product.

Common mistakes

• Ignoring order. Writing $A \times B$ when you mean $B \times A$ gives you different pairs. Always check which set is first.
• Wrong cardinality. Students sometimes add the set sizes instead of multiplying. If $|A| = 3$ and $|B| = 4$, then $|A \times B| = 12$, not 7.
• Missing combinations. When listing elements by hand, use a systematic approach (grid or table) so you don't skip any pairs.

Cartesian product in computer science

Data structures

Multidimensional arrays are essentially Cartesian products of index sets. A 2D array with $m$ rows and $n$ columns stores values at each point in $\{0, \ldots, m-1\} \times \{0, \ldots, n-1\}$. The same idea scales to higher dimensions.

Database theory

In relational databases, the cross join (or Cartesian join) of two tables produces every possible row combination, which is exactly the Cartesian product of the two row sets. Most useful queries then filter this product using conditions (WHERE clauses), which is how JOIN operations work under the hood.

Minimizing unnecessary Cartesian products is a major concern in query optimization, since they can produce enormous intermediate results.

Algorithmic complexity

Computing a full Cartesian product of two sets of size $n$ requires $O(n^2)$ time and space. For $k$ sets of size $n$, it's $O(n^k)$, which grows extremely fast. Efficient algorithms often avoid computing the full product by using filtering, lazy evaluation, or divide-and-conquer strategies.

Historical context

René Descartes' contribution

René Descartes introduced the coordinate system in the 17th century, merging algebra and geometry into what we now call analytic geometry. The Cartesian product and Cartesian plane are named after him (from his Latin name, Cartesius). His insight that geometric points could be represented as pairs of numbers was transformative for mathematics.

Development of set theory

Georg Cantor formalized set theory in the late 19th century, and the Cartesian product became one of its core operations. Cantor's work on infinite sets raised deep questions about Cartesian products of infinite collections, questions that eventually connected to the Axiom of Choice and other foundational topics in mathematical logic.

Advanced concepts

Infinite Cartesian products

You can take the Cartesian product of infinitely many sets. The result is the set of all sequences $(a_1, a_2, a_3, \ldots)$ where each $a_i$ belongs to its corresponding set $A_i$. This comes up in functional analysis and probability theory (for instance, modeling an infinite sequence of coin flips).

The existence of elements in an arbitrary infinite Cartesian product of nonempty sets is guaranteed by the Axiom of Choice, which is not provable from the other standard set theory axioms.

Topology and product spaces

When each set in a Cartesian product carries a topology, the product set can be given a product topology. This is the standard way to study continuity and convergence in multidimensional or infinite-dimensional spaces. Product spaces are central to algebraic topology, functional analysis, and differential geometry.