Cardinality of Cartesian Products
What You'll Learn
You'll learn how to count the elements in a Cartesian product using a simple multiplication rule.
The Core Idea
When you form a Cartesian product A × B, you create ordered pairs by matching every element of A with every element of B. The total number of these pairs is simply the product of the cardinalities of the two sets:
|A × B| = |A| · |B|
Think of it like choosing an outfit: if you have 3 shirts and 4 pairs of pants, you can make 3 × 4 = 12 different outfits. Each outfit is an ordered pair (shirt, pants).
Why This Works
For each of the |A| elements in A, you pair it with all |B| elements in B. Since this happens |A| times, you get |A| · |B| total pairs.
Example
If A = {1, 2, 3} and B = {x, y}, then:
- |A| = 3
- |B| = 2
- |A × B| = 3 · 2 = 6
Indeed, A × B = {(1,x), (1,y), (2,x), (2,y), (3,x), (3,y)} has exactly 6 elements.
Extension to Multiple Sets
This principle extends naturally to products of more than two sets:
|A₁ × A₂ × ... × Aₙ| = |A₁| · |A₂| · ... · |Aₙ|
For example, if you're choosing from 3 shirts, 4 pants, and 2 pairs of shoes, you have 3 × 4 × 2 = 24 complete outfits.
Special Case: Empty Set
If any set in the product is empty, the entire product is empty: |∅ × A| = 0 · |A| = 0.
Key Takeaway: The cardinality of a Cartesian product equals the product of the cardinalities of its component sets: |A × B| = |A| · |B|, generalizing to any number of sets.