Cartesian Product of Sets
The Cartesian product is a fundamental set-theoretic operation that constructs a new set from two existing sets by pairing every element of the first set with every element of the second set. If A and B are two non-empty sets, their Cartesian product, written A × B (read 'A cross B'), is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. The word 'ordered' is critical: the pair (a, b) is distinct from (b, a) unless a = b, because position matters. Cartesian products appear everywhere in mathematics and its applications. The familiar coordinate plane — where every point is identified by an ordered pair (x, y) — is precisely the Cartesian product ℝ × ℝ, often written ℝ². When you list all possible outcomes of rolling two dice, you are enumerating the Cartesian product {1,2,3,4,5,6} × {1,2,3,4,5,6}, which contains 36 ordered pairs. In databases, a Cartesian product of two tables produces every possible row combination, forming the foundation of relational algebra. Understanding the Cartesian product is the essential first step toward understanding relations and functions. A relation from set A to set B is defined as any subset of A × B, and a function is a special kind of relation. Without the Cartesian product providing the 'universe' of all possible pairings, neither concept could be defined precisely.
- What Is an Ordered Pair?
- Formal Definition of A × B
- Cardinality (Size) of the Cartesian Product
- Is the Cartesian Product Commutative?
- Cartesian Product of a Set with Itself
- Extension to Three or More Sets
- Connection to Relations and Functions
What Is an Ordered Pair?
An ordered pair (a, b) is a pairing of two objects where order matters. The first component a is called the first coordinate (or first element) and b is the second coordinate. Two ordered pairs (a, b) and (c, d) are equal if and only if a = c AND b = d simultaneously. This distinguishes ordered pairs from ordinary sets: the set {1, 2} equals {2, 1}, but the ordered pair (1, 2) ≠ (2, 1).
Formal Definition of A × B
Given sets A and B, the Cartesian product is A × B = {(a, b) : a ∈ A and b ∈ B}. To form it, take each element of A in turn and pair it with every element of B. For example, if A = {1, 2} and B = {x, y, z}, then A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}. Notice every element of A appears, and it is paired with every element of B exactly once.
Cardinality (Size) of the Cartesian Product
If set A has m elements and set B has n elements, then A × B has exactly m × n elements, i.e., |A × B| = |A| · |B|. This multiplicative rule is why the operation borrows its name from multiplication. In the example above, |A| = 2 and |B| = 3, so |A × B| = 6, which matches the six pairs listed.
Is the Cartesian Product Commutative?
In general, A × B ≠ B × A. Using A = {1,2} and B = {x,y,z}: B × A = {(x,1),(x,2),(y,1),(y,2),(z,1),(z,2)}, which is a completely different set of ordered pairs (the components are reversed). The two sets have the same number of elements but are not equal unless A = B. This non-commutativity is important: when defining a relation 'from A to B', the order of the sets determines which element plays which role.
Cartesian Product of a Set with Itself
The product A × A, also written A², is the set of all ordered pairs of elements from A. For A = {1, 2, 3}, A² = {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}, giving 9 pairs. The real plane ℝ² = ℝ × ℝ is the infinite version of this idea, providing coordinates for every point in two-dimensional space.
Extension to Three or More Sets
The Cartesian product extends naturally: A × B × C = {(a,b,c) : a ∈ A, b ∈ B, c ∈ C} is the set of all ordered triples. In general, A₁ × A₂ × … × Aₙ consists of all ordered n-tuples. Three-dimensional space ℝ³ = ℝ × ℝ × ℝ illustrates this — every point is an ordered triple (x, y, z). The cardinality rule extends: |A₁ × A₂ × … × Aₙ| = |A₁| · |A₂| · … · |Aₙ|.
Connection to Relations and Functions
A relation R from A to B is any subset R ⊆ A × B. For instance, the 'less than' relation on {1,2,3} is the subset {(1,2),(1,3),(2,3)} of {1,2,3}². A function f: A → B is a relation where every element of A appears as a first coordinate exactly once. Thus, Cartesian products provide the universe from which all relations and functions are carved out.
The Key Equation
- A — First set (—): Any non-empty set whose elements become the first coordinates of the ordered pairs.
- B — Second set (—): Any non-empty set whose elements become the second coordinates of the ordered pairs.
- (a, b) — Ordered pair (—): A pair of elements where a is from A and b is from B; order matters so (a,b) ≠ (b,a) in general.
- |A \times B| — Cardinality of Cartesian product (—): Equals |A| · |B|; the total number of ordered pairs formed when every element of A is paired with every element of B.
Worked Example
Problem. Let A = {2, 4, 6} and B = {1, 3}. (a) List all elements of A × B and B × A. (b) Find |A × B|. (c) Let R = {(a, b) ∈ A × B : a > b}. List R and state whether R = A × B.
Answer. A × B = {(2,1),(2,3),(4,1),(4,3),(6,1),(6,3)}; B × A = {(1,2),(1,4),(1,6),(3,2),(3,4),(3,6)}; |A × B| = 6; R = {(2,1),(4,1),(4,3),(6,1),(6,3)} ⊊ A × B.
Origins · 1 minRené Descartes and how this was discovered
Descartes introduced the coordinate system (the Cartesian plane) in his 1637 work 'La Géométrie', an appendix to his philosophical treatise 'Discourse on the Method'. By assigning a unique ordered pair of numbers to every point in the plane, he unified geometry and algebra — a revolution that made it possible to describe curves as equations. The Cartesian product is named in his honour precisely because ℝ × ℝ is the mathematical formalisation of his coordinate plane. Descartes reportedly developed his ideas about coordinate geometry while lying in bed watching a fly crawl across the ceiling tiles — he realised he could describe the fly's position at any moment using just two numbers measuring distance from two walls.
Related Concepts
- Definition and Representation of Relations — A relation from set A to set B is defined as a subset of the Cartesian product A × B; the Cartesian product is the universe from which all relations are drawn.
- Definition of Functions — A function f: A → B is a special relation — a subset of A × B where every element of A appears as a first coordinate exactly once; understanding A × B is prerequisite to defining functions.
- Types of Functions — Classifying functions (injective, surjective, bijective) relies on analysing which ordered pairs from A × B are included, making the Cartesian product the underlying framework.
- Composition of Functions — Composing f: A → B and g: B → C involves ordered pairs across multiple Cartesian products; the domains and codomains must align, a condition rooted in Cartesian product structure.
- Invertible Functions — The inverse of f: A → B swaps coordinates in the ordered pairs of f, effectively working within B × A instead of A × B, highlighting the non-commutativity of Cartesian products.
- Algebra of Functions — Operations on functions (sum, product, quotient) are defined pointwise on ordered pairs in A × B, so the Cartesian product sets the domain on which these operations act.
- Functional Equations — Solving functional equations often requires specifying the domain and codomain precisely — the sets A and B in the Cartesian product A × B from which the function is drawn.
- Binary Operations — A binary operation on a set S is a function from S × S to S; the Cartesian product S × S provides the domain of ordered pairs (a, b) on which the operation acts.
- Floor and Ceiling Functions — The floor and ceiling functions are specific mappings from ℝ to ℤ; describing them precisely requires the Cartesian product ℝ × ℤ as the set containing their ordered pairs.
- Piecewise Functions — A piecewise function partitions the domain into subsets and assigns different rules on each piece; the overall function is still a subset of A × B, grounding it in Cartesian product theory.