How to Prove a Relation is Partially Ordered?

[StIgM@]

Hello,

I am trying to find out how you can prove that a relation is partially ordered.
I know that it must be reflexive, antisymmetric and transitive but if a relation is given how do you write that it should be partially ordered?

For example I have the relation R: X\leftrightarrowX
I want to check if it is partially ordered...
\forallx1:X | x1 |---> x1 \in X \wedge reflexive
\forallx2:ran X | x1 |---> x2 \in X \wedge x1\neqx2 \Rightarrow x2 |---> x1 \notin X antisymmetricbut how do you show transitivity?

Thanks

 

[Mark44]

Hello,

I am trying to find out how you can prove that a relation is partially ordered.
I know that it must be reflexive, antisymmetric and transitive but if a relation is given how do you write that it should be partially ordered?

I'm not sure I understand your question, but if the relation is reflexive, antisymmetric, and transitive, then it is partially ordered.

For example I have the relation R: X\leftrightarrowX
I want to check if it is partially ordered...
\forallx1:X | x1 |---> x1 \in X \wedge reflexive
\forallx2:ran X | x1 |---> x2 \in X \wedge x1\neqx2 \Rightarrow x2 |---> x1 \notin X antisymmetric

What is the relation? You haven't given a definition of the relation, so how can you show that it is reflexive, antisymmetric, and transitive?

but how do you show transitivity?

Thanks

 

[StIgM@]

For example it is given the relation R:X<--->X
So, we want to check if it is partially ordered.

The only checks that we have to write are:

\forAll x:X | x-->x \in R
\forAll x,y:X | x--->y \in R \and x\notEqual y \isthecasethat y--->y \notIn R
\forAll x,y,z:X | x--->y \in R \and y--->z \in R \implies x--->z \in R

Are these correct?

 

[Mark44]

For example it is given the relation R:X<--->X

This doesn't define the relation. It just says that R is a relation between some set X and itself. It doesn't say how a given x value is mapped to the one it's related to.

Does a value x in X get mapped to itself? In that case the relation would be "=".

I think you are missing an important piece here.

So, we want to check if it is partially ordered.

The only checks that we have to write are:

\forAll x:X | x-->x \in R
\forAll x,y:X | x--->y \in R \and x\notEqual y \isthecasethat y--->y \notIn R
\forAll x,y,z:X | x--->y \in R \and y--->z \in R \implies x--->z \in R

Are these correct?