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!

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
    Reflexivity:
    Given that (x,y) ~ (u,v)
    so max(x,y) = max(u,v) definitely

    Symmetry:
    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
    steps?

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

    Dick

    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

    vela

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove an Equivalence Relation R over N x N
  1. Prove x^n < n! (Replies: 4)

  2. Prove x^n<y^n (Replies: 1)

  3. R^n\{x} is connected (Replies: 2)

Loading...