Course contentsShow
← Computer Science
Lesson 66 of 2,8722. Discrete Mathematics for CSFree lesson

Cartesian Products

Define Cartesian product of sets; compute products and understand ordered pairs and tuples.

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