Course contentsShow
← Mathematics
Lesson 2536 of 3,12151. Discrete Math — Sets, Relations, FunctionsFree lesson

Cardinality of Cartesian Products

Learn that |A × B| = |A| · |B| and extend this principle to products of multiple sets.

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.