Page 603 - Discrete Mathematics and Its Applications

582 9 / Relations

A relation R is called asymmetric if (a, b) ∈ R implies that 33. Let R be the relation on the set of people consisting of
(b, a) /∈ R. Exercises 18–24 explore the notion of an asym- pairs (a, b), where a is a parent of b. Let S be the relation
metric relation. Exercise 22 focuses on the difference between on the set of people consisting of pairs (a, b), where a
asymmetry and antisymmetry. and b are siblings (brothers or sisters). What are S ◦ R
and R ◦ S?
18. Which relations in Exercise 3 are asymmetric?
Exercises 34–37 deal with these relations on the set of real
19. Which relations in Exercise 4 are asymmetric?
numbers:
20. Which relations in Exercise 5 are asymmetric? 2
R 1 ={(a, b) ∈ R | a> b}, the “greater than” relation,
21. Which relations in Exercise 6 are asymmetric? R 2 ={(a, b) ∈ R | a ≥ b}, the “greater than or equal to”
2
22. Mustanasymmetricrelationalsobeantisymmetric?Must relation,
2
an antisymmetric relation be asymmetric? Give reasons R 3 ={(a, b) ∈ R | a< b}, the “less than” relation,
for your answers. 2
R 4 ={(a, b) ∈ R | a ≤ b}, the “less than or equal to”
23. Use quantifiers to express what it means for a relation to relation,
2
be asymmetric. R 5 ={(a, b) ∈ R | a = b}, the “equal to” relation,
2
24. Give an example of an asymmetric relation on the set of R 6 ={(a, b) ∈ R | a = b}, the “unequal to” relation.
all people.
34. Find
25. How many different relations are there from a set with m a) R 1 ∪ R 3 . b) R 1 ∪ R 5 .
elements to a set with n elements?
c) R 2 ∩ R 4 . d) R 3 ∩ R 5 .
Let R be a relation from a set A to a set B. The inverse rela- e) R 1 − R 2 . f) R 2 − R 1 .
tion from B to A, denoted by R −1 , is the set of ordered pairs
{(b, a) | (a, b) ∈ R}. The complementary relation R is the g) R 1 ⊕ R 3 . h) R 2 ⊕ R 4 .
set of ordered pairs {(a, b) | (a, b) /∈ R}. 35. Find
26. Let R be the relation R ={(a, b) | a< b} on the set of a) R 2 ∪ R 4 . b) R 3 ∪ R 6 .
integers. Find c) R 3 ∩ R 6 . d) R 4 ∩ R 6 .
a) R −1 . b) R. e) R 3 − R 6 . f) R 6 − R 3 .
27. Let R be the relation R ={(a, b) | a divides b} on the set g) R 2 ⊕ R 6 . h) R 3 ⊕ R 5 .
of positive integers. Find 36. Find
a) R −1 . b) R.
a) R 1 ◦ R 1 . b) R 1 ◦ R 2 .
28. Let R be the relation on the set of all states in the United c) R 1 ◦ R 3 . d) R 1 ◦ R 4 .
States consisting of pairs (a, b) where state a borders
state b. Find e) R 1 ◦ R 5 . f) R 1 ◦ R 6 .
a) R −1 . b) R. g) R 2 ◦ R 3 . h) R 3 ◦ R 3 .
29. Suppose that the function f from A to B is a one-to- 37. Find
one correspondence. Let R be the relation that equals the a) R 2 ◦ R 1 . b) R 2 ◦ R 2 .
graph of f . That is, R ={(a, f (a)) | a ∈ A}. What is the c) R 3 ◦ R 5 . d) R 4 ◦ R 1 .
inverse relation R −1 ?
e) R 5 ◦ R 3 . f) R 3 ◦ R 6 .
30. Let R 1 ={(1, 2), (2, 3), (3, 4)} and R 2 ={(1, 1), (1, 2), g) R 4 ◦ R 6 . h) R 6 ◦ R 6 .
(2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (3, 4)} be rela- 38. Let R be the parent relation on the set of all people (see
tions from {1, 2, 3} to {1, 2, 3, 4}. Find 3
Example 21). When is an ordered pair in the relation R ?
a) R 1 ∪ R 2 . b) R 1 ∩ R 2 .
39. Let R be the relation on the set of people with doctorates
c) R 1 − R 2 . d) R 2 − R 1 .
such that (a, b) ∈ R if and only if a was the thesis advisor
31. Let A be the set of students at your school and B the set of of b. When is an ordered pair (a, b) in R ? When is an
2
books in the school library. Let R 1 and R 2 be the relations ordered pair (a, b) in R , when n is a positive integer?
n
consisting of all ordered pairs (a, b), where student a is
(Assume that every person with a doctorate has a thesis
required to read book b in a course, and where student a advisor.)
has read book b, respectively. Describe the ordered pairs
in each of these relations. 40. Let R 1 and R 2 be the “divides” and “is a multiple of”
relations on the set of all positive integers, respectively.
a) R 1 ∪ R 2 b) R 1 ∩ R 2
That is, R 1 ={(a, b) | a divides b} and R 2 ={(a, b) | a
c) R 1 ⊕ R 2 d) R 1 − R 2
is a multiple of b}. Find
e) R 2 − R 1 a) R 1 ∪ R 2 . b) R 1 ∩ R 2 .
32. Let R be the relation {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)}, c) R 1 − R 2 . d) R 2 − R 1 .
and let S be the relation {(2, 1), (3, 1), (3, 2), (4, 2)}.
Find S ◦ R. e) R 1 ⊕ R 2 .