Cartesian product
In mathematics, particularly in set theory, the Cartesian product of two sets A and B, denoted A \times B, is defined as the set of all ordered pairs (a, b) where a \in A and b \in B.[1] This construction generalizes to finite collections of sets, yielding n-tuples for n sets, such as A \times B \times C = \{(a, b, c) \mid a \in A, b \in B, c \in C\}.[2] Named after the philosopher and mathematician René Descartes (1596–1650), the concept emerged from his development of analytic geometry in the 17th century, where it underpins the representation of points in the plane as pairs of real numbers, forming the Cartesian coordinate system \mathbb{R} \times \mathbb{R}.[1] In modern set theory, formalized by mathematicians like Georg Cantor in the late 19th century, the Cartesian product serves as a foundational operation for building more complex structures.[3] A key application lies in the theory of relations and functions: a binary relation between sets A and B is any subset of A \times B, while a function from A to B is a relation where each element of A pairs with exactly one element of B.[4] This framework extends to higher dimensions and infinite products, influencing areas such as topology, where product spaces like \mathbb{R}^n define Euclidean spaces, and computer science, including database queries and graph theory via Cartesian products of graphs.[5] The operation's cardinality follows |A \times B| = |A| \cdot |B| for finite sets, highlighting its role in combinatorics.[6]Definition and Notation
Set-theoretic definition
In set theory, the Cartesian product of two sets A and B, denoted A \times B, is defined as the set of all ordered pairs (a, b) such that a \in A and b \in B. This operation combines elements from each set to form a new set whose members are these pairs, providing a foundational structure for representing relations and functions between sets.[7] Formally, the definition is expressed as A \times B = \{ (a, b) \mid a \in A,\ b \in B \}. An ordered pair (a, b) differs fundamentally from an unordered pair \{a, b\}, as the former preserves the sequence of elements—(a, b) = (c, d) if and only if a = c and b = d—while the latter does not distinguish order, so \{a, b\} = \{b, a\}. In axiomatic set theory, ordered pairs can be constructed using the Kuratowski definition, (a, b) = \{\{a\}, \{a, b\}\}, which encodes order using only sets without assuming pairs as primitives.[8] The concept originated with René Descartes in the 17th century, who introduced it through his development of analytic geometry to pair algebraic equations with geometric points via coordinates.[9]Standard notation and abbreviations
The standard notation for the Cartesian product of two sets A and B in set theory is A \times B, where the symbol \times represents the cross product operation./03%3A_New_Page/3.5%3A_Cartesian_Products_of_Sets) This notation emphasizes the formation of ordered pairs from elements of the respective sets.[10] For products involving multiple sets indexed by a set I, the abbreviated form \prod_{i \in I} A_i or \times_{i \in I} A_i is commonly used, particularly when the index set I is finite or specified explicitly to avoid ambiguity in chaining binary products. This indexed notation allows for a compact representation of the set of all functions f: I \to \bigcup_{i \in I} A_i such that f(i) \in A_i for each i \in I. In mathematics, the \times symbol remains the conventional choice for denoting Cartesian products of sets. In computer science, however, subtle variations appear in the context of product types for data structures; for instance, functional programming languages like Standard ML use the asterisk * to denote product types, as inint * bool. (Note: This citation references Pierce's "Types and Programming Languages," a seminal work on type systems, where product types are discussed, aligning with notations like those in ML-family languages.)
The empty product, or Cartesian product over an empty index set, is defined as the singleton set containing the empty tuple, \{()\}, which serves as the identity element for the Cartesian product operation in set theory.[11] This convention ensures consistency in the recursive definition of products, where the nullary case yields a unique "empty" choice.[11]
Examples
Deck of cards
A standard deck of playing cards provides a concrete illustration of the Cartesian product in set theory. The set of suits consists of four elements: hearts, diamonds, clubs, and spades.[12] The set of ranks includes thirteen elements: ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, and king.[1][12] The deck itself is the Cartesian product of these sets, denoted as S \times R, where S is the set of suits and R is the set of ranks.[12][13] Each card in the deck corresponds to a unique ordered pair (s, r), with the suit s appearing first by convention to specify the card's identity, such as (\heartsuit, \text{ace}) for the ace of hearts.[14] This ordered pair structure ensures that no two cards share the same combination, distinguishing, for example, the ace of hearts from the ace of spades.[1][12] To visualize a portion of this product, consider the following partial table for the suits hearts and diamonds crossed with the ranks ace through 3:| Suit / Rank | Ace | 2 | 3 |
|---|---|---|---|
| Hearts | (\heartsuit, \text{ace}) | (\heartsuit, 2) | (\heartsuit, 3) |
| Diamonds | (\diamondsuit, \text{ace}) | (\diamondsuit, 2) | (\diamondsuit, 3) |