Cartesian Products

How can we build the coordinate plane out of nothing but sets? A point in $\mathbb{R}^2$ is a pair of real numbers. But "pair" is not itself a primitive notion in set theory. It has to be manufactured from sets we already trust. Once we know how to encode an ordered pair $(a,b)$ so that $(a,b) = (c,d)$ exactly when $a=c$ and $b=d$ , a natural question follows. Given two sets $A$ and $B$ , what is the set of all ordered pairs with first coordinate in $A$ and second coordinate in $B$ ? This set is the Cartesian product $A \times B$ . It is named after René Descartes, whose coordinate geometry made the pairing of numbers into a picture worth living in. The Cartesian product matters because it is the algebraic engine behind relations and functions. A function $f : A \to B$ is nothing more than a special subset of $A \times B$ . A relation on a set is a subset of $A \times A$ . A graph, a group action, an equivalence — all of these are dressed-up subsets of a Cartesian product. Without a rigorous product construction, none of these ideas has a home in pure set theory. This article treats the product as an object built from sets we already have. It proves that it exists as a set, not just a "collection." It also works out the exact identities that let you distribute products over unions and intersections. The big picture is that Cartesian products give us a systematic way to combine sets into structured, ordered collections. This is the first genuinely two-dimensional construction in the whole hierarchy of set-building tools. After pairing, union, and power set, the product is the tool that lets sets talk about position and coordinates. It generalizes smoothly to finite tuples of arbitrary length. With more delicate machinery involving the Axiom of Choice, it also extends to products of infinitely many sets at once. This article gives the precise definition of $A \times B$ and of $n$ -tuples. It proves that $A \times B$ is a legitimate set under the axioms of set theory. It establishes the core distributive identities relating products to unions and intersections. It works through concrete numerical examples to make every identity tangible. It closes by placing the Cartesian product in its proper context. There, it serves as a stepping stone toward relations, functions, and eventually the Axiom of Choice.

Key takeaways

$A \times B$ is the set of all ordered pairs $(a,b)$ with $a \in A$ and $b \in B$ ; it is proved to be a genuine set using Power Set and Separation.
$A \times B$ generally differs from $B \times A$ , and $|A \times B| = |A|\cdot|B|$ for finite sets.
Products distribute over unions and intersections: $A \times (B \cup C) = (A\times B)\cup(A\times C)$ , and likewise for $\cap$ , on both the left and the right factor.
Ordered $n$ -tuples are built recursively from ordered pairs, e.g. $(a,b,c) := ((a,b),c)$ , giving $A_1\times A_2\times \cdots \times A_n$ .
The product does not distribute nicely over set difference in a naive symmetric way without care, and $A\times\varnothing = \varnothing$ for every $A$ .
Key idea: the Cartesian product turns two sets into one new set of ordered, structured pairs, and it is the raw material out of which relations and functions are defined.

Where this lives today

Cartesian products are the silent scaffolding underneath enormous swaths of mathematics and its applications. In pure mathematics, every relation is by definition a subset of a Cartesian product $A\times B$ (or $A\times A$ ), and every function $f:A\to B$ is identified with its graph, a special subset of $A\times B$ in which each first coordinate appears exactly once — this is the standard route by which functions are given a fully set-theoretic definition, building directly on the material here. In topology, the product topology on $X \times Y$ is built from the Cartesian product of the underlying sets, equipped with a basis generated from open sets in each factor; in linear algebra, $\mathbb{R}^n$ itself is (as a set) the $n$ -fold product $\mathbb{R}\times\cdots\times\mathbb{R}$ , with vector addition and scalar multiplication added on top. In computer science and databases, the relational model represents a database table as a subset of a Cartesian product of "domains" (columns), and the SQL `CROSS JOIN` operation literally computes a Cartesian product of two tables. In probability theory, the product sample space for two independent experiments is the Cartesian product of the two individual sample spaces, and product measures are built by extending measures compatibly across such products. In cryptography and coding theory, product constructions (e.g. product codes, where a message array is encoded by treating rows and columns as independent codewords) exploit exactly the "grid" structure of $A\times B$ pictured in the figure above. Finally, generalizing the product to infinitely many factors — the product $\prod_{i \in I} A_i$ of a possibly infinite family of sets — requires selecting one element from each factor simultaneously, and proving this can always be done for arbitrary nonempty $A_i$ is precisely the content of the Axiom of Choice, one of the deepest and most consequential axioms among the axioms of set theory.

Ask the tutor: How does the definition of a function as a special subset of $A \times B$ connect to the Axiom of Choice when we need to pick one output for every input across an infinite domain?

A

Intuition

