Tarski's Fixed Point Theorem

Let  be any complete lattice. Suppose  is monotone increasing (or isotone), i.e., for all ,  implies . Then the set of all fixed points of  is a complete lattice with respect to  (Tarski 1955)

Consequently,  has a greatest fixed point  and a least fixed point . Moreover, for all ,  implies , whereas  implies .

Consider three examples:

1. Let  satisfy , where  is the usual order of real numbers. Since the closed interval  is a complete lattice, every monotone increasing map  has a greatest fixed point and a least fixed point. Note that  need not be continuous here.

2. For  declare  to mean that , ,  (coordinatewise order). Let  satisfy . Then the set

			(1)
			(2)

is a complete lattice (with respect to the coordinatewise order). Hence every monotone increasing map  has a greatest fixed point and a least fixed point.

3. Let  and  be injections. Then there is a bijection  (Schröder-Bernstein theorem), which can be constructed as follows. The power set of  ordered by set inclusion, , is a complete lattice. Since the map ,

(3)

is monotone increasing, it has a fixed point . As , a bijection  can be defined just by setting

(4)

REFERENCES:

Tarski, A. "A Lattice-Theoretical Fixpoint Theorem and Its Applications." Pacific J. Math. 5, 285-309, 1955.