1. ## Equivalence Relation Question

I've got another question.

Problem:
Let R be a relation on A. (a,b) $\in$ 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 $\in$ A such that a $\in$ Z.
if 3a + a = 4n
then a = n and (a,a) $\in$ R.
I assumed that because we have IFF I have to go the other way...
if (a,a) $\in$ 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?

2. Originally Posted by Alterah
I've got another question.

Problem:
Let R be a relation on A. (a,b) $\in$ 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 $\in$ A such that a $\in$ Z.
if 3a + a = 4n
then a = n and (a,a) $\in$ R.
I assumed that because we have IFF I have to go the other way...
if (a,a) $\in$ 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.

3. Originally Posted by Alterah
I've got another question.

Problem:
Let R be a relation on A. (a,b) $\in$ 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 $\mathbb{Z}$

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

For Reflexive I've got:
Let a $\in$ A such that a $\in$ Z.
if 3a + a = 4n
then a = n and (a,a) $\in$ R.
I assumed that because we have IFF I have to go the other way...
if (a,a) $\in$ 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 $(a,b)\in R\Longrightarrow 3a+b=4n$ for some $n\in\mathbb{Z}$ ; we know that $(b,a)\in R\iff 3b+a=4m$ for some $m\in\mathbb{Z}$ , but then we can write:

$a+3b=3a+b+2(b-a)=4n+2(b-a)=4k$ since $a,b$ must have the same parity (why? Check this from the assumption that $3a+b=4n$...if you

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

This proves that if $(a,b)\in R$ then also $(b,a)\in R$ and you have symmetry...and more: we've discovered that if $(x,y)\in R$ then both integers $a,b$ 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 $(a,b),\,(b,c)\in R$ ...)

Tonio

4. Thanks, that's what I needed.