Cartesian Products
What you'll learn: How to combine two sets into a new set of all possible ordered pairs.
What Is a Cartesian Product?
The Cartesian product of two sets creates a new set containing every possible ordered pair where the first element comes from the first set and the second element comes from the second set.
If you have set A = {1, 2} and set B = {x, y}, the Cartesian product A × B (read "A cross B") gives you:
A × B = {(1, x), (1, y), (2, x), (2, y)}
Notice each element is an ordered pair written as (a, b), where order matters: (1, x) ≠ (x, 1).
The Analogy
Think of choosing an outfit: if you have 2 shirts {red, blue} and 3 pants {jeans, khakis, shorts}, the Cartesian product gives you all 6 possible outfits:
{(red, jeans), (red, khakis), (red, shorts), (blue, jeans), (blue, khakis), (blue, shorts)}
Computing Cartesian Products
For sets A and B:
- A × B = {(a, b) | a ∈ A and b ∈ B}
- If |A| = m and |B| = n, then |A × B| = m × n
Example: A = {1, 2, 3}, B = {a, b}
A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
Size: 3 × 2 = 6 pairs
Beyond Pairs: Tuples
You can extend this to three or more sets, creating tuples:
A × B × C produces ordered triples like (a, b, c).
Key Takeaway: The Cartesian product A × B creates all possible ordered pairs (a, b) where a comes from A and b comes from B, and its size equals |A| × |B|.