s
Section 5.1 Relations
331
S
S
S
S
S
S
S
S
One-to-one
One-to-many
Many-to-one
Many-to-many
Figure 5.1
These ideas extend to relations from a set S to a set T. The relation of Example 5
is one-to-many because the first component 2 appears more than once; 2 from set
S is associated with both 4 and 7 from set T.
Suppose B is the set of all binary relations on a given set S. If r and s belong
to B, then they are subsets of S × S. As such, we can perform set operations
of union, intersection, and complementation that result in new subsets of S × S,
that is, new binary relations, which we will denote by r c s, r d s, and r′,
respectively. Thus
x (r c s) y 4 x r y or x s y
x (r d s) y 4 x r y and x s y
x r′ y 4 not x r y
PRaCtiCe 3 Let r and s be two binary relations on N defined by x r y 4 x = y and x s y 4 x < y.
Give verbal descriptions for parts (a), (b), and (c); give a set description for part (d).
a. What is the relation r c s?
b. What is the relation r′?
c. What is the relation s′?
d. What is the relation r d s?
■
■
PRaCtiCe 2 Identify each of these relations on S, where S = 52, 5, 7, 96, as one-to-one, one-to-many,
many-to-one, or many-to-many.
a. 5(5, 2), (7, 5), (9, 2)6
b. 5(2, 5), (5, 7), (7, 2)6
c. 5(7, 9), (2, 5), (9, 9), (2, 7)6