Chapter 9 Directed graphs & Partial Orders268
(e)The empty relation on the set of real numbers.(f)The identity relation on the set of integers.Class Problems
Problem 9.16. (a)Verify that the divisibility relation on the set of nonnegative
integers is a weak partial order.
(b)What about the divisibility relation on the set of integers?Problem 9.17.
Consider the nonnegative numbers partially ordered by divisibility.
(a)Show that this partial order has a unique minimal element.(b)Show that this partial order has a unique maximal element.(c)Describe an infinite chain in this partial order.(d)Describe an infinite antichain in this partial order.(e)What are the minimal elements of divisibility on the integers greater than 1?
What are the maximal elements?
Problem 9.18.
How many binary relations are there on the setf0;1g?
How many are there that are transitive?,... asymmetric?,... reflexive?,... irreflexive?,
... strict partial orders?,... weak partial orders?
Hint:There are easier ways to find these numbers than listing all the relations
and checking which properties each one has.
Problem 9.19.
Prove that if a binary relation on a set is transitive and irreflexive, then it is asym-
metric.
Problem 9.20.
Prove that ifRis a partial order, then so isR ^1