# Partial order relations

1. Nov 17, 2004

### Townsend

For some reason I am having a hard time dealing with partial order relations. The definition is what is killing me here. I have a digraph of a partial order relation and yet it does not appear to agree with the definition of partial order. I wish I could draw a picture of the digraph but since that would not work very well I will just do my best to explain it and why I think it is not a partial order.

R is a relation on X={a,b,c,d,f}

Starting from the bottom I have

vertex a which is related to vertex b and vertex c

Then I have vertex b related to vertex d and c related to vertex d

then I have vertex d related to vertex d and vertex f

So correct me if I am wrong but if I were to write out R as a set of ordered pairs I would have

R={(a,b), (a,c), (b,d), (c,d), (d,f), (d,e)}

If that is correct then how can this be a partial order when the definition of partial order says a relation is partial order iff R is reflexive? That relation is not reflexive since (a,a) is not an element of R (the same is true for b,c,d,e,f).

Next problem I have is how to tell if one element is comparable to another. If someone could give me a good intuitive idea of how to tell if two elements of R is comparable I would greatly appericate it.

Regards

2. Nov 18, 2004

### matt grime

it is implicit in the graph that there is a suppressed loop from each point to itself, and that the relation is reflexive, that is a<=a (usually a<a is false....)

an element is comparable (less than) to another if there is a (directed) path in the graph leading from the smaller to the larger. you are just using transitivity.

a<b, and b<d so a<d

a<c and c<d so a<d, good

a<d and d<f so a<f

a<d and d<e so a<e

now do it for b

3. Nov 18, 2004

### Townsend

Well now that certainly makes things much easier to deal with.

b<d and d<f so b<f

b<d and d<e so b<e

I appreciate your help matt grime.

Regards

Last edited: Nov 18, 2004