Think of $A$ as a set of row-labels and $B$ as a set of column-labels. The product $A \times B$ is the entire grid of cells you get by choosing one label from each: it is exactly the abstract version of a multiplication table or a coordinate grid. If $A = \{1,2\}$ and $B = \{x,y,z\}$ , then $A\times B$ has six elements, one for every cell of a $2\times 3$ grid — and this is no coincidence, since $|A\times B| = |A|\cdot|B|$ for finite sets, which is why the construction is called a "product" at all. The order matters. The pair $(1,x)$ lives in $A \times B$ , but $(x,1)$ does not — it isn't even well-formed as an element of $A\times B$ unless $x \in A$ and $1 \in B$ as well. This asymmetry is the entire point: a Cartesian product remembers which coordinate came from which set, and this is exactly the structure needed to define a function's graph, since a function must assign to each input exactly one output, and the graph is a very particular kind of subset of the product where each first coordinate appears only once.

Figure

The grid picture of A × B for A = {1,2}, B = {x,y,z}

Why A × B is a legitimate set

Before proving identities about $A\times B$ , we must confirm it deserves to be called a set at all — the defining formula " $\{(a,b) \mid a\in A, b\in B\}$ " is not automatically a set by naive comprehension; in ZFC, unrestricted comprehension is forbidden (it leads to Russell's paradox), so we must show $A\times B$ can be carved out, via the Axiom of Separation, from some set we already know to exist.

A

(a,b) = \{\{a\},\{a,b\}\}

A_1,\dots,A_n

n

The core identities

We now record and prove the identities relating $\times$ to $\cup$ and $\cap$ . Throughout, $A, B, C$ denote arbitrary sets.

A, B, C

\subseteq

Note that the proof technique used throughout is extensionality-based double inclusion together with propositional logic: each product identity is reduced, via the defining biconditional for $\times$ , to a corresponding tautology of first-order/propositional logic ( $\wedge$ distributing over $\vee$ , and idempotence of $\wedge$ ). This is non-circular: it uses only the definitions of $\times, \cup, \cap, \varnothing$ and elementary logic, never any theorem depending on the result being proved.

Worked examples

Example 1 (a genuinely asymmetric numeric check). Let

A = \{1,2\}, \qquad B = \{2,3\}, \qquad C = \{3,4,5\}.

We verify identity (1), $A \times (B\cup C) = (A\times B)\cup(A\times C)$ , by brute enumeration — this is a completeness check on the proof, not a substitute for it. First, $B \cup C = \{2,3\}\cup\{3,4,5\} = \{2,3,4,5\}$ . So

A \times (B\cup C) = \{1,2\}\times\{2,3,4,5\}

has $|A|\cdot|B\cup C| = 2\cdot 4 = 8$ elements:

\{(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5)\}.

Next compute the two pieces on the right side. We have

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

A\times C = \{1,2\}\times\{3,4,5\} = \{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\}.

Their union is

(A\times B)\cup(A\times C) = \{(1,2),(1,3),(2,2),(2,3)\}\cup\{(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)\}.

Taking the union means listing each pair once even though $(1,3)$ and $(2,3)$ appear in both sets (since $3 \in B \cap C$ ). The result is

\{(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5)\},

which has exactly $8$ elements ( $|A\times B|+|A\times C|-|A\times B \cap A\times C| = 4+6-2=8$ , matching by inclusion–exclusion since $(1,3),(2,3)$ are shared). Comparing element-by-element with $A\times(B\cup C)$ computed above, the two sets are identical. This confirms identity (1) concretely and, importantly, shows the union operation must correctly merge the overlap coming from $B\cap C = \{3\}$ — a feature a careless symmetric example (say $B=C$ ) would never expose.

Example 2 (intersection identity with a genuinely nonempty but non-trivial overlap, and a 3-tuple check). Let

A = \{a,b,c\}, \qquad B = \{1,2,3\}, \qquad C = \{2,3,4\}.

We verify identity (2), $A\times(B\cap C) = (A\times B)\cap(A\times C)$ . Since $B \cap C = \{2,3\}$ ,

A \times (B\cap C) = \{a,b,c\}\times\{2,3\} = \{(a,2),(a,3),(b,2),(b,3),(c,2),(c,3)\},

a set of $3 \cdot 2 = 6$ pairs. Now compute both large products:

A\times B = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3),(c,1),(c,2),(c,3)\} \quad (9 \text{ pairs}),

A\times C = \{(a,2),(a,3),(a,4),(b,2),(b,3),(b,4),(c,2),(c,3),(c,4)\} \quad (9 \text{ pairs}).

Intersecting these two 9-element sets keeps exactly the pairs appearing in both lists — that is, pairs $(x,y)$ with $y \in \{1,2,3\}\cap\{2,3,4\} = \{2,3\}$ :

(A\times B)\cap(A\times C) = \{(a,2),(a,3),(b,2),(b,3),(c,2),(c,3)\},

