# Finding the relation for the partitions { 2x } and { 2x + 1 }

I have to find an equivalence relation in the set of natural numbers which has the two partitions

{ 2x } and { 2x + 1 }


My first thought was

R = { (x,y) in N² : 2 | x + y }


I assume that this is incorrect, because the set is N² and N.

Then I thought about the following:

R = { x in N : ∃ y in N : 2 | x + y }


Is that a correct way to define the relation with the partitions described above?

Your first thought is correct. A binary relation in $\mathbb N$ is supposed to be a subset of $\mathbb N^2$, so having a set of pairs of numbers is exactly what you need to write here.

• Thank you for your help. Is the second relation also correct or is it incorrect?
– xxsl
Nov 27 '14 at 20:56
• @xxsl: Your second set is not a relation at all -- it is a subset of $\mathbb N$ (in fact it is all of $\mathbb N$, since we can always make $2\mid x+y$ hold by choosing $y$ to be $x$), whereas a relation must be a subset of $\mathbb N\times\mathbb N$. Nov 27 '14 at 20:58
• Thank you for the insight. I was worried about that (that it is in fact all of N), but I thought I had to do it this way to avoid NxN.
– xxsl
Nov 27 '14 at 20:59

Your first relation works. Can you prove it?

(You went to your second relation because you were concerned about $\Bbb N^2$ being the wrong set, but remember that a relation on a set $A$ is a subset of $A\times A$, so you actually do want $R\subseteq\Bbb N^2$.)

• Thank you for your help. My proof would be that the equivalences classes are { 0, 2, 4, ... } and { 1, 3, 5, ... }
– xxsl
Nov 27 '14 at 20:57
• Right, but you would have to prove that statement, too :) Nov 27 '14 at 21:03

R = {(x,y) : 2 | (x - y)}

(x,y) is in R if and only if x and y are either both even or both odd.