# 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. 