9.11. Summary of Relational Properties 363
(d)The relation ’beats’ on Rock, Paper and Scissor (for those who don’t know the
game “Rock, Paper, Scissors:” Rock beats Scissors, Scissors beats Paper and Paper
beats Rock).
(e)The empty relation on the set of real numbers.(f)The identity relation on the set of integers.Problem 9.32. (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.33.
Prove directly from the definitions (without appealing to DAG properties) that if a
binary relationRon a setAis transitive and irreflexive, then it is asymmetric.
Class Problems
Problem 9.34.
Show that the set of nonnegative integers partially ordered under the divides rela-
tion...
(a)... has a minimum element.(b)... has a maximum element.(c)... has an infinite chain.(d)... has an infinite antichain.(e)What are the minimal elements of divisibility on the integers greater than 1?
What are the maximal elements?
Problem 9.35.
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.