Information Technology Reference
In-Depth Information
1
2
2
3
0
0
1
(a)
(b)
Fig. 2.1
Partially ordered sets
an arrow that goes upward from
x
to
y
if
y
is an immediate successor of
x
, i.e.
x
y
and there is no
z
with
x
by removing elements
(
x
,
x
) for all
x
. For instance, the partially ordered set given in the above example can
be depicted by the diagram in Fig.
2.1
a.
If
Y
has an upper bound that is also an element of
Y
, then it is said to be the
greatest element
in
Y
. We can dually define the
least element
. In the presence of a
least element we speak of a
pointed
partially ordered set. If the set of upper bounds
z
y
, where
is obtained from
for
Y
has a least element
x
, then
x
is called the
supremum
or
join
of
Y
, written
Y
.
Dually we have
infimum
or
meet
and write
Y
. Note that a subset might not have
supremum even if it has upper bounds; so is the case for infimum.
={
}
Example 2.2
Consider the set
X
0, 1, 2, 3
with the binary relation
defined
=
Id
X
∪{
}
by
(0, 2), (0, 3), (1, 2), (1, 3)
. It forms the partially ordered set depicted
in Fig.
2.1
b. The subset
has two upper bounds, namely 2 and 3, but it has no
supremum because the two upper bounds are incomparable in the sense that neither
2
{
0, 1
}
2 holds.
We call
X
a
lattice
, if suprema and infima exist for all the subsets of
X
with two
elements, i.e. if
{
x
,
y
}
3 nor 3
exist for any
x
,
y
∈
X
. We call
X
a
complete
lattice
if suprema and infima exist for all the subsets of
X
.
and
{
x
,
y
}
Remark 2.1
A few characteristics of complete lattices are worth mentioning because
they are useful in many applications.
1. It suffices to define complete lattices in terms of either suprema or infima only.
For example, a candidate definition is to say
X
is a complete lattice if suprema
exist for all subsets of
X
. Then the infimum of any subset
Y
also exists because
Y
=
{
x
∈
X
|∀
y
∈
Y
:
x
y
}
2. Let
X
be a complete lattice. By definition,
X
itself has a supremum, which is
the greatest element of
X
, written
, and an infimum, which is the least element
of
X
, written
↥
. It can be checked that the empty set
∅
has supremum
↥
and
infimum
.
Search WWH ::
Custom Search