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: 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