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 !
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 !
