Re: Tarski's fixed point lattice theorem


"William Elliot" <marsh@xxxxxxxxxxxxxxxxxx> wrote:

Below in part is a converse to Tarski's fixed point lattice thereom
complete lattice S, increasing f:S -> S ==> f has fixed point

Let S be a lattice and assume
for all increasing f:S -> S, f has a fixed point.

How to show S has a top, maximum element?
Counter examples also acceptable. ;-)

If L is a complete lattice and k:L->L is a monotonic function, then there
exist a fixed point for k.

If X={x in L | x<=k(x)}, such a set is nonempty because 0 is in X. Let z =
sup X, since z>=x for all x in X, then (from the monotonicity of k) it
follows that k(z)<=k(x) and so k(z)>=x for all x in X. Then z = sup X <=
k(z).
Other way, from z<=k(z) follows k(z)<=k(k(z)) and so k(z) is in X. Since z
is a majorant (I don't know the exact term, sorry) of all elements in X, we
can conclude that k(z)<=z. We have proved that k(z)=z.


.

Quantcast