Partial Order Relations |
Example
Solution We choose to use digraphs to make the explanations in this case.
Note In example 1, R and S are built on
A from '' '' and ''=''
respectively by
R | = | { (x,y): x,y A, x y } , |
S | = | { (x,y): x,y A, x=y } . |
Example
u v or uRv , iff u v ,
is a partial order relation. Find a minimal element and a greatest element.
Solution It is easy to verify that '' '' is a partial ordering. Since is a subset of any u A, i.e. u, we see is not only a minimal element, it is also a least element of A. Since for any u A one has u { a,b,c}, i.e. u { a,b,c}, we see that { a,b,c} is a greatest element of A.
Examples
It is somewhat ''messy'' and some arrows can be derived from transitivity anyway. If we
This type of graph is called a Hasse diagram, it is often used to represent a partially ordered set.
a b iff a | b .
Draw the Hasse diagram of the relation.
Solution First it is easy to verify that the relation defined above is a partial ordering. The directed graph of relation is
and the Hasse diagram is
A={ 3, 4, 5, 6, 10, 12 }
and a binary relation R on A be defined by
(x, y) R iff x | y ,
i.e. (x,y) R if and only if x divides y. Give explicitly R in terms of its elements and draw the corresponding Hasse diagram.
(x, y) R' if and only if either x | y or y | x
and R'' be the transitive closure of R'. Use directed graphs to represent R, R' and R'' respectively. Which of the three relations R, R' and R'' is an equivalence relation? For the equivalence relation, give all the distinct equivalence classes.
Solution
R = { (3,3), (3,6), (3,12), (4,4), (4,12), (5,5), (5,10), (6,6), (6,12), (10,10), (12,12) } .
Hence the digraph for R is
which induces the following Hasse diagram
Since relation R'' is the transitive closure of R', we can derive R'' from R' by connecting 3 to 4 and 4 to 6 and connecting 4 to 3 and 6 to 4. We connect 3 to 4 via an direct arrow because we can travel from 3 to 12 and then from 12 to 4 all along the arrows, and we connect 4 to 3 because we can travel from 4 to 12 then to 3 all along the arrows too. Similar reasons are applicable for the arrows from 4 to 6 and 6 to 4. Hence R'' can be drawn as
Since there is no arrow from element 12 to element 3 in the digraph of R despite the existence of an arrow from 3 to 12, relation R is not symmetric hence is not an equivalence relation. Since relation R' is not transitive (because its transitive closure R'' is not the same as R' itself), relation R' is not an equivalence relation either. As for the relation R'' , it is obviously reflexive, symmetric and transitive. Hence R'' is an equivalence relation.
Since elements 3, 4, 6 and 12 are all related (connected) to each other through the arrows of the digraph R'' and none of these 4 elements are related to any other elements, they must form a single equivalence class. Hence we have
[3] = { 3, 4, 6, 12 } .
Likewise we can derive another equivalence class
[5] = { 5, 10 } .
Because any element of A is either in the equivalence class [3] or in the equivalence class [5], these two classes are all the distinct equivalence classes.
Note A partial order relation can be used to do a topological sorting, which may find applications in such as compiler construction. Interested readers may consult Epp's book for further details.