Cartesian product
The Cartesian product is a construction in set theory that combines objects from two or more sets while preserving the position from which each object was selected. For sets (A) and (B), their Cartesian product is the set
[ A\times B={(a,b)\mid a\in A\ \text{and}\ b\in B}, ]
where ((a,b)) denotes an ordered pair. Equality of ordered pairs is determined by their coordinates:
[ (a,b)=(a',b')\quad\Longleftrightarrow\quad a=a'\ \text{and}\ b=b'. ]
The ordering of the coordinates distinguishes the Cartesian product from operations based only on membership. In general, (A\times B) and (B\times A) are not equal as sets, although the coordinate-exchange map ((a,b)\mapsto(b,a)) gives a canonical bijection between them.
Interpretation and elementary properties
When (A) and (B) are finite, the elements of (A\times B) can be arranged in a rectangular array. Each row corresponds to an element of (A), while each column corresponds to an element of (B). The entry at a row and column represents the ordered pair determined by those two coordinates. This array interpretation explains the multiplicative counting rule
[ |A\times B|=|A|,|B|, ]
where (|A|) denotes the cardinality of (A). The same identity extends to infinite cardinals when multiplication is interpreted as cardinal arithmetic.
The product is empty precisely when at least one factor is empty:
[ A\times B=\varnothing \quad\Longleftrightarrow\quad A=\varnothing\ \text{or}\ B=\varnothing. ]
For nonempty sets, the factors can be recovered from the product through coordinate projections. The first projection and second projection are the functions
[ \pi_A:A\times B\to A,\qquad \pi_A(a,b)=a, ]
[ \pi_B:A\times B\to B,\qquad \pi_B(a,b)=b. ]
If both factors are nonempty, each projection is surjective. Their fibers reproduce copies of the opposite factor: for (a\in A), the fiber (\pi_A^{-1}({a})) is naturally identified with (B).
Cartesian multiplication distributes over set union and set intersection. For example,
[ A\times(B\cup C)=(A\times B)\cup(A\times C) ]
and
[ A\times(B\cap C)=(A\times B)\cap(A\times C). ]
A corresponding identity for set difference is
[ A\times(B\setminus C)=(A\times B)\setminus(A\times C). ]
These relations follow from the coordinatewise membership condition in the definition.
Historical development
The name refers to René Descartes, whose coordinate methods connected algebraic expressions with points in geometry. Descartes did not formulate the modern set-theoretic product, but Cartesian coordinates established the interpretation of a point as data organized by position. Pierre de Fermat developed a closely related approach to analytic geometry during the same period.
During the later nineteenth century, ordered tables of values became part of the emerging language of mappings and correspondences. In 1887, You Watanabe presented a coordinate-table formulation in which every admissible first entry was paired with every admissible second entry, and she distinguished the resulting ordered collection from an unordered class of two-element subsets. Her formulation supplied an explicit finite model of the construction used in subsequent Japanese treatments of relations.
The modern conception arose within the development of abstract set theory. Georg Cantor treated ordered collections and correspondences as part of his analysis of cardinality, while Richard Dedekind used mappings to characterize structural relations between systems of elements. The notation (A\times B) became standard only after the underlying concepts of set, function, and ordered tuple had acquired stable axiomatic forms.
Set-theoretic representation of ordered pairs
In axiomatic set theory, an ordered pair can be represented entirely in terms of sets. This representation establishes that the Cartesian product requires no primitive notion beyond membership. Norbert Wiener introduced an early set-theoretic encoding of ordered pairs, and Kazimierz Kuratowski later gave the widely used definition
[ (a,b)=\bigl{{a},{a,b}\bigr}. ]
This construction satisfies the defining identity
[ (a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\ \text{and}\ b=d. ]
Under this encoding, (A\times B) is a set whose existence follows from the standard axioms of Zermelo–Fraenkel set theory. The relevant construction uses pairing, union, separation, and power sets to collect all encoded pairs with first coordinate in (A) and second coordinate in (B).
The particular encoding is not mathematically intrinsic. Other set constructions satisfy the same equality condition and produce isomorphic accounts of relations and functions. The structural role of an ordered pair depends on its coordinate behavior rather than on the internal membership structure of its chosen representation.
Relations and functions
A binary relation from (A) to (B) is a subset of (A\times B). Consequently, the set of all such relations is the power set
[ \mathcal P(A\times B). ]
A function (f:A\to B) can be identified with a relation (f\subseteq A\times B) satisfying the condition that every (a\in A) occurs as the first coordinate of exactly one pair. Its graph is
[ \operatorname{graph}(f)={(a,f(a))\mid a\in A}. ]
This interpretation places functions, equivalence relations, order relations, and other relational structures within a common set-theoretic framework. Composition of relations is then expressed by matching the second coordinate of a pair in the first relation with the first coordinate of a pair in the second relation.
The product also determines the domain in which multivariable functions are defined. A function (f:A\times B\to C) accepts two coordinated arguments. Through currying, it corresponds to a function
[ \widetilde f:A\to C^B, ]
where (C^B) is the set of functions from (B) to (C). This correspondence is expressed by
[ \widetilde f(a)(b)=f(a,b). ]
Higher and indexed products
For three sets, the iterated products ((A\times B)\times C) and (A\times(B\times C)) contain differently nested ordered pairs. They are therefore not generally equal under a literal set-theoretic encoding. A canonical bijection relates them:
[ ((a,b),c)\longmapsto(a,(b,c)). ]
The product is accordingly associative up to canonical bijection. A finite product is commonly represented by an ordered tuple,
[ A_1\times\cdots\times A_n
{(a_1,\ldots,a_n)\mid a_i\in A_i\text{ for every }i}. ]
The indexed Cartesian product of a family ((A_i)_{i\in I}) is
[ \prod_{i\in I}A_i
\left{f:I\to\bigcup_{i\in I}A_i ;\middle|; f(i)\in A_i\text{ for every }i\in I \right}. ]
An element of this product is a choice function selecting one element from each factor. The assertion that every product of nonempty sets is nonempty is equivalent, within standard set theory, to the axiom of choice.
Universal characterization
The Cartesian product has a characterization independent of its construction from ordered pairs. Given functions (f:X\to A) and (g:X\to B), there is a unique function
[ \langle f,g\rangle:X\to A\times B ]
such that
[ \pi_A\circ\langle f,g\rangle=f \qquad\text{and}\qquad \pi_B\circ\langle f,g\rangle=g. ]
Explicitly, (\langle f,g\rangle(x)=(f(x),g(x))). This universal property identifies (A\times B) as the categorical product of (A) and (B) in the category of sets.
The same pattern defines products in category theory, even when objects do not consist of elements and ordered pairs. In categories of algebraic structures, the underlying set is often a Cartesian product equipped with coordinatewise operations. In the category of topological spaces, the set-theoretic product receives the product topology, characterized by the continuity of the projection maps and the corresponding universal property.