07 Partial Order

partial order
Partially Ordered Set (Poset)

A relation R on a set A is called a
partial ordering or partial order if it
is reflexive, anti-symmetric, and
transitive. Set A together with a
partial ordering R is called a
partially ordered set, and is
denoted by (A, R)
Partial ordering examples
Example: Consider the “less than
or equal” relation 
(defined by {(x, y) | x  y}
Is  a partial ordering on the set
of integers?
 is reflexive, because a a for
every integer a.
 is antisymmetric, because
if
(x  y) ( y x) then x=y
 is transitive, because if x  y and
y  z, then
x  z.
Consequently, (Z,  ) is a partially
ordered set
Let n be any integer and let R be
the relation of divisibility on Dn set
of all (+ve) integer divisors of n.
R  |, i.e. (x,y)R  x|y
Then R is an partial order on Dn

Convention : whenever (A; R) is
a partially ordered set we write
relation R
as  i.e (A; )
Comparable/Incomparable
The elements a and c of a poset
(S,  ) are called comparable if
either a  c or c  a. When a
and c are elements of S such that
neither a  c nor c  a, a and c
are called incomparable.
Example:
Consider the power set of {a, c, d}
and the subset relation.
(P({a,c,d}),  )
{a,c} {a,d}
So, {a,c} and {a,d} are
incomparable
Linearly Ordered set
 Forsome purposes, we require all
elements of a set to be comparable.
 For example, if we want to write a
dictionary, we need to define an
order on all English words
(alphabetic order).
 Definition: If (S, ) is a poset
and every two elements of S
are comparable, S is called
linearly ordered set, and  is
called a total order or linear
order. A totally ordered set is
also called a chain.
Hasse Diagrams
Given any partial order relation
defined on a finite set, it is possible
to draw the directed graph so that
all of directions are pointing
upward.
This makes it possible to associate a
somewhat simpler graph, called a
Hasse diagram, with a partial order
relation defined on a finite set
Definition(Hasse diagram):
A Hasse diagram of a partial order
whose digraph is known is a graph
which does not have loops and arcs
implied by the transitivity. Further, it
is drawn so that all arcs point
upward eliminating arrowheads.
Eliminate the loops at all the
vertices.
Eliminate all arcs whose
existence is implied by the
transitive property.
remove the directions on the arcs.

Hasse Diagrams
Consider the digraph for a finite poset
({u,v,w,z},R)
z
It is simple to check that R represented
w
through digraph is a partial order.
u
z
z z
z
w
w w
w
v
Hasse v
v v
diagram u
u u
u
10: Draw digraph of relation of divisibility
on D12 hence find hasse diagram of
(D12 , |)
Solution :D12= {1,2 ,3, 4, 6, 12} If R is Relation

of divisibility then
R={(1,1), (1,2), (1,3), (1,4), (1,6), (1,12), (2,2), (2,4),
(2,6),(2,12),(3,3),(3,6),(3,12),(4,4),(4,12),(6,6),(6,12),
(12,12) }
R=={(1,1), (1,2), (1,3), (1,4),
(1,6),
12
(1,12),(2,2),(2,4),(2,6),(2,12),
(3,3),(3,6),(3,12),
(4,4),(4,12),(6,6),(6,12),
(12,12) }
4
6
Digraph of (D12 ,|)

12
Now delete loops

12
Now mark transitive edges and delete them

12
Delete all edges which are consequence of

transitivity
Subset C A , then C is a
partially ordered set with the
partial order of A and elements of
partial order are R(CC), where
R is the partial order. (prove that)
Greatest element
Definition : If (A, ) is a partially

ordered set and C A, an element
cC is called greatest element of C
if x c. xC
least element

dC is called least element of C if
d≤x, xC
Maximal element

cC is called maximal element of
C if there does not exist any other
xC such that c  x.
Definition : If (A,  ) is a partially
wC is called minimal element of C
if there does not exist any other xC
such that x  w .
Maximal and minimal elements of a

subset C of A should belong to the subset C.
There can be several Maximal and minimal

elements for a subset C .
Greatest element

cC is called greatest element of C
if t x c. xC
least element

dC is called least element of C if
d≤x, xC
wA is called lower bound of C if
w  x for all xC .

cA is called upper bound of C if
c  x for all xC .
Definition : C A & If set of lower
bounds of C , has greatest element
then that element is called is called
greatest lower bound of C in
partially ordered set (A,  )
Definition : C A & If set of upper
bounds of C , has least element then
that element is called is called least
upper bound of C in partially
ordered set (A,  )
Q.2 Define the relation Q
on real functions of one
variable defined on Real
number R
by f Q g if f(x)≤g(x)
xR , then Q is a partial
order but not a total
order.
3 If R is a partial ordering on a
set S then for n2, there can
not exist a sequence s1 ,s2 ……….
sm of distinct elements of S
such that s1 Rs2 Rs3 R ………sm R s1
Solution : trivial
8 How many total ordering
are there on a set with n
elements?
Answer : factorial n (why?)

12 Inverse of a relation R
If R is a relation on A , then
R-1 ={ (y,x) : (x,y)  R }
(i)If R is a partial order on set A,
then R-1 is a partial order on A.
(ii) If R is a linear order on set A,
then R-1 is a linear order on A.
(iii) R is a linear order on set A
then AA = RR-1
There can be several lower bounds
and upper bounds for a subset C .
As greatest and least element are unique if

they exist ,least upper bound and greatest
lower bound for a subset C of A are
unique if they exist.
Well ordered set : A total order on a set A
is called a well order if every subset C of A
contains a least element.
As is evident from hasse diagram of a finite

totally ordered set that any finite totally ordered
set is a well ordered set.
(N,≤) is well ordered set.
(Z,≤) is not well ordered set as set of

negative integers does not have a
least element.
(Q+ ,≤) is not well ordered set as there

exist subsets of (Q+ ,≤) that do not
have a least element.(which subsets)
Examples of Maximal/Minimal Elements
Example : On set {2, 3,4, 6, 8, 12, 18} for
hasse diagram find maximal & element.
8
12 18
Maximal elements: 8, 12, 18
4 6
Minimal elements: 2, 3
2 3
Example : Find the maximal
and minimal element is there a
greatest and least element?
How many elements are there
in partial order R
c
s r
a d
l
Example : Write the set of partial order R on
set A = {z,w,q,m,c,a} whose hasse
diagram is drawn in fig. Which elements are
maximal and minimal for sub set C if
(i) C=A (ii) C = { q,c,a}
(iii) C={w,q,m,a}
c
a
z w
c
a R={(a,a,),(c,c),(z,z),(w,w),(m,m),(q,q),
( z,q), (w,q),(q,m),(m,a),(m,c),
m
(z,m),(z,a),(z,c),(w,m),(w,c),(w,a),(q,a),(q,c)}
an element d of A in (A; ) is called

q minimal That is, d is minimal if there does
not exist any other element x such that
x d. Hence minimal element are z & w
z w
Definition : If (A,  ) is a partially ordered set and an element lA is

called maximal element of A if there does not exist any other xA
such that l  x. Hence maximal element are a & c
(ii) C = { q,c,a}
a c
m (iii) C={w,q,m,a}
Solution (iii) Maximal

q
elements a
minimal element w
z w

07 Partial Order

Uploaded by

Copyright:

Available Formats

07 Partial Order

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

07 Partial Order

Uploaded by

Copyright:

Available Formats

partial order

Partially Ordered Set (Poset)

R  |, i.e. (x,y)R  x|y

Then R is an partial order on Dn

remove the directions on the arcs.

Solution :D12= {1,2 ,3, 4, 6, 12} If R is Relation

Digraph of (D12 ,|)

Now delete loops

Now mark transitive edges and delete them

Delete all edges which are consequence of

Definition : If (A, ) is a partially

Definition : If (A, ) is a partially

Definition : If (A, ) is a partially

Maximal and minimal elements of a

There can be several Maximal and minimal

Definition : If (A, ) is a partially

Definition : If (A, ) is a partially

Definition : If (A,  ) is a partially

Answer : factorial n (why?)

As greatest and least element are unique if

As is evident from hasse diagram of a finite

(Z,≤) is not well ordered set as set of

(Q+ ,≤) is not well ordered set as there

an element d of A in (A; ) is called

Definition : If (A,  ) is a partially ordered set and an element lA is

Solution (iii) Maximal

You might also like