Page 595 - Discrete Mathematics and Its Applications

574 9 / Relations

(Jason Goodfriend, CS518) and (Deborah Sherman, CS518) belong to R. If Jason Goodfriend
is also enrolled in CS510, then the pair (Jason Goodfriend, CS510) is also in R. However,
if Deborah Sherman is not enrolled in CS510, then the pair (Deborah Sherman, CS510) is
not in R.
Note that if a student is not currently enrolled in any courses there will be no pairs in R that
have this student as the first element. Similarly, if a course is not currently being offered there
will be no pairs in R that have this course as their second element. ▲

EXAMPLE 2 Let A be the set of cities in the U.S.A., and let B be the set of the 50 states in the U.S.A.
Define the relation R by specifying that (a, b) belongs to R if a city with name a is in
the state b. For instance, (Boulder, Colorado), (Bangor, Maine), (Ann Arbor, Michigan),
(Middletown, New Jersey), (Middletown, New York), (Cupertino, California), and
(Red Bank, New Jersey) are in R. ▲

EXAMPLE 3 Let A ={0, 1, 2} and B ={a, b}. Then {(0, a), (0, b), (1, a), (2,b)} is a relation from A to B.
This means, for instance, that 0 Ra, but that 1 R b. Relations can be represented graphically,
as shown in Figure 1, using arrows to represent ordered pairs. Another way to represent this
relation is to use a table, which is also done in Figure 1. We will discuss representations of
relations in more detail in Section 9.3. ▲

0
R a b
a
0
1 1
2
b

2

FIGURE 1 Displaying the Ordered Pairs in the Relation R from Example 3.

Functions as Relations

Recall that a function f from a set A to a set B (as defined in Section 2.3) assigns exactly
one element of B to each element of A. The graph of f is the set of ordered pairs (a, b) such
that b = f(a). Because the graph of f is a subset of A × B, it is a relation from A to B.
Moreover, the graph of a function has the property that every element of A is the first element
of exactly one ordered pair of the graph.
Conversely, if R is a relation from A to B such that every element in A is the first element
of exactly one ordered pair of R, then a function can be defined with R as its graph. This can be
done by assigning to an element a of A the unique element b ∈ B such that (a, b) ∈ R. (Note
that the relation R in Example 2 is not the graph of a function because Middletown occurs more
than once as the first element of an ordered pair in R.)
A relation can be used to express a one-to-many relationship between the elements of the
sets A and B (as in Example 2), where an element of A may be related to more than one element
of B. A function represents a relation where exactly one element of B is related to each element
of A.
Relations are a generalization of graphs of functions; they can be used to express a much
wider class of relationships between sets. (Recall that the graph of the function f from A to B
is the set of ordered pairs (a, f (a)) for a ∈ A.)