Binary relations: weak order, strict partial order, equivalence

[imlearning]

Homework Statement

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.

Homework 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.

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?

 

[mighty2000]

thank you for reaching out for help with this exercise. It seems like you have a good understanding of the definitions of weak order, strictly partial order, and equivalence. To show that P and I are strictly partial and equivalent, we need to prove that they satisfy the properties of transitivity and asymmetry for strictly partial order, and transitivity and symmetry for equivalence.

Let's start with P. We can use the definition of weak order to show that it satisfies transitivity. Since R is a weak order, we know that for any x, y, and z in X, if xRy and yRz, then xRz. Now, let's consider the definition of P. If xPy and yPz, that means xRy and yRz, but also that yRx and zRy. By the transitive property of R, we know that xRz and zRx. However, since P is defined as xPy if and only if xRy and not yRx, we know that zRx cannot be true. Therefore, xPy and yPz imply xPz, and P satisfies transitivity.

To show that P is asymmetric, we can use the definition of P again. If xPy, that means xRy and not yRx. Therefore, if yPx were true, that would mean yRx and not xRy, which contradicts the definition of P. Therefore, P is asymmetric.

Similarly, we can use the definitions of I and weak order to show that I satisfies transitivity and symmetry, and is therefore an equivalence relation.

I hope this helps guide you in the right direction. Remember to always start with the definitions and use them to guide your proofs. Good luck!