Partial order relation

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

 y   if xR1y and R1 is a partial order relation,
 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  b or  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 is a maximal element of A if  a holds for every  A whenever b and a are comparable.
An element  A is a greatest element of A if  a holds for all  A.
An element  A is a minimal element of A if  b holds for every  A whenever b and a are comparable.
An element  A is a least element of A if  b holds for all  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,

     v or uRv ,     iff  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  A, i.e.   u, we see  is not only a minimal element, it is also a least element of A. Since for any  A one has  { a,b,c}, i.e.  { a,b,c}, we see that { a,b,c} is a greatest element of A.

Author: Deepak Chahar

Leave a Reply

Your email address will not be published. Required fields are marked *