Lecture Notes on Notions for Partial Orders (COMP11120)

Notions for Partial Orders

Maximal and Minimal Elements

An element p of a
poset (P ) ,
is a maximal element of P if and only if for all Example : The binary relation R' on set S where R =
[(V v) , ,
(V , W) , (w , v) , (W , W) , (W , ),

(X , z) , (X w) , (2 y) , (y z)]
pleP have p 1 p' then
, , ,
we
p =
p

For a maximal element of a
poset there cannot be another element above it (because any
& maximal
element above has to be equal to it) v
.




Vi elements


E w W
An element Y
*

p of a
poset (P 2) ,
is a minimal element of P if and only if it is the

case that for all pleP we have p' up then p =
pl

Z
A minimal element cannot have another element below it. 8y < *
X


minimal
A poset have than maximal minimal element.
can more one or
elements




Greatest and Least Element

An element of poset (P 2) is the greatest
p a
,
element of P if and only if it is the Example : The binary relation R' on set S where R =
((V v) , ,
(V , W) , (w , v) , (W , Wh , (W , ),

z) , (X w) , (2 y) , (y z)]
case that for all plep we have p'Xp (X , , , ,




maximal
An element p of a
poset (P 2) ,
is the least element of P if and only if it is the
v
elements
Least : none as we can't

case that for all pleP we have pap compare X with 2



Y W
Greatest : none as we can't

Compare y , v, and 2
.

minimal
Z
X elements



Bitstrings Example : Consider the relation 1 over bitstrings b = mom,me of length 3 for
mo ,
m
, ma e [0 13 ,
i . .
e




b
/000 , 001, 010
,
011 , 100
,
101 , 110 , 1113

Let mom , me momims if and
only if mosmo and m
, m ! and

m2 < m2

111 masimal


011 101 110

Least : 000
001 018 100
Greatest : 111


000 minimal




Upper and Lower Bounds

Let S be a subset of a poset (P, ) Example Consider
: poset (P , 1) for ,
P = Su ,
V
,
W
, , y, 23 given below .




An element Find all the bounds for the set S
p of P is an
upper bound for S if and only if for all pleS if we have p'XP .
upper .




An element of P is lower bound S if only if for all pleS if have pXP! V S UB
p a
for and we



[x] * V, w
, Y


Note that in both cases
p doesn't have to be an element of S Y
W U
(x 2) ,
v
,
w




(w ,
x
, z] v
,
w




X 2
Sy ,
W,
v} v




V S LB

Sy V3
,
7,
y

Y
W U
sw uy , Z


X
& Y W3
,




X 2 Ey w
, , v3 none !