Results 1 to 10 of 10
Like Tree4Thanks
  • 1 Post By topsquark
  • 1 Post By romsek
  • 1 Post By emakarov
  • 1 Post By Plato

Math Help - Sketching the equivalence classes of R N x N

  1. #1
    Junior Member
    Joined
    Nov 2013
    From
    Germany
    Posts
    40
    Thanks
    1

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,667
    Thanks
    298
    Awards
    1

    Re: Sketching the equivalence classes of R N x N

    Quote Originally Posted by Cyganek View Post
    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
    Thanks from Cyganek
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2013
    From
    Germany
    Posts
    40
    Thanks
    1

    Re: Sketching the equivalence classes of R N x N



    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?
    Last edited by Cyganek; November 23rd 2013 at 01:56 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    1,554
    Thanks
    569

    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.
    Thanks from Cyganek
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2013
    From
    Germany
    Posts
    40
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Sketching the equivalence classes of R N x N

    Quote Originally Posted by Cyganek View Post
    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.
    Thanks from Cyganek
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1

    Re: Sketching the equivalence classes of R N x N

    Quote Originally Posted by Cyganek View Post
    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 View Post
    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 0\notin\mathbb{N},
    But it makes the construction of \mathbb{N} easier from a set-theoretic point of view to include 0.

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

    Note that \mathcal{R}[k] contains k+1 pairs.
    Last edited by Plato; November 23rd 2013 at 07:47 AM.
    Thanks from Cyganek
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2013
    From
    Germany
    Posts
    40
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Sketching the equivalence classes of R N x N

    Quote Originally Posted by Cyganek View Post
    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 f : \mathbb{N}\times\mathbb{N}/R\to\mathbb{N}, p\mapsto \pi_1(p)+\pi_2(p) where I define \pi_i to be the ith projection, i.e., \pi_i(x_1,x_2)=x_i. The symbol \mapsto even has the name \mapsto in LaTeX.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    1,554
    Thanks
    569

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 17th 2013, 04:12 PM
  2. Replies: 10
    Last Post: January 14th 2010, 12:28 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM
  5. Equivalence classes
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 1st 2007, 07:57 AM

Search Tags


/mathhelpforum @mathhelpforum