1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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