Mathematics for Computer Science

Chapter 9 Directed graphs & Partial Orders368

symmetric, whether it is transitive, and whether it is an equivalence relation.

(a)f.a;b/jaandbare the same ageg

(b)f.a;b/jaandbhave the same parentsg

(c)f.a;b/jaandbspeak a common languageg

Problem 9.45.
For each of the binary relations below, state whether it is a strict partial order, a
weak partial order, an equivalence relation, or none of these. If it is a partial order,
state whether it is a linear order. If it is none, indicate which of the axioms for
partial-order and equivalence relations it violates.

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

(b)The relation between any two nonnegative integersaandbsuch thatab
.mod8/.

(c)The relation between propositional formulasGandHsuch thatŒGIMPLIES
Hçis valid.

(d)The relation between propositional formulasGandHsuch thatŒGIFFHçis
valid.

(e)The relation ‘beats’ on Rock, Paper, and Scissors (for those who don’t know
the game Rock, Paper, Scissors, Rock beats Scissors, Scissors beats Paper, and
Paper beats Rock).

(f)The empty relation on the set of real numbers.

(g)The identity relation on the set of integers.

(h)The divisibility relation on the integers,Z.

Class Problems

Problem 9.46.
Prove Theorem 9.10.4: The equivalence classes of an equivalence relation form a
partition of the domain.
Namely, letRbe an equivalence relation on a set,A, and define the equivalence
class of an elementa 2 Ato be

ŒaçRWWDfb 2 Aja R bg: