Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Equivalence relation

  1. May 12, 2008 #1
    1. The problem statement, all variables and given/known data
    We define a relation ~ for N^2 by:

    (n, m) ~(k, l) <=> n + l = m + k

    Show that ~ is a equivalence relation

    2. Relevant equations

    A relation R on a set A is equivalent if R is:
    reflexive if x R x for all x that is an element of A
    symmetric if x R y implies y R x, for all x,y that is an element of A
    transitive if x R y and y R z imply x R z, for all x,y,z that is an element of A

    3. The attempt at a solution
    I have to prove this by showing that the relation is reflexive, symmetric and transitive. The symmetric part i understand, the fact that we can turn the relation around and it will be the same: n + l = m + k vs m + k = n + l.

    But how do I prove the refexive and transitive part? I am really confused by the ~ and do not quite understand why it appears both as the name of the relation and as an element of the relation itself.
  2. jcsd
  3. May 12, 2008 #2


    User Avatar
    Homework Helper
    Gold Member

    To prove reflexivity, you must check whether (x,y) ~ (x,y), i.e. whether any element a of [tex]N^2[/tex] satisfies a ~ a . By using the definition of ~ that you gave, can you check that (x,y) ~ (x,y)?

    For transitivity, you must check whether (a,b) ~ (c,d) and (e,f) ~ (g,h) implies (a,b) ~ (g,h). Again, its just a matter of using the definition of ~.
    Last edited: May 12, 2008
  4. May 12, 2008 #3
    You mean by writing (x, y) ~ (x, y) <=> x + y = x + y ?

    I think my problem is that I get really confused by the ~ and what it means.
  5. May 12, 2008 #4


    User Avatar
    Homework Helper
    Gold Member

    ~ is a relation, just like < or >. Just like you can check whether a < b, you can check whether (a,b) ~ (c,d) using the definition of ~ that you gave.
  6. May 12, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi thenoob! Welcome to PF! :smile:

    Maybe this will help … :smile: (and maybe it won't! :redface:)

    An equivalence relation separates N^2 into mutually exclusive sets.

    Anything in one set ~ anything else in that set, but ~ nothing in any other set.

    Everything is in exactly one set.

    So how would you describe the set (the equivalence class) that (1,0) is in (if necessary, pick a few examples, and find a pattern)? :smile:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook