Partial Order Relations

Partial Orderings

Let R be a binary relation on a set A.
R is antisymmetric if for all x,y A, if xRy and yRx, then x=y.
R is a partial order relation if R is reflexive, antisymmetric and transitive.
In terms of the digraph of a binary relation R, the antisymmetry is tantamount to saying there are no arrows in opposite directions joining a pair of (different) vertices.

Example

  1. Let A={0,1,2} and R={ (0,0),(0,1),(0,2),(1,1), (1,2), (2,2)} and S={(0,0),(1,1),(2,2)} be 2 relations on A. Show
    (i)
    R is a partial order relation.
    (ii)
    S is an equivalence relation.

    Solution We choose to use digraphs to make the explanations in this case.

    (i)
    The digraph for R on the right implies
    Reflexive: loops on every vertex.
    Transitive: if you can travel from vertex v to vertex w along consecutive arrows of same direction, then there is also a single arrow pointing from v to w.
    Antisymmetric: no type of arrows.
    (ii)
    The digraph for S on the right is reflexive due to loops on every vertex, and is symmetric and transitive because no no-loop arrows exist.

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 } .
Hence partial order relation and equivalence relation can be in general regarded as ''generalisation'' of '' '' and ''='' respectively. For the same reasons, they are often denoted by

x y   if xR1y and R1 is a partial order relation,
x y   if xR2y and R2 is an equivalence relation.
Let R be a partial order relation on set A.
Two elements a,b A are {\bf comparable} if either aRb or bRa, i.e. either a b or b a.
If all elements of A are comparable with each other, then the partially ordered set A (w.r.t. R) is said to be a totally ordered set.
An element a A is a maximal element of A if b a holds for every b A whenever b and a are comparable.
An element a A is a greatest element of A if b a holds for all b A.
An element a A is a minimal element of A if a b holds for every b A whenever b and a are comparable.
An element a A is a least element of A if a b holds for all b A.

Example

  1. Let A be the set of all subsets of set { a,b,c}. Show the ''subset'' relation on A, i.e. u,v A,

    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.

Hasse Diagrams

Hasse diagrams are meant to present partial order relations in equivalent but somewhat simpler forms by removing certain deducible ''noncritical'' parts of the relations. For better motivation and understanding, we'll introduce it through the following examples.

Examples

  1. The relation in example 2 can be drawn as

    It is somewhat ''messy'' and some arrows can be derived from transitivity anyway. If we

    omit all loops,
    omit all arrows that can be inferred from transitivity,
    draw arrows without heads,
    understand that all arrows point upwards,
    then the above graph simplifies to

    This type of graph is called a Hasse diagram, it is often used to represent a partially ordered set.

  2. Let A ={ 1,2,3,9,18} and for any a,b A,

    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

  3. (a)
    Let set A be given by

    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.

    (b)
    Let a new binary relation R' on the set A given in (a) be defined by

    (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

    (a)
    Among all the elements of set A={ 3, 4, 5, 6, 10, 12 }, obviously 3 A, for instance, divides 3, 6 and 12. Hence by the definition of the relation R specified by the question we conclude (3,3), (3,6) and (3,12) are all elements of the relation R. Likewise we can show that (4,4), (4,12), (5,5), (5,10), (6,6), (6,12), (10,10), (12,12) are all elements of R. In fact we have

    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

    (b)
    The digraphs for R is already given in (a). As for R' we observe that, according to the definition of the relation R', if (x,y) (e.g. (3,6) ) is in R so will (y,x) (thus e.g. (6,3) ). Hence we can obtain R' by adding to R the symmetric pairs like (6,3), (12,3) etc. In terms of the digraph, such addition of elements is equivalent to drawing an opposite arrows to each existing (non-loop) arrows. The digraph of R' thus takes the following form

    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.