Discrete Mathematics Recall that a relation is an equivalence relation if it is

Question

Discrete Mathematics

Recall that a relation is an equivalence relation if it is reflexive, symmetric, and transitive. For the following relations, determine whether or not they are equivalence relations. If they are equivalence relations, prove that they satisfy all three properties. If they are not, find the property that they do not satisfy and provide a counter example.

(a) Let R1 be the relation over Q such that a R1 b if and only if a b Z.

(b) Let R2 be the relation over N × N such that (a, b) R2 (c, d) if and only if ad = bc. (Here, we say N is the set of positive integers, not including 0).

(c) Let R3 be the relation over Z such that a R3 b if and only if |a b| 5.

For each of the above relations you have shown to be equivalence relations, identify the corresponding equivalence classes. Explain your reasoning.

Explanation / Answer

a> aR1a holds as a-a=0 and 0 is an integer. R is reflexive.

Let aR1 b holds.

So a-b = k for some integer k

=> b-a= -(a-b)=-k   

=> b-a is an integer as -k is also an integer when k is so

=> bR1a holds

=> R is symmetric

Let aR1b & bR1 c hold.

Then

a-b = p and b-c = q for some integer p & q

Thus

a-c = (a-b)+(b-c) = p+q = r(say)   

=> a- c is an integer as sum of two integers is also an integer

=> aR1 c holds

=> R1 is transitive

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.