Results 1 to 9 of 9

Math Help - equivalence class

  1. #1
    Junior Member
    Joined
    Feb 2010
    Posts
    45

    equivalence class

    Find the equivalence class
    from the set of {0,1,2,3}
    for
    {(0,0)(1,1),(2,2),(3,3))
    and
    {(0,0),(1,1)(1,2)(2,1)(2,2)(3,3)}

    I said for the first one it is [a]={a,a} if 0<=a<=3. Not sure if thats right

    I don't know what the second is..some help appreciated.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Find the equivalence class
    Do you need to find all classes or just one class?

    I said for the first one it is [a]={a,a} if 0<=a<=3.
    This is correct, but also recall that {a,a}={a} as sets.

    I don't know what the second is..some help appreciated.
    Draw a graph with vertices 0, 1, 2, 3 and an edge between each a, b such that (a, b) is in the relation. If you can travel from one vertex to another, they belong to the same equivalence class; otherwise they belong to different classes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by emakarov View Post
    Do you need to find all classes or just one class?

    This is correct, but also recall that {a,a}={a} as sets.

    Draw a graph with vertices 0, 1, 2, 3 and an edge between each a, b such that (a, b) is in the relation. If you can travel from one vertex to another, they belong to the same equivalence class; otherwise they belong to different classes.
    thanks!
    let me answer your first question first..I need to find all the classes.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Ok, so i put 0 1 2 3 as vertices..I then drew lines between the ones that are in the relation. I'm guessing (0,0), (1,1) don't have lines then because you can't connect them to themselves? If so i only end up with a line from 1 to 2...does that mean only (1,2) and (2,1) are in the equivalence class?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    Caveat: what I am offering is not a manual procedure set in stone; it's just a way to visualize the situation and find an answer.

    I'm guessing (0,0), (1,1) don't have lines then because you can't connect them to themselves?
    It makes sense to have a loop at every vertex. They correspond to (0,0), (1,1), (2,2) and (3,3).

    If so i only end up with a line from 1 to 2
    And a line from 2 to 1. In fact, we are talking not about lines but about arrows: one from 1 to 2 and one back.

    does that mean only (1,2) and (2,1) are in the equivalence class?
    (1,2) and (2,1) are not elements of the set. They are elements of the relation, whereas equivalence classes are subsets of the original set, not relation. This would mean that 1 and 2 are in one equivalence class. The other two classes are singletons (one-element sets) {0} and {3}.

    In general, suppose you draw a diagram of a relation as described above. Then the relation is an equivalence relation if: (1) every vertex has a loop, (2) for every arrow from a to b there is an arrow back from b to a, and (3) if you can go from a to b in several steps, you can also do this in one step. These conditions are reflexivity, symmetry and transitivity of the relation expressed in terms of arrows and vertices. Given such diagram, an equivalence class consists of all vertices that are interconnected.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Quote Originally Posted by emakarov View Post
    Caveat: what I am offering is not a manual procedure set in stone; it's just a way to visualize the situation and find an answer.

    It makes sense to have a loop at every vertex. They correspond to (0,0), (1,1), (2,2) and (3,3).

    And a line from 2 to 1. In fact, we are talking not about lines but about arrows: one from 1 to 2 and one back.

    (1,2) and (2,1) are not elements of the set. They are elements of the relation, whereas equivalence classes are subsets of the original set, not relation. This would mean that 1 and 2 are in one equivalence class. The other two classes are singletons (one-element sets) {0} and {3}.

    In general, suppose you draw a diagram of a relation as described above. Then the relation is an equivalence relation if: (1) every vertex has a loop, (2) for every arrow from a to b there is an arrow back from b to a, and (3) if you can go from a to b in several steps, you can also do this in one step. These conditions are reflexivity, symmetry and transitivity of the relation expressed in terms of arrows and vertices. Given such diagram, an equivalence class consists of all vertices that are interconnected.
    Ok so in this case all those conditions are satisfied. so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771
    so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?
    Again, don't confuse the original set A = {0,1,2,3} with the relation R on A. Both A and R are sets, but elements of A are numbers, while elements of R are pairs of numbers. Speaking in programmer's terms, A and R have different types.

    Equivalence classes are subsets of A, so they also consist of individual numbers, not pairs. So you have [0] = {0}, [1] = [2] = {1,2}, and [3] = {3}.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,414
    Thanks
    1328
    Quote Originally Posted by bfpri View Post
    Ok so in this case all those conditions are satisfied. so the equivalence classes would have [1,2]={(1,1),(2,2)(1,2),(2,1) and [0]={(0,0) and [3]={(3,3)} correct?
    No. A "relation" on set A is a set of ordered pairs from A. "Equivalence classes" are subsets of A.

    For the first one, {(0,0)(1,1),(2,2),(3,3)) you should be able to see that 0 is equivalent to itself and nothing else: one equivalence class is {0}. Similarly, 1 is equivalent to itself and nothing else: another equivalence class is {1}. There are two more equivalence classes. What are they?


    For the second, {(0,0),(1,1)(1,2)(2,1)(2,2)(3,3)}. 0 is equivalent to itself and nothing else: one equivalence class is {0}. 1 is equivalent to itself and is equivalent to 2 (which, of course, is equivalent to itself and 1): another equiivalence class is {1, 2}. There is one more equivalence class.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Feb 2010
    Posts
    45
    Ahhhh Alright I get it now. I was understanding the equivalence classes wrong. Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  2. Equivalence Class HELP!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 19th 2009, 06:52 AM
  3. equivalence class ?
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 29th 2008, 08:42 AM
  4. equivalence class
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 20th 2008, 06:32 PM
  5. Equivalence class
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 10th 2007, 02:50 AM

Search Tags


/mathhelpforum @mathhelpforum