Knaster–Tarski theorem

From Wikipedia, the free encyclopedia

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

Let L be a complete lattice and let f : L → L be an order-preserving function. Then the set of fixed points of f in L is also a complete lattice.

Since complete lattices cannot be empty, the theorem in particular guarantees the existence of at least one fixed point of f, and even the existence of a least (or greatest) fixed point. In many practical cases, this is the most important implication of the theorem.

The least fixpoint of f is the least element x such that f(x) = x, or, equivalently, such that f(x) ≤ x; the dual holds for the greatest fixpoint, the greatest element x such that f(x) = x.

If f(lim x_n)=lim f(x_n) for all x_n an ascending sequence of elements of L, then the least fixpoint of f is lim fⁿ(0) where 0 is the least element of L, thus giving a more "constructive" version of the theorem. More generally, if f is monotonic, then the least fixpoint of f is the stationary limit of f^α(0), taking α over the ordinals, where f^α is defined by transfinite induction: f^α+1 = f ( f^α) and f^γ for a limit ordinal γ is the least upper bound of the f^β for all β ordinals less than γ. The dual theorem holds for the greatest fixpoint.

For example, in theoretical computer science, least fixed points of monotone functions are used to define program semantics. Often a more specialized version of the theorem is used, where L is assumed to be the lattice of all subsets of a certain set ordered by subset inclusion. This reflects the fact that in many applications only such lattices are considered. One then usually is looking for the smallest set that has the property of being a fixed point of the function f. Abstract interpretation makes ample use of the Knaster–Tarski theorem and the formulas giving the least and greatest fixpoints.

Knaster–Tarski theorem can be used for a simple proof of Cantor–Bernstein–Schroeder theorem.

A special case of this theorem (for lattices of sets) appeared in a paper of Bronislaw Knaster:

Every function, on and to the family of all subsets of a set, which is increasing under set-theoretical inclusion has at least one fixpoint.

A kind of converse of this theorem was proved by Anne C. Davis: If every order preserving function f : L → L has a fixed point, then L is a complete lattice.

[edit] References

Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics 5:2: 285–309.
Andrzej Granas and James Dugundji (2003). Fixed Point Theory. Springer-Verlag, New York. ISBN 0-387-00173-5.
M. Kolibiar, A. Legéň, T. Šalát and Š. Znám (1992). Algebra a príbuzné disciplíny. Alfa, Bratislava (in Slovak). ISBN 80-05-00721-3.
Anne C. Davis (1955). "A characterization of complete lattices". Pacific J. Math. 5: 311–319.
B. Knaster (1928). "Un théorème sur les fonctions d'ensembles". Ann. Soc. Polon. Math. 6: 133–134.
T. Forster, Logic, Induction and Sets, ISBN 0521533619