Partial order relations

  • Thread starter Townsend
  • Start date
  • #1
221
0
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
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
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
221
0
matt grime said:
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

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:

Related Threads on Partial order relations

Replies
0
Views
2K
Replies
2
Views
5K
  • Last Post
Replies
5
Views
2K
Replies
5
Views
978
  • Last Post
Replies
1
Views
1K
Replies
2
Views
1K
Replies
3
Views
4K
Replies
5
Views
41K
Replies
10
Views
4K
Top