Page 144 - Discrete Mathematics and Its Applications

2.1 Sets 123

Many of the discrete structures we will study in later chapters are based on the notion of the
Cartesian product of sets (named after René Descartes). We first define the Cartesian product
of two sets.

DEFINITION 8 Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all
ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,

A × B ={(a, b) | a ∈ A ∧ b ∈ B}.

EXAMPLE 16 Let A represent the set of all students at a university, and let B represent the set of all courses
offered at the university. What is the Cartesian product A × B and how can it be used?

Solution: The Cartesian product A × B consists of all the ordered pairs of the form (a, b), where
a is a student at the university and b is a course offered at the university. One way to use the set
A × B is to represent all possible enrollments of students in courses at the university. ▲

EXAMPLE 17 What is the Cartesian product of A ={1, 2} and B ={a, b, c}?

Solution: The Cartesian product A × B is

A × B ={(1, a), (1, b), (1, c), (2, a), (2, b), (2,c)}.
▲

Note that the Cartesian products A × B and B × A are not equal, unless A =∅ or B =∅
(so that A × B =∅)or A = B (see Exercises 31 and 38). This is illustrated in Example 18.

EXAMPLE 18 Show that the Cartesian product B × A is not equal to the Cartesian product A × B, where A
and B are as in Example 17.

Solution: The Cartesian product B × A is

B × A ={(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

This is not equal to A × B, which was found in Example 17. ▲

The Cartesian product of more than two sets can also be defined.

DEFINITION 9 The Cartesian product of the sets A 1 ,A 2 ,...,A n , denoted by A 1 × A 2 × ··· × A n , is the
set of ordered n-tuples (a 1 ,a 2 ,...,a n ), where a i belongs to A i for i = 1, 2,...,n. In other
words,
A 1 × A 2 × ··· × A n ={(a 1 ,a 2 ,...,a n ) | a i ∈ A i for i = 1, 2,...,n}.