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: Prove an Equivalence Relation R over N x N

  1. Oct 8, 2011 #1
    1. The problem statement, all variables and given/known data
    Given: A relation R over N x N
    ((x,y), (u,v)) belongs to R. i.e (x, y) ~ (u,v)

    If max(x,y) = max(u,v), given that
    max(x,y) = x if x >= y
    = y if x < y

    Prove that R is an equivalence relation

    2. Relevant equations
    I know that to prove an equivalence relation, I must prove that the
    relation satisfies : reflexivity, symmetry, and transitivity, but I
    somehow get confused on how to use the condition: max(x,y) = max(u,v)
    in my proof

    3. The attempt at a solution
    Here are my thoughts about the proof:

    To prove
    Given that (x,y) ~ (u,v)
    so max(x,y) = max(u,v) definitely

    My self-question: since (x,y) ~ (u,v). Does (u,v)~(x,y)?
    My thought: since max(x,y) = max(u,v), then flip the sides
    I have max(u,v) = max(x, y). This is always
    true, because (x,y) ~ (u,v)

    Transitivity: I get confused the most with this one, and I kind of get
    stuck with the proof from here too.

    My thought:
    Since I'm given ((x,y), (u,v)) belongs to R and (x,y) ~ (u,v)
    Can I let another ordered pairs, say (a,b) that also belongs to R
    and then use the following sequence:
    (x,y) ~ (u,v) and (u,v) ~ (a,b), then (x,y) ~ (a,b)?

    My question: how should I introduce (a,b) into the proof? How do I
    prove the fact that (u,v) ~ (a,b) is true, so that I can proceed later

    The most important question: are my thoughts, so far, correct? am I
    missing something?
  2. jcsd
  3. Oct 8, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    The reflexivity isn't going well. Reflexivity says (x,y)~(x,y). Is that always true? Translate that into the max statement. Symmetry seems ok. Transitivity says (x,y)~(u,v) and (u,v)~(w,z) implies (x,y)~(w,z). Can you show that?
  4. Oct 8, 2011 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    To prove reflexivity, you want to show that (x,y) ~ (x,y). No (u,v) at all in this part.
    The order is a bit mixed up here.

    1. You assume (x,y) ~ (u,v).
    2. This means by definition of R that max(x, y) = max(u, v).
    3. This implies max(u, v) = max(x,y). (Why?)
    4. Therefore...

    You need to fill in the last step.
    These two things mean the same thing.
    Yes, that's exactly what you do. You assume (x,y) ~ (u,v) and (u,v) ~ (a,b). Then show that this means that (x,y) ~ (a,b).
    You don't need to prove it. It's true by assumption. You want to show that the assumptions lead to the conclusion.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook