Editing Knaster–Tarski theorem (section)

{{Short description|Theorem in order and lattice theory}}
In the [[mathematics|mathematical]] areas of [[order theory|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 [[Monotonic function#In order theory|order-preserving (monotonic) function]] w.r.t. ≤. Then the [[set (mathematics)|set]] of [[fixed point (mathematics)|fixed point]]s of f in L forms a complete lattice under ≤.''

It was Tarski who stated the result in its most general form,<ref>{{cite journal|author=Alfred Tarski|year=1955|title=A lattice-theoretical fixpoint theorem and its applications|url=https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-lattice-theoretical-fixpoint-theorem-and-its-applications/pjm/1103044538.full|journal=Pacific Journal of Mathematics|volume=5|issue=2 |pages=285&ndash;309|doi=10.2140/pjm.1955.5.285 |doi-access=free}}</ref> and so the theorem is often known as '''Tarski's fixed-point theorem'''. Some time earlier, Knaster and Tarski established the result for the special case where ''L'' is the [[lattice (order)|lattice]] of [[subset]]s of a set, the [[power set]] lattice.<ref>{{cite journal | author=B. Knaster | title=Un théorème sur les fonctions d'ensembles | journal=[[Ann. Soc. Polon. Math.]] | year=1928 | volume=6 | pages=133&ndash;134}} With A. Tarski.</ref>

The theorem has important applications in [[formal semantics of programming languages]] and [[abstract interpretation]], as well as in [[game theory]].

A kind of converse of this theorem was proved by [[Anne C. Morel|Anne C. Davis]]: If every [[order-preserving function]] ''f'' : ''L'' → ''L'' on a lattice ''L'' has a fixed point, then ''L'' is a complete lattice.<ref>{{cite journal|author=Anne C. Davis|year=1955|title=A characterization of complete lattices|url=https://www.projecteuclid.org/journals/pacific-journal-of-mathematics/volume-5/issue-2/A-characterization-of-complete-lattices/pjm/1103044539.full|journal=Pacific Journal of Mathematics|volume=5|issue=2|pages=311&ndash;319|doi=10.2140/pjm.1955.5.311|doi-access=free|authorlink=Anne C. Morel}}</ref>