0
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your help. Is the second relation also correct or is it incorrect? $\endgroup$
    – xxsl
    Nov 27 '14 at 20:56
  • 1
    $\begingroup$ @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$. $\endgroup$ Nov 27 '14 at 20:58
  • $\begingroup$ 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. $\endgroup$
    – xxsl
    Nov 27 '14 at 20:59
1
$\begingroup$

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$.)

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.