Thread: Equivalence Relation Question

I've got another question.

Problem:
Let R be a relation on A. (a,b) R IFF 3a + b = 4n for some integer n. Prove that R is an equivalence relation on Z.

I assumed the Z part was a typo, but am not sure now...

I know I need to show that R is reflexive, symmetric, and transitive.

For Reflexive I've got:
Let a A such that a Z.
if 3a + a = 4n
then a = n and (a,a) R.
I assumed that because we have IFF I have to go the other way...
if (a,a) R, then 4a = 4n and a = n which checks.

For Symmetric and Transitive...I am at a loss, don't I have to do two statements here for the IFF...or am I getting confused and using given information in the proof?

Originally Posted by Alterah

I've got another question.

Problem:
Let R be a relation on A. (a,b) R IFF 3a + b = 4n for some integer n. Prove that R is an equivalence relation on Z.

I assumed the Z part was a typo, but am not sure now...

I know I need to show that R is reflexive, symmetric, and transitive.

For Reflexive I've got:
Let a A such that a Z.
if 3a + a = 4n
then a = n and (a,a) R.
I assumed that because we have IFF I have to go the other way...
if (a,a) R, then 4a = 4n and a = n which checks.

For Symmetric and Transitive...I am at a loss, don't I have to do two statements here for the IFF...or am I getting confused and using given information in the proof?

Z is definately not a typo. For e.g. the relation fails for (.5,.5)

You need to state your working more systematically. This is not a tough question I presume.

Originally Posted by Alterah

I've got another question.

Problem:
Let R be a relation on A. (a,b) R IFF 3a + b = 4n for some integer n. Prove that R is an equivalence relation on Z.

I assumed the Z part was a typo, but am not sure now...


Why do you think so? It really is a transitive relation on

I know I need to show that R is reflexive, symmetric, and transitive.

For Reflexive I've got:
Let a A such that a Z.
if 3a + a = 4n
then a = n and (a,a) R.
I assumed that because we have IFF I have to go the other way...
if (a,a) R, then 4a = 4n and a = n which checks.

For Symmetric and Transitive...I am at a loss, don't I have to do two statements here for the IFF...or am I getting confused and using given information in the proof?

Suppose for some ; we know that for some , but then we can write:

since must have the same parity (why? Check this from the assumption that ...if you

can do arithmetic modulo 4 this is pretty simple) so then is even and thus is a multiple of 4...!

This proves that if then also and you have symmetry...and more: we've discovered that if then both integers have

the same parity (I honestly didn't have a clue before beginning to do the maths for symmetry).

Now you try to do transitivity by yourself (idea: sum up both eq's for ...)

Tonio

Thanks, that's what I needed.