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.
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.