Mathematics for Computer Science

9.12. Summary of Relational Properties 269

Homework Problems

Problem 9.21.
LetRandSbe transitive binary relations on the same set,A. Which of the follow-
ing new relations must also be transitive? For each part, justify your answer with a
brief argument if the new relation is transitive and a counterexample if it is not.

(a)R^1

(b)R\S

(c)RıR

(d)RıS

Exam Problems

Problem 9.22.

(a)For each row in the following table, indicate whether the binary relation,R, on
the set,A, is a weak partial order or a path-total order by filling in the appropriate
entries with either Y = YES or N = NO. In addition, list the minimal and maximal
elements for each relation.

A a R b weak p. o. path-total order minimal(s) maximal(s)

RRC ajb

P.f1;2;3g/ ab

N[fig a > b

(b)What is the longestchainon the subset relation,, onP.f1;2;3g/? (If there
is more than one, provideoneof them.)

(c)What is the longestantichainon the subset relation,, onP.f1;2;3g/? (If
there is more than one, provideoneof them.)

Problems for Section 9.9

Class Problems

Problem 9.23.
LetR 1 ,R 2 be binary relations on the same set,A. A relational property is preserved