A relation $R$ is defined on $\Bbb N$ by $aRb$ if $a^2+b^2$ is even.
a) Prove $R$ is an equivalence relation.
b) Determine the distinct equivalence classes.
I am having trouble with the transitive part of the proof and the distinct classes.
Asked
Active
Viewed 156 times
0
-
If $a^2+b^2$ is even then or both quantities are even, or both quantities are odd. But it cannot be the case that $a$ is even and $b$ is odd. From here define two relations $aRb$ and $bRc$ and deduce that $aRc$. – Masacroso Nov 15 '16 at 02:35
2 Answers
0
It is just congruence modulo 2. This is an equivalence relation by a previous result in your book.
Jacob Wakem
- 2,382
-
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review – Cave Johnson Nov 15 '16 at 03:39
-
@CaveJohnson Yes its an answer. When I was an undergraduate I had the same problem and solved it similarly. – Jacob Wakem Nov 15 '16 at 03:50
-
1I understand that what you post would help to solve the problem. But usually an answer is supposed to be in good format, more or less self-contained, and with a precise reference when needed. Otherwise. comment is a better choice. – Cave Johnson Nov 15 '16 at 04:03
0
A common trick to prove transitivity when working with relations involving "$+$" or "$-$" is to add them together. In this case, suppose $aRb$ and $bRc$, so $a^{2}+b^{2}$ and $b^{2}+c^{2}$ are even. If we add these together we find that $a^{2}+2b^{2}+c^{2}$ is even. Thus, since $2b^{2}$ is even, we see that $a^{2}+c^{2}$ is even. In other words, we have shown $aRc$. This proves transitivity.
For the distinct classes, just observe that $aRb$ if and only if $a,b$ are both odd or both even (i.e. $a,b$ are congruent modulo $2$). Thus the two distinct equivalence classes are just the even numbers and the odd numbers.
JonCC
- 1,188
-
That makes sense now. I am still not sure about distinct classes and how to determine them for other problems. Thanks. – Jeffjg18 Nov 15 '16 at 03:20