MHB Equivalence Relations: Solving & Proving Reflexivity, Symmetry & Transitivity

Lancelot1
Messages
26
Reaction score
0
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.

1659787389283.png


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

Thank you !
 
Physics news on Phys.org
Lancelot said:
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
 
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.
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
Back
Top