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)