Expert: Paul Klarreich - 11/10/2008

Question
Paul, thanks for your help so far. I do not understand this next one at all. I am anxious to see your explanation.

A relation R is defined on the set of natural numbers by aRb if and only if a^2 + b^2 is even. Prove that R is an equivalence relation. Determine the distinct equivalence classes.

Answer
Questioner:   Pete
Category:  Advanced Math
Private:  No
 
Subject:  Proofs
Question:  Paul, thanks for your help so far. I do not understand this next one at all. I am anxious to see your explanation.

A relation R is defined on the set of natural numbers by aRb if and only if a^2 + b^2 is even. Prove that R is an equivalence relation. Determine the distinct equivalence classes.
......................................
Hi, Pete,

ALWAYS  ALWAYS  ALWAYS  ALWAYS  ALWAYS  ALWAYS  ALWAYS
start by writing the definition, to make sure you know what the words say.  [Then make sure you know what the words mean.]

Equivalence:  You have to show that:

1. Reflexive:  aRa.
2. Symmetric:  If aRb then bRa.
3. Transitive: If aRb and bRc then aRc.

Now just use the relation to show those are true.

Such as:

1. Reflexive:  a^2 + a^2 is even.  Can you do this?
2. Symmetric:  If a^2 + b^2 is even then prove b^2 + a^2 is even.  This too, you should be able to handle.
3. Transitive: If a^2 + b^2 is even AND b^2 + c^2 is even can you prove that a^2 + c^2 is even?

If you can't do part 3, let me know.