Discrete Mathematics for Computer Science

190 CHAPTER 3 Relations

13. Prove Theorem 4.


14. There is an old, fallacious proof that if a relation is both symmetric and transitive, it is
    reflexive. We give this "proof" below. What is the error?
    Suppose R is a symmetric and transitive relation on a set X. Pick an x E X.
    We need to show x R x. So, take any y where x R y. By symmetry, it follows
    that y R x. By transitivity, it follows that x R x.


15. For a relation R on a set X, let R denote the reflexive and transitive closure of R.
    (a) For any relation R on a set X, define a relation -' on X as follows: x - y if and
    only if x R y and y R x. Prove that -is an equivalence relation.
    (b) Let xl -x2 and yj -Y2. Show that x1 R yi if and only if x2 R* Y2.


16. (a) For k, n1, n2, ml, m2 E N, show that if

n- n 2 (modk)

and

ml m 2 (modk)

then

nt + ml n2 + m 2 (modk)

and

nli ml -n2 • m2(mod k)

(b) Part (a) says that if we take two equivalence classes [ m ] and [ n ], then we can

unambiguously define [m ] + [ n ] and [] [ n ]. Pick any mI I [ m ] and any

n I E [ n ], and define

[mi]+[n] = [ml +ni]

and

[m] • [n]--[ml -ni]

The definition is unambiguous since it doesn't matter which ml and nl we

pick. Find the addition and multiplication tables for the equivalence classes of

• (mod 4) and =- (mod 5). (Hint: For both =- (mod 4) and -(mod 5), your an-
  swer should include

[0]+[0] -[0], [01+[1] -[1], [01 .[0]- [0]

and

but, for -- (mod 4),

whereas, that will be false for (mod 5).)