Sketching the equivalence classes of R N x N

Relation R on ℕ x ℕ

((a,b),(c,d)) R <=> a+b = c+d

Ok I had to prove that R is an equivalence relation (Reflexivity, symmetry, transtitivity). I already did that. Second part is to sketch all equivalence classes of R.

I dont understand or the way to sketch it. Do I have to draw a matrix? Or a coordinate system?

A coordinate system would simply cover the whole positive area of it. But I need to sketch the CLASSES of R so I dont think I understand it the way I should. What am I overlooking?

Re: Sketching the equivalence classes of R N x N

Quote:

Originally Posted by

**Cyganek** Relation R on ℕ x ℕ

((a,b),(c,d)) R <=> a+b = c+d

Ok I had to prove that R is an equivalence relation (Reflexivity, symmetry, transtitivity). I already did that. Second part is to sketch all equivalence classes of R.

I dont understand or the way to sketch it. Do I have to draw a matrix? Or a coordinate system?

A coordinate system would simply cover the whole positive area of it. But I need to sketch the CLASSES of R so I dont think I understand it the way I should. What am I overlooking?

Hint: Plot the point (a, b). Now plot any point which is equivalent to it. What kind of graph do you see?

-Dan

Re: Sketching the equivalence classes of R N x N

http://i.imgur.com/zVRFOb0.png

Red line = Class

Green dots = Actual elements (Because we are only looking at ℕ)

Is this correct?

Follow up Queston: I need to find a bijection for f: (ℕ x ℕ)/R --> ℕ

but I dont understand the question, especially the (ℕ x ℕ)/R.

Divisible by R? What do I need to do here? Example?

Re: Sketching the equivalence classes of R N x N

I wouldn't call the lines the class. Each class is the set of points (m,n) in NxN that lie on each of those lines. The lines also contain infinite coordinate pairs that aren't in the class because they aren't natural numbers.

One small problem with your drawing is that you've included the points on the axes which is incorrect. 0 is not a natural number.

So for example C[2] = {(1,1)}, C[3] = {(1,2),(2,1)}, C[4] = {(1,3),(2,2),(3,1)} etc. The classes consist of pairs of natural numbers.

As for your followup question. I'm going to assume that NxN/R is the set of equivalence classes generated by R over NxN, i.e. the classes you just derived.

So you are looking for a bijection, a one to one mapping, from each class to N. One such mapping is pretty obvious with a moment's thought.

Re: Sketching the equivalence classes of R N x N

First: Thanks. I used the lines to just "group" the points up. I know that for example 0,5+0,5 is not in the class, thats why specifically made dots to show the actual elements. But yea all you say makes sense - thank you :)

Second: So if I take a look at C[4].

Do you mean something like this?

f(1) = 3

f(2) = 2

f(3) = 1

Re: Sketching the equivalence classes of R N x N

Quote:

Originally Posted by

**Cyganek** Second: So if I take a look at C[4].

Do you mean something like this?

f(1) = 3

f(2) = 2

f(3) = 1

The function f should take an entire class, not elements of a class, and map it to a single natural number.

Re: Sketching the equivalence classes of R N x N

Quote:

Originally Posted by

**Cyganek** Relation R on ℕ x ℕ

((a,b),(c,d)) R <=> a+b = c+d

Second part is to sketch all equivalence classes of R.

Quote:

Originally Posted by

**romsek** One small problem with your drawing is that you've included the points on the axes which is incorrect.

0 is not a natural number.

I do not agree with that. Now I know that there are some who would say $\displaystyle 0\notin\mathbb{N}$,

But it makes the construction of $\displaystyle \mathbb{N}$ easier from a set-theoretic point of view to include 0.

It also makes this question interesting. $\displaystyle \forall k\in\mathbb{N}$ the equivalence class $\displaystyle \mathcal{R}[k]=\{(n,m)\in \mathbb{N}\times\mathbb{N}: n+m=k\}$

Note that $\displaystyle \mathcal{R}[k]$ contains $\displaystyle k+1$ pairs.

Re: Sketching the equivalence classes of R N x N

Yea that makes sense... so how do I write it correctly for the class C[4] = {(1,3),(2,2),(3,1)} ? For example I am mapping all of these pairs on 4. I just dont know how to write it mathematically right.

Edit: @Plato: In my course we use ℕ and ℕ0 to express one or another. I heard it depends on the professor and is different from place to place.

Re: Sketching the equivalence classes of R N x N

Quote:

Originally Posted by

**Cyganek** so how do I write it correctly for the class C[4] = {(1,3),(2,2),(3,1)} ? For example I am mapping all of these pairs on 4.

I am also not sure about the notation C[k]. It would be OK if it had an explicit definition, like R[k] is defined in post #7. It is customary to denote the equivalence class of x by [x], so without an explicit definition it would seem that C[k] refers to the equivalence class of k, which is a type error because the relation is defined on pairs of numbers, not individual numbers. In contrast, [(3,1)] is OK: [(3,1)] = {(1,3), (2,2), (3,1)}.

One way to write f would be f([(m, n)]) = m + n. As usual, one has to prove that this definition does not depend on the representative (m, n).

Another way is to write $\displaystyle f : \mathbb{N}\times\mathbb{N}/R\to\mathbb{N}$, $\displaystyle p\mapsto \pi_1(p)+\pi_2(p)$ where I define $\displaystyle \pi_i$ to be the *i*th projection, i.e., $\displaystyle \pi_i(x_1,x_2)=x_i$. The symbol \mapsto even has the name \mapsto in LaTeX.

Re: Sketching the equivalence classes of R N x N

the notation C[k] is something I made up at the moment and used it because it should be obvious what it means in the context of it's use. If you all are going to pick away at every last detail of perfectly reasonable answers I'll find somewhere else to help. Enjoy.