## jango_IN_DTOWN one year ago Equivalence relation problem

1. jango_IN_DTOWN

2. jango_IN_DTOWN

@ganeshie8

3. ganeshie8

|dw:1444584458933:dw|

4. ganeshie8

for each relation, we need to check : 1) reflexive 2) symmetry 3) transitive

5. ganeshie8

for i : reflexive : $$(x_1, y_1)\sim (x_1,y_1)$$ because $$y_1=y_1$$ symmetry : $$(x_1,y_1)\sim(x_2,y_2) \implies (x_2,y_2)\sim (x_1,y_1)$$ because $$y_1=y_2 \implies y_2=y_1$$ transitivity : $$(x_1,y_1)\sim(x_2,y_2)$$ and $$(x_2,y_2)\sim (x_3,y_3)$$ $$\implies (x_1,y_1)\sim (x_3,y_3)$$ because $$y_1=y_2$$ and $$y_2=y_3$$$$\implies y_1=y_3$$ therefore, this is an equivalence relation

6. jango_IN_DTOWN

the reflexive part in i) I am having a confusion

7. ganeshie8

to better understand reflexivity, maybe consider a relation that is not reflexive

8. ganeshie8

first of all, as the name says, "reflexive" refers to the reflection that you see when u look at mirror. you see your own reflection... we say a relation is reflexive if $$x\sim x$$ for all $$x$$ in the relation.

9. ganeshie8

can you think of a relation that is not reflexive ?

10. jango_IN_DTOWN

yes a>b

11. ganeshie8

nice, another one : a-b is odd

12. jango_IN_DTOWN

yeah

13. ganeshie8

so do you get why the relation in part i is reflexive ?

14. jango_IN_DTOWN

yes now it is clear..

15. ganeshie8

review quick top 3 properties |dw:1444585876121:dw|

16. jango_IN_DTOWN

checked..

17. ganeshie8

can you guess what the equivalence classes will be

18. jango_IN_DTOWN

x will be any member of R and y will be fixed

19. ganeshie8

Exactly! for example below is an equivalence class : [(x, 1)] = {(1,1), (2,1), (2.2, 1), (-99, 1), ... }

20. ganeshie8

below is another equivalence class [(x, 3)] = {(1,3), (2,3), (2.2, 3), (-99, 3), ... }

21. jango_IN_DTOWN

[(x,y)]={(a,b)belongs to R^2 such that b=y}

22. ganeshie8

looks nice

23. jango_IN_DTOWN

so this is the answer right?

24. ganeshie8

Yes thats the answer for part i

25. ganeshie8

look at the relation in part ii, whats ur first guess, can it be an equivalence relation ?

26. jango_IN_DTOWN

I think it is reflexive and symmetric but transitivity cant say

27. ganeshie8

right, just show an example that its not transitive

28. jango_IN_DTOWN

then we need to consider general points of R^2

29. ganeshie8

yes just pick any one simple example

30. jango_IN_DTOWN

(1,2)~(1,3) and(1,3)~(2,3) but (1,2) is not ~ to (2,3)

31. ganeshie8

that will do, that proves the relation is not transitive consequently its not equivalence relation

32. jango_IN_DTOWN

yes correct and hence no question of equivalence classes arise

33. ganeshie8

good iii looks innocent, but it can be very tricky...

34. ganeshie8

because there are several ways to get an integer by taking difference of two numbers : 3 - 1 = integer 1.4 - 0.4 = integer 0.3 - 0.3 = integer ..

35. jango_IN_DTOWN

ohhhh

36. ganeshie8

proving that it is an equivalence relation is trivial but figuring out equivalence classes can be tricky...

37. jango_IN_DTOWN

we see that the y component can be anything

38. ganeshie8

hey wait, does it really pass transitivity ?

39. jango_IN_DTOWN

yeah if a-b is an integer and b-c is an integer then a-c must be an integer

40. jango_IN_DTOWN

a-c=(a-b)+(b-c)= sum of integers

41. ganeshie8

Ahh thats clever! okay so it does pass transitivity

42. jango_IN_DTOWN

yes.. and the symmetric and reflexive parts are also satisfied.. so we need to figure out the equivalence realtion

43. ganeshie8

you mean equivalence classes

44. jango_IN_DTOWN

yeah oops

45. jango_IN_DTOWN

so our y component can be anything

46. jango_IN_DTOWN

but x component will be those real numbers whose difference gives integer

47. ganeshie8

How about this [(x,y)]={(a,b)belongs to R^2 such that a = x-floor(x)+k, $$k \in \mathbb Z$$}

48. ganeshie8

floor(x) gives the integer part of x so, x - floor(x) gives the fractional part of x

49. jango_IN_DTOWN

yeah it gives integer always I thought of another one, [(x,y)]={(a,b)belongs to R^2 such that (x-a) belongs to Z}

50. ganeshie8

looks much better!

51. jango_IN_DTOWN

But both will work

52. ganeshie8

mine is like construction your's is more like a logic statement yeah both works, but yours looks better

53. jango_IN_DTOWN

Thanks. so we are done with the questions. I just need to construct the language only..:)

54. ganeshie8

np :)