Page 604 - Discrete Mathematics and Its Applications

9.2 n-ary Relations and Their Applications 583

41. Let R 1 and R 2 be the “congruent modulo 3” and the 49. Find the error in the “proof” of the following “theorem.”
“congruent modulo 4” relations, respectively, on the set
of integers. That is, R 1 ={(a, b) | a ≡ b(mod 3)} and “Theorem”: Let R be a relation on a set A that is sym-
R 2 ={(a, b) | a ≡ b(mod 4)}. Find metric and transitive. Then R is reflexive.
a) R 1 ∪ R 2 . b) R 1 ∩ R 2 . “Proof ”: Let a ∈ A. Take an element b ∈ A such that
c) R 1 − R 2 . d) R 2 − R 1 . (a, b) ∈ R. Because R is symmetric, we also have
e) R 1 ⊕ R 2 . (b, a) ∈ R. Now using the transitive property, we can con-
42. List the 16 different relations on the set {0, 1}. clude that (a, a) ∈ R because (a, b) ∈ R and (b, a) ∈ R.
43. How many of the 16 different relations on {0, 1} contain 50. Suppose that R and S are reflexive relations on a set A.
the pair (0, 1)? Prove or disprove each of these statements.
44. Which of the 16 relations on {0, 1}, which you listed in a) R ∪ S is reflexive.
Exercise 42, are b) R ∩ S is reflexive.
c) R ⊕ S is irreflexive.
a) reflexive? b) irreflexive?
c) symmetric? d) antisymmetric? d) R − S is irreflexive.
e) asymmetric? f) transitive? e) S ◦R is reflexive.
51. Show that the relation R on a set A is symmetric if and
45. a) How many relations are there on the set {a, b, c, d}?
only if R = R −1 , where R −1 is the inverse relation.
b) How many relations are there on the set {a, b, c, d}
that contain the pair (a, a)? 52. Show that the relation R on a set A is antisymmetric if
−1
46. Let S be a set with n elements and let a and b be dis- and only if R ∩ R is a subset of the diagonal relation
tinct elements of S. How many relations R are there on S ={(a, a) | a ∈ A}.
such that 53. Show that the relation R on a set A is reflexive if and only
−1
a) (a, b) ∈ R? b) (a, b) ∈ R? if the inverse relation R is reflexive.
c) no ordered pair in R has a as its first element? 54. Show that the relation R on a set A is reflexive if and only
d) at least one ordered pair in R has a as its first element? if the complementary relation R is irreflexive.
e) no ordered pair in R has a as its first element or b as 55. Let R be a relation that is reflexive and transitive. Prove
its second element? that R = R for all positive integers n.
n
f) at least one ordered pair in R either has a as its first 56. Let R be the relation on the set {1, 2, 3, 4, 5} containing
element or has b as its second element? the ordered pairs (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (3, 1),
∗ 47. How many relations are there on a set with n elements (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2), and (5, 4).
that are Find
5
2
4
3
a) symmetric? b) antisymmetric? a) R . b) R . c) R . d) R .
c) asymmetric? d) irreflexive? 57. Let R be a reflexive relation on a set A. Show that R is
n
e) reflexive and symmetric? reflexive for all positive integers n.
f) neither reflexive nor irreflexive? n
∗ 58. Let R be a symmetric relation. Show that R is symmetric
∗ 48. How many transitive relations are there on a set with n for all positive integers n.
elements if 2
59. Suppose that the relation R is irreflexive. Is R necessar-
a) n = 1? b) n = 2? c) n = 3?
ily irreflexive? Give a reason for your answer.
9.2 n-ary Relations and Their Applications
Introduction

Relationships among elements of more than two sets often arise. For instance, there is a relation-
ship involving the name of a student, the student’s major, and the student’s grade point average.
Similarly, there is a relationship involving the airline, flight number, starting point, destination,
departure time, and arrival time of a flight. An example of such a relationship in mathematics
involves three integers, where the first integer is larger than the second integer, which is larger
than the third. Another example is the betweenness relationship involving points on a line, such
that three points are related when the second point is between the first and the third.
Wewillstudyrelationshipsamongelementsfrommorethantwosetsinthissection.Thesere-
lationships are called n-ary relations. These relations are used to represent computer databases.
These representations help us answer queries about the information stored in databases, such
as: Which flights land at O’Hare Airport between 3 a.m. and 4 a.m.? Which students at your