تسجيل الدخول

تسجيل

Tarski,s Fixed Point Theorem

المؤلف:  Tarski, A.

المصدر:  "A Lattice-Theoretical Fixpoint Theorem and Its Applications." Pacific J. Math. 5

الجزء والصفحة:  285-309

9-1-2022

2022

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

		{x in R^n:a<=x<=b}" src="https://mathworld.wolfram.com/images/equations/TarskisFixedPointTheorem/Inline31.gif" style="height:15px; width:109px" />	(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.