which is exactly $A\times(B\cap C)$ , confirming the identity with $6$ matching elements on each side (not $9$ , illustrating that intersecting the products is strictly smaller than either factor product, as it must be since $B \cap C \subsetneq B, C$ ). As a bonus, we build a genuine $3$ -tuple example to illustrate the recursive tuple definition. Take $A_1 = \{a,b\}$ , $A_2=\{1,2\}$ , $A_3=\{\alpha\}$ . Then

A_1\times A_2 \times A_3 = (A_1\times A_2)\times A_3.

First $A_1 \times A_2 = \{(a,1),(a,2),(b,1),(b,2)\}$ , a $4$ -element set. Then

(A_1\times A_2)\times A_3 = \big\{\big((a,1),\alpha\big),\big((a,2),\alpha\big),\big((b,1),\alpha\big),\big((b,2),\alpha\big)\big\},

and by the recursive definition, $((a,1),\alpha) =: (a,1,\alpha)$ , and so on, giving the expected

A_1\times A_2\times A_3 = \{(a,1,\alpha),(a,2,\alpha),(b,1,\alpha),(b,2,\alpha)\}

with $2\cdot 2\cdot 1 = 4$ elements, exactly matching $|A_1|\cdot|A_2|\cdot|A_3|$ .

\times

Scope, edge cases & common traps

Situation	What holds	What fails / must be checked
$A = B$	$A\times A = A^2$ ; identities specialize but reveal nothing new	Don't use $A=B$ as your only test case — it hides ordering bugs
One factor empty	$A\times\varnothing=\varnothing\times A=\varnothing$ for every $A$ , even $A=\varnothing$	$A\times B=\varnothing$ implies $A=\varnothing$ or $B=\varnothing$ (converse of the above)
Commutativity	none in general: $A\times B \neq B\times A$ unless $A=B$ or one is empty	Never assume $(a,b)=(b,a)$ ; only true if $a=b$
Associativity	$A\times(B\times C) \neq (A\times B)\times C$ as sets (different element shapes)	Usually identified "up to relabeling," but not literally equal — this is why tuples are defined recursively rather than via a single flattening axiom
Distributing over $\setminus$ (difference)	$A\times(B\setminus C) = (A\times B)\setminus(A\times C)$ holds with a shared factor	Mixing all four sets independently, as in the counterexample, fails
Infinite index sets	Finite products extend to arbitrary products $\prod_{i\in I} A_i$	Existence of a choice function selecting one element from each nonempty $A_i$ needs the Axiom of Choice when $I$ is infinite

Common trapThe classic error: forgetting that the product's identities require the same fixed factor on both sides

The single most common mistake is writing down a "distributive-looking" identity where the sets appearing on the left do not literally match the sets used to reconstruct the right, most often by silently swapping which factor is "shared." The Theorem's four identities all have a common factor kept identical on both sides of the equation ( $A$ in (1)–(2), $C$ in (3)–(4)). Any variant identity — such as the tempting but false $(A\times B)\setminus(C\times D) = (A\setminus C)\times(B\setminus D)$ exhibited above — must be proved from scratch by the same double-inclusion method, not assumed by analogy with $\cup$ and $\cap$ .

The mathematician behind it

Origins · 1 minRené Descartes and how this was discovered

René Descartes

1596–1650 · Analytic geometry and the invention of coordinates

Descartes was a French philosopher and mathematician whose La Géométrie (1637) introduced the systematic use of coordinates to translate geometric problems into algebraic ones — and vice versa. By representing a point in the plane as an ordered pair of numbers, and a curve as an equation relating those numbers, Descartes fused geometry and algebra into what we now call analytic geometry. The set-theoretic Cartesian product is the direct abstract descendant of his coordinate idea: instead of pairs of real numbers specifically, we allow pairs drawn from any two sets whatsoever, with the ordered pair itself later given a rigorous foundation by Kuratowski in the 20th century.

History

- 1637 — Descartes publishes La Géométrie, introducing coordinate axes and representing points as ordered pairs of numbers.

- 1895 — Georg Cantor develops the foundations of set theory, including cardinal arithmetic that would later formalize

|A\times B| = |A|\cdot|B|

- 1910 — Whitehead and Russell, in Principia Mathematica, treat ordered pairs and relations using ad hoc devices lacking a purely set-theoretic reduction.

- 1921 — Kazimierz Kuratowski gives the now-standard set-theoretic definition

(a,b) = \{\{a\},\{a,b\}\}

, making the Cartesian product fully rigorous within ZF-style set theory.

