(a) Define what it means to be an equivalence relation on a set X. (i.e., name a

Question

(a) Define what it means to be an equivalence relation on a set X. (i.e., name and define the properties such a relation must have). (b) Consider the following two relations: The relation L on R defined by aLb if a lessthanorequalto b. The relation S on Z defined by xSy if x^2 y^2 (mod 4) Prove that one of these is an equivalence relation, while the other is not. For the one which is, give the corresponding partition of the set into equivalence classes. For the one which is not, identify which properties of an equivalence relation fail to hold.

Explanation / Answer

a)

It must ahve three properties

We denote the relation by R

for any element, x in X

xRx ie R is reflexive

For any element ,x,y in X so that xRy we must ahve yRx

ie R is symmetric

If, x,y,z in X so that

xRy and yRz then xRz ie R is transitive

b)

L is not an equivalence relation

2<3 hence, 2L3 but 3L2 is not true

S is an equivalence relation

mod 4 we ahve only two remainders:

4m,4m+2 type of numbers give remainder 0 then lie in one equivalence classes

And ,4m+1,4m-1 give remainder 1 on being squared modulo 4 belonging to another equivalence class

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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