0

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?

xxsl
  • 99

3 Answers3

1

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

Eric Stucky
  • 12,758
  • 3
  • 38
  • 69
1

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.

hmakholm left over Monica
  • 286,031
  • Thank you for your help. Is the second relation also correct or is it incorrect? – xxsl Nov 27 '14 at 20:56
  • 1
    @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$. – hmakholm left over Monica 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
0

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.

leaveswater02
  • 578