- 1920s–1930s — Zermelo–Fraenkel axioms (with Skolem's refinements) settle the axiomatic basis (Pairing, Union, Power Set, Separation) needed to prove

A\times B

exists as a set, as used in the Theorem above.

A \times B

the same set as

B \times A

No, not in general. Elements of $A\times B$ are pairs $(a,b)$ with $a\in A$ , $b \in B$ , while elements of $B\times A$ are pairs $(b,a)$ with $b\in B$ , $a \in A$ . If $a \neq b$ , then $(a,b) \neq (b,a)$ as ordered pairs (this is exactly the content of the Kuratowski property $(x,y)=(u,v)\iff x=u\wedge y=v$ ), so unless $A = B$ or one of $A,B$ is empty, $A\times B$ and $B\times A$ contain genuinely different elements and are unequal sets. There is, however, always a natural bijection $A\times B \to B\times A$ sending $(a,b)\mapsto(b,a)$ , so the two products are equal in cardinality but not as literal sets.

Why isn't

(A\times B)\times C

literally the same set as

A\times(B\times C)

Because the Kuratowski encoding makes an element of $(A\times B)\times C$ have the shape $((a,b),c)$ , while an element of $A\times(B\times C)$ has the shape $(a,(b,c))$ — these are different sets as raw objects (one has an ordered pair as first coordinate, the other has one as second coordinate). They are naturally in bijection via $((a,b),c)\mapsto(a,(b,c))$ , and in practice mathematicians identify them "up to relabeling" and just write $A\times B\times C$ . But the definition of the $n$ -tuple given in this article resolves the ambiguity by fixing a specific convention: nest pairs from the left, i.e. $(a_1,\dots,a_n) := ((a_1,\dots,a_{n-1}),a_n)$ , so that $A_1\times\cdots\times A_n$ is unambiguous as a literal set.

Does

A \times B = A \times C

imply

B = C

Only if $A \neq \varnothing$ . If $A$ is nonempty, pick any $a_0 \in A$ ; then for any $b$ , $b \in B \iff (a_0,b) \in A\times B = A\times C \iff (a_0,b)\in A\times C \iff b \in C$ (using the defining biconditional for $\times$ twice), so $B = C$ by extensionality. But if $A = \varnothing$ , then $A\times B = \varnothing = A\times C$ for every $B$ and $C$ whatsoever (by identity (5) in the Theorem), so the implication fails completely — $B$ and $C$ can be wildly different sets while $A\times B = A\times C$ both trivially equal $\varnothing$ .

How does the Cartesian product relate to functions and relations?

A relation from $A$ to $B$ is defined to be any subset $R \subseteq A\times B$ ; writing $aRb$ is shorthand for $(a,b)\in R$ . A function $f: A \to B$ is then defined as a relation $f\subseteq A\times B$ satisfying two extra conditions: for every $a\in A$ there exists some $b\in B$ with $(a,b)\in f$ (totality), and if $(a,b)\in f$ and $(a,b')\in f$ then $b=b'$ (single-valuedness). This is exactly how "function" is reduced to pure set theory: the familiar notation $f(a)=b$ is just shorthand for $(a,b)\in f$ . So every relation and every function is, by definition, a particular kind of subset of a Cartesian product, making $A\times B$ the ambient universe in which all such structures live.

Why does the Axiom of Choice become relevant for infinite Cartesian products?

For finitely many sets, one can always explicitly construct an element of $A_1\times\cdots\times A_n$ (assuming each $A_i$ nonempty) just by picking elements one at a time — finitely many choices require no special axiom. For an infinite family $\{A_i\}_{i\in I}$ , the product $\prod_{i\in I}A_i$ is defined as the set of functions $f$ with domain $I$ such that $f(i)\in A_i$ for every $i$ — essentially "infinite tuples." Showing this product is nonempty whenever every $A_i$ is nonempty requires simultaneously selecting one element from each of possibly infinitely many sets with no explicit rule for doing so, and this is precisely the assertion of the Axiom of Choice. In fact "the infinite product of nonempty sets is nonempty" is one of the standard equivalent formulations of the Axiom of Choice itself.

Is the empty set ever an element of A × B?

Yes, this is possible and unrelated to whether $A\times B$ itself is empty. If $\varnothing \in A$ (i.e. $\varnothing$ happens to be an element of $A$ , as can occur since sets can contain other sets, including $\varnothing$ ) and $B$ is nonempty, say $b_0\in B$ , then $(\varnothing, b_0) = \{\{\varnothing\},\{\varnothing,b_0\}\}$ is a perfectly good, non-empty element of $A\times B$ ; note this ordered pair itself is not the empty set (it has two elements, or one if $\{\varnothing\}=\{\varnothing,b_0\}$ , which happens iff $b_0=\varnothing$ ). The set $A\times B$ is empty as a whole if and only if $A=\varnothing$ or $B=\varnothing$ , by identity (5) of the Theorem together with its converse (proved via contraposition: if both are nonempty, pick $a\in A, b\in B$ , then $(a,b)\in A\times B$ , so $A\times B\neq\varnothing$ ).