Results 1 to 10 of 10

Math Help - Equivalence Relations and Classes

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    24

    Equivalence Relations and Classes

    I am doing my first maths class since high school three years ago and I'm having trouble at getting my head around the abstraction of equivalence relations.

    The following table gives a list of 6 different relations.

    a) Which of the relations are equivalence relations? Mark anXin the column under “is equivalence relation?”for those which are equivalence relations.

    b) For those which are equivalence relations, give an example of an equivalence class (i.e., choose an elementxof the set, and write a list of all the elements equivalent tox, or a formula for all the elements if this isan infinite set).

    c) For those which are equivalence relations, in the last column of the table, write down the number ofequivalence classes (this could be infinite.)

    Each relation in this table is a relation on a given set, listed under “set”.

    Set / Relation
    1. R /aRb ⇐⇒ a−b is negative
    2. Z / aRb ⇐⇒ a−b is even
    3. R / aRb ⇐⇒ |a|=b
    4. R/ aRb ⇐⇒ |a|=|b|
    5. R/aRb ⇐⇒ |a|b=a|b|
    6.Z/aRb⇐⇒|a| − |b| is even


    Ok - What I think
    To be an equivalence relation the relation on the set needs to be reflexive, symmetric and transitive. I am having trouble with understanding how the reflexive requirement applies on any of these

    1. Every relation will be in Z so it is reflexive? Not symmetric. Not transitive
    2. Reflexive, Symmetric, transitive. 2 equivalence classes [0] and [1]
    3. Reflexive, not symmetric, not transitive.
    4. Reflexive, Symmetric, transitive. Equivalence classes [0],[1],[2],...[,oo]
    5. Reflexive, not symmetric, not transitive
    6. The same as 2.


    Any help/advice is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Relations

    Hello TTim
    Quote Originally Posted by TTim View Post
    I am doing my first maths class since high school three years ago and I'm having trouble at getting my head around the abstraction of equivalence relations.

    The following table gives a list of 6 different relations.

    a) Which of the relations are equivalence relations? Mark anXin the column under “is equivalence relation?”for those which are equivalence relations.

    b) For those which are equivalence relations, give an example of an equivalence class (i.e., choose an elementxof the set, and write a list of all the elements equivalent tox, or a formula for all the elements if this isan infinite set).

    c) For those which are equivalence relations, in the last column of the table, write down the number ofequivalence classes (this could be infinite.)

    Each relation in this table is a relation on a given set, listed under “set”.

    Set / Relation
    1. R /aRb ⇐⇒ a−b is negative

    Any relation is reflexive if aRa for all a in the set. In other words every element is related to itself - hence 'reflexive'.

    So for #1, is aRa for all a in the set? Clearly not, because a - a = 0, which is not negative.

    A relation is symmetric if for any a and b in the set, aRb if and only if bRa. So is #1 symmetric? In other words, does a - b < 0 mean that b - a < 0? Again, clearly not. In fact, the opposite is true. (This means that the relation is anti-symmetric.)

    A relation is transitive whenever aRb and bRc always means that aRc. So here if a - b < 0 and b - c < 0, does it follow that a - c < 0? A moment's thought will tell you that a - c = (a - b) + (b - c), and so the answer is yes, because we are adding together two negative numbers. So #1 is transitive.

    2. Z / aRb ⇐⇒ a−b is even
    (i) Is a - a even? Yes, because it's zero, of course. So it's reflexive.

    (ii) If a - b is even, is b - a even? Yes, because (b - a) = -(a - b). So it's symmetric.

    (iii) If a - b is even and b - c is even, is a - c even? Yes. Again, a - c = (a - b) + (b - c). So it's transitive.

    So #2 is an equivalence relation, and the integers are separated (partitioned) into just two equivalence classes: all the even numbers in one class, and all the odd numbers into the other.


    3. R / aRb ⇐⇒ |a|=b
    (i) Reflexive? Is |a| = a, for all a in R? What about a = -3?

    (ii) Symmetric? If |a| = b, does it follow that |b| = a? Again, what about a = -3 (and b = 3)?

    (iii) Transitive? If |a| = b, and |b| = c, must it follow that |a| = c?

    4. R/ aRb ⇐⇒ |a|=|b|
    Ask the same three questions again, as we did in #3, but this time it's |a| = |b|.

    5. R/aRb ⇐⇒ |a|b=a|b|
    ... and again here. Try some numbers, including as many combinations of positive and negative as you can think of.

    6.Z/aRb⇐⇒|a| − |b| is even
    Go carefully through #2 again, but this time with |a| and |b|. Does changing the signs (if necessary) to make it positive make any difference to whether the numbers are odd and even?

    You might also like to look at another posting where I give further examples of equivalence relations:
    http://www.mathhelpforum.com/math-he...tml#post239094

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Thankyou very much. I couldn't seem to quote quotes so I will just do it in an orderly fashion.

    4. R / aRb ⇐⇒ |a|=|b|
    Reflexive? |a|=|a| always. Reflexive
    Symmetric? if |a|=|b| then |b|=|a|. This obviously holds. Is there a proof?
    Reflexive? If |a|=|b| and |b|=|c| then |a|=|c|. Proof?

    So there would be infinite number of equivalent classes in R with each equivalence class only have two elements of a in R and two elements of b in R(is this worded correctly?) apart from (0,0).

    {(-1,-1),(-1,1),(1,-1),(1,1)} Is this an equivalence class. If so the general term for the infinite equivalence classes where n is an element of +R would be {(-n,-n),(-n,n),(n,-n),(n,n)}

    5.R/aRb ⇐⇒ |a|b=a|b|

    I still feel the same about the symmetry and transititity. (not symmetric, not transitive) but I am still confused with reflexiveness. Does my combination of (a,b) have to be (a,a) ((2,2) or (-8,-8) for example) when I test it here? If it does it will be reflexive. If the combination doesn't have to be (a,a) but (a,b) where a and b can be differentb ((-2,1) for example) then it will not be reflexive.

    I have to go to class now but I will continue with 6 later. In the meantime if anyone can spot errors or smooth out my confusion in q5 that would be great!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    24
    After working through this with a friend I see I still have errors in my second post. I understand it all now, if anyone wants to see the results I'll put them up if you ask.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by TTim View Post
    After working through this with a friend I see I still have errors in my second post. I understand it all now, if anyone wants to see the results I'll put them up if you ask.
    well, it wouldn't hurt to post your final work and have someone review it
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Jhevon View Post
    well, it wouldn't hurt to post your final work and have someone review it
    Sure, why not

    3. R / aRb ⇐⇒ |a|=b

    |-3| 3 therefore this is not reflexive, not an equiv relation

    4. R / aRb ⇐⇒ |a|=|b|

    |a|=|a| reflexive
    |a|=|b| => |b|=|a| symmetric
    if |a|=|b| and |b|=|c| => |a|=|c| transitive

    There are infinite equivalence classes.

    [1] = {1,-1)
    [n] = {n,-n}

    Is there an equivalence class [-1]? If there is does [-1] = [1]?

    5.R/aRb ⇐⇒ |a|b=a|b|
    |a|a=a|a| reflexive
    if |a|b=a|b| => |b|a= b|a| (just changed the order) symm.
    if |a|b=a|b|...(1) & |b|c=b|c|...(2) => |a|c=a|c| (working below) trans

    to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|

    There are three equivalence classes
    [1] = R+ and {0}
    [0] = R
    [-1] = R- and {0}

    5 was the tough one for me and 4 is the one where I still have a question. Any answers for my question in bold?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Relations

    Hello TTim
    3. R / aRb ⇐⇒ |a|=b

    |-3| 3 therefore this is not reflexive, not an equiv relation

    This is correct.

    4. R / aRb ⇐⇒ |a|=|b|
    |a|=|a| reflexive
    |a|=|b| => |b|=|a| symmetric
    if |a|=|b| and |b|=|c| => |a|=|c| transitive

    There are infinite equivalence classes.

    [1] = {1,-1)
    [n] = {n,-n}

    OK, apart from a minor typo.

    Is there an equivalence class [-1]? If there is does [-1] = [1]?

    Yes. [n] = [-n]. You can use any element in an equivalence class to represent the whole class.

    5.R/aRb ⇐⇒ |a|b=a|b|
    |a|a=a|a| reflexive
    if |a|b=a|b| => |b|a= b|a| (just changed the order) symm.
    if |a|b=a|b|...(1) & |b|c=b|c|...(2) => |a|c=a|c| (working below) trans

    to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|

    There are three equivalence classes
    [1] = R+ and {0}
    [0] = R
    [-1] = R- and {0}

    5 was the tough one for me and 4 is the one where I still have a question. Any answers for my question in bold?

    The problem occurs when b = 0, and you get the familiar 'division by zero' error.

    It's not transitive, of course, because if b = 0, |a|b = a|b| = 0 = |b|c = c|b| for any a and c.

    Otherwise, I think you've done some good work here.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Grandad View Post
    It's not transitive, of course, because if b = 0, |a|b = a|b| = 0 = |b|c = c|b| for any a and c.

    Ahhhh, so it would be transitive if the set was all R apart from zero? This one element (zero) causes the set not to be transitive and therefore not an equivalence relation so therefore it cannot have equivalence classes. Where did I go wrong in my proof?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Equivalence Relations

    Hello TTim
    Quote Originally Posted by TTim View Post
    Ahhhh, so it would be transitive if the set was all R apart from zero?
    Yes. The equivalence classes would then be \mathbb{R^+} and \mathbb{R^-}.

    This one element (zero) causes the set not to be transitive and therefore not an equivalence relation so therefore it cannot have equivalence classes. Where did I go wrong in my proof?
    As I said, it's a 'division by zero' error. You said:
    to prove trans divide LHS of (1) by RHS of (2) and RHS of (1) by LHS of (2) => (|a|b)/(b|c|) = (a|b|)/(|b|c) => |a|/|c| = a/c => |a|c = a|c|
    But this doesn't work if b = 0, because you're relying on being able to divide by b|c| and |b|c. Essentially, you've got something equivalent to this:

    bx = by \Rightarrow \frac{bx}{b} = \frac{by}{b} \Rightarrow x = y, which is not correct.

    The correct statement is bx = by \Rightarrow b = 0 \text{ or }x = y.

    Is that OK now?

    Grandad

    PS I've just spotted a typo in my previous posting: |b|c = c|b| should, of course, be |b|c = b|c|.
    Last edited by Grandad; March 13th 2009 at 03:18 AM. Reason: Add PS
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Mar 2009
    Posts
    24
    Quote Originally Posted by Grandad View Post
    As I said, it's a 'division by zero' error.
    Sorry I didn't know that was its actual name.

    Thankyou very much for your help. I feel like I have a good grasp on this stuff now.

    Tim
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 19th 2011, 01:09 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 classes and relations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2008, 06:28 AM
  5. Equivalence relations and classes.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2008, 05:51 AM

Search Tags


/mathhelpforum @mathhelpforum