Page 656 - Discrete Mathematics and Its Applications

Supplementary Exercises 635

c) Describe two algorithms for finding the transitive clo- 16. a) Explain how to construct the Hasse diagram of a partial
sure of a relation. order on a finite set.
d) Find the transitive closure of the relation b) Draw the Hasse diagram of the divisibility relation on
{(1,1), (1,3), (2,1), (2,3), (2,4), (3,2), (3,4), (4,1)}. the set {2, 3, 5, 9, 12, 15, 18}.
10. a) Define an equivalence relation. 17. a) Define a maximal element of a poset and the greatest
b) Which relations on the set {a, b, c, d} are equivalence element of a poset.
relations and contain (a, b) and (b, d)? b) Give an example of a poset that has three maximal
11. a) Show that congruence modulo m is an equivalence re- elements.
lation whenever m is a positive integer. c) Give an example of a poset with a greatest element.
b) Show that the relation {(a, b) | a ≡±b(mod 7)} is an 18. a) Define a lattice.
equivalence relation on the set of integers. b) Give an example of a poset with five elements that is
12. a) What are the equivalence classes of an equivalence re- a lattice and an example of a poset with five elements
lation? that is not a lattice.
b) What are the equivalence classes of the “congruent 19. a) Show that every finite subset of a lattice has a greatest
modulo 5” relation? lower bound and a least upper bound.
c) What are the equivalence classes of the equivalence b) Show that every lattice with a finite number of elements
relation in Question 11(b)? has a least element and a greatest element.
13. Explain the relationship between equivalence relations on
20. a) Define a well-ordered set.
a set and partitions of this set.
b) Describe an algorithm for producing a totally ordered
14. a) Define a partial ordering. set compatible with a given partially ordered set.
b) Show that the divisibility relation on the set of positive c) Explain how the algorithm from (b) can be used to or-
integers is a partial order. der the tasks in a project if tasks are done one at a time
15. Explain how partial orderings on the sets A 1 and A 2 can and each task can be done only after one or more of
be used to define a partial ordering on the set A 1 × A 2 . the other tasks have been completed.

Supplementary Exercises

1. Let S be the set of all strings of English letters. Determine 9. Let R 1 and R 2 be symmetric relations. Is R 1 ∩ R 2 also
whether these relations are reflexive, irreflexive, symmet- symmetric? Is R 1 ∪ R 2 also symmetric?
ric, antisymmetric, and/or transitive. 10. A relation R is called circular if aRb and bRc imply that
a) R 1 ={(a, b) | a and b have no letters in common} cRa. Show that R is reflexive and circular if and only if
b) R 2 ={(a, b) | a and b are not the same length} it is an equivalence relation.
c) R 3 ={(a, b) | a is longer than b} 11. Show that a primary key in an n-ary relation is a primary
2. Construct a relation on the set {a, b, c, d} that is key in any projection of this relation that contains this key
a) reflexive, symmetric, but not transitive. as one of its fields.
b) irreflexive, symmetric, and transitive. 12. Is the primary key in an n-ary relation also a primary
c) irreflexive, antisymmetric, and not transitive. key in a larger relation obtained by taking the join of this
d) reflexive, neither symmetric nor antisymmetric, and relation with a second relation?
transitive. 13. Show that the reflexive closure of the symmetric closure
e) neither reflexive, irreflexive, symmetric, antisymmet- of a relation is the same as the symmetric closure of its
ric, nor transitive. reflexive closure.
3. Show that the relation R on Z × Z defined by 14. Let R be the relation on the set of all mathematicians that
(a,b)R (c,d) if and only if a + d = b + c is an equiva- contains the ordered pair (a, b) if and only if a and b have
lence relation. written a published mathematical paper together.
2
4. Show that a subset of an antisymmetric relation is also a) Describe the relation R .
∗
antisymmetric. b) Describe the relation R .
2
5. Let R be a reflexive relation on a set A. Show that R ⊆ R . c) The Erd˝os number of a mathematician is 1 if this
mathematician wrote a paper with the prolific Hun-
6. Suppose that R 1 and R 2 are reflexive relations on a set A. garian mathematician Paul Erd˝os, it is 2 if this math-
Show that R 1 ⊕ R 2 is irreflexive.
ematician did not write a joint paper with Erd˝os but
7. Suppose that R 1 and R 2 are reflexive relations on a set A. wrote a joint paper with someone who wrote a joint
Is R 1 ∩ R 2 also reflexive? Is R 1 ∪ R 2 also reflexive? paper with Erd˝os, and so on (except that the Erd˝os
8. Suppose that R is a symmetric relation on a set A.Is R number of Erd˝os himself is 0). Give a definition of the
also symmetric? Erd˝os number in terms of paths in R.