Information Technology Reference
In-Depth Information
3. If (
X
,
) is a complete lattice, then so is (
X
,
), where
is the inverse relation
of
, i.e.
x
y
iff
y
x
for any elements
x
,
y
∈
X
.
Example 2.3
The set
X
={
1, 2, 3, 5, 6, 10, 15, 30
}
of all divisors of 30, partially
ordered by divisibility, constitutes a complete lattice.
Example 2.4
The set of all natural numbers
N
, with the usual relation
≤
on natural
numbers, forms a lattice which is not a complete lattice.
Example 2.5
Let
X
be any set. Its powerset
P
(
X
)
={
Y
|
Y
ↆ
X
}
with the
inclusion relation
forms a complete lattice whose join and meet are set union and
intersection, respectively.
Given a function
f
:
X
ↆ
ₒ
Y
and a set
Z
ↆ
X
, we write
f
(
Z
) for the image of
Z
under
f
, i.e. the set
{
f
(
z
)
|
z
∈
Z
}
. Given a partially ordered set
X
and a function
f
:
X
ₒ
X
, we say
x
∈
X
is a
fixed point
(resp.
prefixed point
,
postfixed point
)of
f
if
x
=
f
(
x
) (resp.
f
(
x
)
x
,
x
f
(
x
)).
Definition 2.2
Let
X
and
Y
be partially ordered sets. A function
f
:
X
ₒ
Y
is
called
monotone
,if
x
y
implies
f
(
x
)
f
(
y
) for all
x
,
y
∈
X
.
Theorem 2.1 (Knaster-Tarski Fixed-Point Theorem)
If X is a complete lattice,
then every monotone function f from X to X has a fixed point. The least of these is
given by
=
{
∈
|
}
lfp
(
f
)
x
X
f
(
x
)
x
,
and the greatest by
gfp
(
f
)
=
{
x
∈
X
|
x
f
(
x
)
}
.
Let
X
={
and
x
∗
=
X
. For each
x
X
we have
Proof
x
∈
X
|
f
(
x
)
x
}
∈
x
∗
x
and then by monotonicity
f
(
x
∗
)
f
(
x
)
x
. Taking the infimum over
x
we get,
f
(
x
∗
)
f
(
X
)
X
=
x
∗
, thus
x
∗
∈
X
and is the least prefixed
point. On the other hand,
x
∈
X
implies
f
(
x
)
∈
X
by monotonicity. Applying
this to
x
∗
yields
f
(
x
∗
)
f
(
x
∗
). Therefore, we obtain that
x
∗
=
f
(
x
∗
). In fact,
x
∗
is the least fixed point because we have just shown that it is
the least prefixed point.
The case for the greatest fixed point is dual and thus omitted.
X
which implies
x
∗
∈
Definition 2.3
Given a complete lattice
X
, the function
f
:
X
ₒ
X
is
continuous
if it preserves increasing chains, i.e. for all sequences
x
0
x
1
...
we have
f
(
n
≥
x
n
)
=
f
(
x
n
)
.
0
n
≥
0
Dually,
f
is
cocontinuous
if it preserves decreasing chains.
Notice that both continuity and cocontinuity imply monotonicity. For example,
if
f
is continuous and
x
y
, then from the increasing sequence
x
y
y
...
Search WWH ::
Custom Search