Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders362

(a)Prove that the function L./WA!Lis a bijection.

(b)Complete the proof by showing that

ab iff L.a/L.b/ (9.14)

for alla;b 2 A.

Homework Problems

Problem 9.30.
Every partial order is isomorphic to a collection of sets under the subset relation
(see Section 9.7). In particular, ifRis astrictpartial order on a set,A, anda 2 A,
define
L.a/WWDfag[fx 2 Ajx R ag: (9.15)

Then
a R b iff L.a/L.b/ (9.16)

holds for alla;b 2 A.

(a)Carefully prove statement (9.16), starting from the definitions of strict partial
order and the strict subset relation,.

(b)Prove that if L.a/DL.b/thenaDb.

(c)Give an example showing that the conclusion of part (b) would not hold if the
definition of L.a/in equation (9.15) had omitted the expression “fag[.”

Problems for Section 9.8

Practice Problems

Problem 9.31.
For each of the binary relations below, state whether it is a strict partial order, a
weak partial order, or neither. If it is not a partial order, indicate which of the
axioms for partial order it violates.

(a)The superset relation,on the power set powf1;2;3;4;5g.

(b)The relation between any two nonnegative integers,a,bthatab .mod8/.

(c)The relation between propositional formulas,G,H, thatG IMPLIES H is
valid.