Encyclopedia > Knaster-Tarski theorem

  Article Content

Knaster-Tarski theorem

In mathematics, the Knaster-Tarski theorem, named after Bronislaw Knaster[?] and Alfred Tarski, states the following:

Let L be a complete lattice and let f : L -> L be a monotonic 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.

For example, in mathematical logic least fixed points of functions on sets of formulas are used to compute the semantics of a logic program. Sometimes 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.


  • Alfred Tarski: A lattice-theoretical theorem and its applications. Pacific Journal of Mathematics, vol. 5 (1955), pp 285-309.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article

... (POEA)]] [2] (http://www.pan-uk.org/pestnews/actives/glyphosa.htm). These components are responsible for acute toxicity to humans such as ey ...