# Binary relations: weak order, strict partial order, equivalence

1. Oct 27, 2009

### imlearning

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: $$\forall$$x,y,z in X, xRy $$\wedge$$ yRz => xRz (transitive)

: $$\forall$$x,y in X, xRy $$\vee$$ yRx (completeness)

P: xPy: $$\forall$$x,y,z in X, xPy $$\wedge$$ yPz => xPz (transitive)

: $$\forall$$ x,y in X, xPy =>$$\neg$$yRx (asymmetry)

I: xIy: $$\forall$$x,y,z in X, xIy $$\wedge$$ yIz => xIz (transitive)

: $$\forall$$ 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 $$\Leftrightarrow$$ xRy $$\wedge$$ $$\neg$$yRx

I: xRy $$\Leftrightarrow$$ xRy $$\wedge$$ yRx

Then I tried formulating a contrapositive statement for P:
$$\neg$$(xPy) $$\Leftrightarrow$$ $$\neg$$(xRy $$\wedge$$ $$\neg$$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?