Page 145 - Discrete Mathematics and Its Applications

124 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

EXAMPLE 19 What is the Cartesian product A × B × C, where A ={0, 1}, B ={1, 2}, and C ={0, 1, 2} ?

Solution:The Cartesian product A × B × C consists of all ordered triples (a, b, c), where a ∈ A,
b ∈ B, and c ∈ C. Hence,

A × B × C ={(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2),
(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}. ▲

Remark: Note that when A, B, and C are sets, (A × B) × C is not the same as A × B × C (see
Exercise 39).

2
We use the notation A to denote A × A, the Cartesian product of the set A with itself.
4
3
Similarly, A = A × A × A, A = A × A × A × A, and so on. More generally,
n
A ={(a 1 ,a 2 ,...,a n ) | a i ∈ A for i = 1, 2,...,n}.

3
2
EXAMPLE 20 Suppose that A ={1, 2}. It follows that A ={(1, 1), (1, 2), (2, 1), (2, 2)} and A =
{(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}. ▲
A subset R of the Cartesian product A × B is called a relation from the set A to the set
B. The elements of R are ordered pairs, where the first element belongs to A and the second
to B. For example, R ={(a, 0), (a, 1), (a, 3), (b, 1), (b, 2), (c, 0), (c, 3)} is a relation from the
set {a, b, c} to the set {0, 1, 2, 3}. A relation from a set A to itself is called a relation on A.

EXAMPLE 21 What are the ordered pairs in the less than or equal to relation, which contains (a, b) if a ≤ b,
on the set {0, 1, 2, 3}?

Solution: The ordered pair (a, b) belongs to R if and only if both a and b belong to {0, 1, 2, 3}
and a ≤ b. Consequently, the ordered pairs in R are (0,0), (0,1), (0,2), (0,3), (1,1), (1,2), (1,3),
(2,2), (2, 3), and (3, 3). ▲

We will study relations and their properties at length in Chapter 9.

Using Set Notation with Quantifiers

Sometimes we restrict the domain of a quantified statement explicitly by making use of a
particular notation. For example, ∀x∈S(P (x)) denotes the universal quantification of P(x)
over all elements in the set S. In other words, ∀x∈S(P(x)) is shorthand for ∀x(x ∈ S → P(x)).
Similarly, ∃x∈S(P(x)) denotes the existential quantification of P(x) over all elements in S.
That is, ∃x∈S(P(x)) is shorthand for ∃x(x ∈ S ∧ P(x)).

2
2
EXAMPLE 22 What do the statements ∀x∈R (x ≥ 0) and ∃x∈Z (x = 1) mean?
2
2
Solution: The statement ∀x∈R(x ≥ 0) states that for every real number x, x ≥ 0. This state-
ment can be expressed as “The square of every real number is nonnegative.” This is a true
statement.
2
2
The statement ∃x∈Z(x = 1) states that there exists an integer x such that x = 1. This
statement can be expressed as “There is an integer whose square is 1.”This is also a true statement
because x = 1 is such an integer (as is −1). ▲