Equivalence Relations: Solving & Proving Reflexivity, Symmetry & Transitivity

[Lancelot1]

Dear All,

I am trying to solve the attached two questions.

In both I need to determine if the relation is an equivalence relation, to prove it if so, and to find the equivalence classes.

In both cases it is an equivalence relation, and I managed to prove both relations are reflexive. Now I am with symmetry and transitivity. In the first case, it is obviously symmetric, but how do I prove it ? Same for the second relation, I find it hard to prove and also to prove transitivity.

For reflexivity, m-m = 0 which is dividable by 4. Also 7m-5m=2m, which is dividable by 2 and therefore even.

Thank you !

 

[topsquark]

Dear All,

I am trying to solve the attached two questions.

In both I need to determine if the relation is an equivalence relation, to prove it if so, and to find the equivalence classes.

In both cases it is an equivalence relation, and I managed to prove both relations are reflexive. Now I am with symmetry and transitivity. In the first case, it is obviously symmetric, but how do I prove it ? Same for the second relation, I find it hard to prove and also to prove transitivity.

View attachment 11885

For reflexivity, m-m = 0 which is dividable by 4. Also 7m-5m=2m, which is dividable by 2 and therefore even.

Thank you !

Some pointers.

For the first problem. Look at it this way. If mEn then 4|m - n. That means m - n = 4k, where k is some integer. If this is true then can you find such a k' for n - m? Any integer k' will do. Transitivity works on the same model.

For the second we have a similar idea. If mRn then 2|7m - 5n. So 7m - 5n = 2k. What can we say about the parities of m and n here? (ie. are they odd/even?) When this is true what can we say about 7n - 5m? Transitivity here isn't too bad. If we have mRn and nRp then we know that 7m - 5n = 2j and 7n - 5p = 2k. So again, what is the parity of m and n? Of n and p? So then what are the parities of m and p? So then what can we say about 7m - 5p?

Give it a go and if you are still having problems come back and show us what you've been able to do with it.

-Dan

 

[HallsofIvy]

Yes, you have shown that both are 'reflexive', mEm and mRm.

An "equivalence relation" must also be symmetric. We need to show that "if mEn then nEm" and "if mRn the nRm".
If mEn then 4 divides m- n so m- n= 4k for some integer k. Now n- m= -(m- n)= -4k= 4j where j=-k.
If mRn 7m- 5n is even so 7m- 5n= 2k for some integer k. 7m= 2k- 5n so that 7n- 5m= (7m- 5n)- (12m- 2n)= 2k- 2(6m- n)= 2(k- 6m+ n) an even number.

An "equivalence relation" must also be "transitive"- if mEn and nEp then mEp and if mRn and nRp then mRp.
If mEn then 4 divides m- n so m- n= 4k for some integer k.
If nEp then 4 divides n- p so n- p= 4k' for some integer k'.
m- p= (m- n)- (n- p)= 4k- 4k'= 4(k- k) so 4 divides m- p.

If mRn then 7m- 5n= 2k for some integer k.
If nRp then 7n- 5p= 2k' for some integer k'.
7m- 5p= (7m- 5n)+ (7n- 5p)- 2n= 2k+ 2k'- 2n= 2(k+ k'- 1) so is even.