Definition
Concept
Cartesian product: operation producing ordered pairs from two sets. Given sets A and B, their cartesian product A × B = {(a,b) | a ∈ A, b ∈ B}.
Ordered Pairs
Ordered pair (a,b): sequence with first element a, second element b. Order matters: (a,b) ≠ (b,a) generally.
Set Formation
Result is a set of ordered pairs, each from first set combined with each from second set.
Historical Context
Named after René Descartes (Cartesian coordinate system). Originates from analytic geometry relating algebra and geometry.
Notation
Symbol
Symbol: "×" denotes cartesian product. For sets A and B, A × B.
Alternative Notations
Sometimes written as A ⨯ B or A × B in various texts. No ambiguity with multiplication due to context.
Tuple Notation
Elements represented as ordered n-tuples: (a,b) for 2 sets, (a,b,c) for 3 sets, etc.
Extension to Multiple Sets
Notation extends to n sets: A₁ × A₂ × ... × Aₙ.
Properties
Non-commutativity
A × B ≠ B × A generally. (a,b) ≠ (b,a) unless A = B and elements coincide.
Associativity
(A × B) × C ≅ A × (B × C). Sets are isomorphic via bijection between ((a,b),c) and (a,(b,c)).
Distributivity over Union
A × (B ∪ C) = (A × B) ∪ (A × C). Similarly for (A ∪ B) × C.
Empty Set Behavior
If either set is empty (∅), then A × ∅ = ∅ × A = ∅.
Examples
Finite Sets
A = {1,2}, B = {x,y}, then A × B = {(1,x),(1,y),(2,x),(2,y)}.
Infinite Sets
For A = ℕ (natural numbers), B = {0,1}, A × B is infinite set of pairs with second element 0 or 1.
Singleton Sets
{a} × {b} = {(a,b)}. Product reduces to single ordered pair.
Cross Product with Empty Set
{1,2} × ∅ = ∅.
Cardinality
Product Cardinality Formula
|A × B| = |A| · |B| where |.| denotes cardinality.
Finite Cardinalities
If |A| = m, |B| = n, then |A × B| = m × n.
Infinite Cardinalities
For infinite sets, cardinal multiplication applies: e.g. |ℕ × ℕ| = |ℕ| (countably infinite).
Cardinality Table
| Set A | Set B | |A × B| |
|---|---|---|
| {1,2,3} | {a,b} | 6 |
| ℕ | {0,1} | ℵ₀ (countable infinity) |
Generalization to n-ary Products
Definition
For sets A₁, A₂, ..., Aₙ, cartesian product is A₁ × A₂ × ... × Aₙ = {(a₁,a₂,...,aₙ) | aᵢ ∈ Aᵢ}.
Tuples
Elements are ordered n-tuples, extending ordered pairs.
Cardinality
|A₁ × A₂ × ... × Aₙ| = ∏ᵢ |Aᵢ| (product of cardinalities).
Associativity
Groupings do not affect isomorphism: (A₁ × A₂) × A₃ ≅ A₁ × (A₂ × A₃).
Relations and Functions
Binary Relations
Binary relation from A to B is subset of A × B.
Functions as Special Relations
Function f: A → B is subset of A × B with unique second element for each first element.
Domain and Range
Domain: first elements of pairs; Range: second elements.
Graph of a Function
Graph(f) ⊆ A × B representing function as relation.
Applications
Coordinate Systems
Cartesian product underlies Cartesian coordinates in geometry.
Database Theory
Joins in relational databases modeled as cartesian product of tables.
Computer Science
State spaces, product automata constructed via cartesian product.
Logic and Proofs
Relations, predicates defined on cartesian products.
Algebraic Structures
Product Groups
Group G × H with operation defined componentwise from groups G and H.
Product Rings and Modules
Cartesian product forms ring or module with componentwise operations.
Topological Products
Product topology defined on cartesian product of topological spaces.
Category Theory
Product as universal construction in categories.
Computational Aspects
Algorithmic Generation
Enumerate all ordered pairs by nested loops over elements of sets.
Complexity
Time complexity proportional to product of input set sizes.
Data Structures
Arrays, lists used to store elements of cartesian products.
Optimization
Lazy evaluation and generators to handle large/infinite products.
Examples with Tables
Finite Cartesian Product Table
| A | B | (a,b) |
|---|---|---|
| 1 | x | (1,x) |
| 1 | y | (1,y) |
| 2 | x | (2,x) |
| 2 | y | (2,y) |
Algorithmic Representation
function cartesianProduct(A, B): result = [] for a in A: for b in B: result.append((a,b)) return resultFormal Properties and Theorems
Associativity Isomorphism
Existence of bijection φ: (A × B) × C → A × (B × C) defined by φ(((a,b),c)) = (a,(b,c)).
Distributive Laws
A × (B ∪ C) = (A × B) ∪ (A × C)(A ∪ B) × C = (A × C) ∪ (B × C)Empty Set Product
∀A, A × ∅ = ∅ and ∅ × A = ∅.
Injection and Projection Maps
Projection π₁: A × B → A; π₂: A × B → B. Both surjective functions.
Universal Property
For any set X with functions f: X → A and g: X → B, ∃ unique h: X → A × B with π₁ ∘ h = f and π₂ ∘ h = g.
References
- Halmos, P. R., Naive Set Theory, Springer, 1974, pp. 22-30.
- Enderton, H. B., Elements of Set Theory, Academic Press, 1977, pp. 40-50.
- Rosen, K. H., Discrete Mathematics and Its Applications, McGraw-Hill, 7th Edition, 2012, pp. 30-45.
- Suppes, P., Axiomatic Set Theory, Dover Publications, 1972, pp. 15-25.
- Jech, T., Set Theory, Springer Monographs in Mathematics, 2003, pp. 10-20.