1. ## Equivalence Relation Question

I've got another question.

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

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

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

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

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

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

Tonio

4. Thanks, that's what I needed.