Knaster–Tarski theorem

Remarks

Proof idea for the least fixed point: let $D = \set{x : f(x) \le x}$ and $m = \inf D$. For $x \in D$, $m \le x$ gives $f(m) \le f(x) \le x$, so $f(m)$ is a lower bound of $D$ and $f(m) \le m$. Then $f(f(m)) \le f(m)$, so $f(m) \in D$ and $m \le f(m)$; hence $f(m) = m$, and every fixed point lies in $D$, so $m$ is the least one. Let $W$ be a set of fixed points with supremum $a$ in $L$. The map $f$ sends the complete lattice $\set{x \in L : a \le x}$ into itself. Its least fixed point there is the join of $W$ in $\operatorname{Fix}(f)$, and meets are handled dually. The join of a set of fixed points in $\operatorname{Fix}(f)$ need not be its join in $L$. Example: on the power set of $\N$, the map $f(S) = \set{0} \cup \set{n + 2 : n \in S}$ is monotone, and its least fixed point is the set of even numbers. Monotonicity is needed: on the two-element lattice $\set{0, 1}$, the map that swaps $0$ and $1$ has no fixed point. Completeness is needed too: on the lattice $\Z$ the monotone map $x \mapsto x + 1$ has no fixed point.

Going deeper

For a student

The theorem is the basic existence result for fixed points in order theory. In logic and computer science it gives the semantics of inductive and coinductive definitions as least and greatest fixed points. It also underlies the proof of the Cantor–Schröder–Bernstein theorem through a monotone map on a power set. When $f$ is moreover Scott-continuous, the Kleene fixed-point theorem computes the least fixed point as the supremum of the iterates $f^n(\bot)$. A converse holds: a lattice in which every monotone self-map has a fixed point is complete.