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: Binary relations: weak order, strict partial order, equivalence

  1. Oct 27, 2009 #1
    1. The problem statement, all variables and given/known data

    I'm totally lost about this. I know the properties of binary relations (or at least I think I know them, what it means to be transitive, complete etc).

    This exercise asks me to show that P and I are strictly partial and equivalent respectively when P and I are defined in terms of R, a weak order. How do I apply the properties to do this? What should my steps be?

    The exercise:

    Let R be a weak order relation. The relation P is defined by xPy if and only if xRy and not yRx and the relation I is defined by xRy if and only if xRy and yRx.

    2. Relevant equations

    The question does not supply these but these are the definitions of 'weak order', 'strictly partial order' and 'equivalence' as given by the lecturer's notes:

    Weak order: a binary relation that satisfies transitivity and completeness.
    Strictly partial order: a binary relation that satisfies transitivity and asymmetry.
    Equivalence: a binary relation that satisfies transitivity and symmetry.

    3. The attempt at a solution

    I started by writing out what R, P and I would normally be just to be a weak order, strict partial order and equivalence:

    R: xRy: [tex]\forall[/tex]x,y,z in X, xRy [tex]\wedge[/tex] yRz => xRz (transitive)

    : [tex]\forall[/tex]x,y in X, xRy [tex]\vee[/tex] yRx (completeness)

    P: xPy: [tex]\forall[/tex]x,y,z in X, xPy [tex]\wedge[/tex] yPz => xPz (transitive)

    : [tex]\forall[/tex] x,y in X, xPy =>[tex]\neg[/tex]yRx (asymmetry)

    I: xIy: [tex]\forall[/tex]x,y,z in X, xIy [tex]\wedge[/tex] yIz => xIz (transitive)

    : [tex]\forall[/tex] x,y in X, xIy => yIx (symmetry)

    Then I wrote out what P and I would be when defined as per the exercise's instruction:
    P: xPy [tex]\Leftrightarrow[/tex] xRy [tex]\wedge[/tex] [tex]\neg[/tex]yRx

    I: xRy [tex]\Leftrightarrow[/tex] xRy [tex]\wedge[/tex] yRx

    Then I tried formulating a contrapositive statement for P:
    [tex]\neg[/tex](xPy) [tex]\Leftrightarrow[/tex] [tex]\neg[/tex](xRy [tex]\wedge[/tex] [tex]\neg[/tex]yRx)

    But frankly I don't know the direction I should take to solve this problem, so stopped there and sought help! What are the steps I should be taking? How do I use the properties of completeness, transitivity, asymmetry and symmetry to show this?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted