Mathematics for Computer Science

9.11. Summary of Relational Properties 369

That is,ŒaçRDR.a/.
(a)Prove that every block is nonempty and every element ofAis in some block.

(b)Prove that ifŒaçR\ŒbçR¤ ;, thena R b. Conclude that the setsŒaçRfor
a 2 Aare a partition ofA.

(c)Prove thata R biffŒaçRDŒbçR.

Problem 9.47.
For any total functionf WA!Bdefine a relationfby the rule:

afa^0 iff f.a/Df.a^0 /: (9.17)

(a)Observe (and sketch a proof) thatfis an equivalence relation onA.

(b)Prove that every equivalence relation,R, on a set,A, is equal tof for the
functionf WA!pow.A/defined as

f.a/WWDfa^02 Aja R a^0 g:

That is,f.a/DR.a/.

Problem 9.48.
LetRbe a binary relation on a setD. Each of the following formulas expresses the
fact thatRhas a familiar relational property such as reflexivity, asymmetry, tran-
sitivity. Predicate formulas have roman numerals i.,ii.,... , and relational formulas
(equalities and containments) are labelled with letters (a),(b),....
Next to each of the relational formulas, write the roman numerals of all the pred-
icate formulas equivalent to it. It is not necessary to name the property expressed,
but you can get partial credit if you do. For example, part (a) gets the label “i.” It
expressesirreflexivity.

i. 8 d: NOT.d R d/

ii. 8 d: d R d

iii. 8 c;d: c R dIFFd R c

iv. 8 c;d: c R dIMPLIESd R c

v. 8 c;d: c R dIMPLIES NOT.d R c/