Kleene fixed-point theorem

In the mathematical areas of order and lattice theory, the Kleene fixpoint theorem, named after American mathematician Stephen Cole Kleene, states the following:

Let L be a complete lattice, and let f : L → L be a continuous (and therefore monotone) function. Then the least fixed point of f is the supremum of the ascending Kleene chain of f.

The ascending Kleene chain of f is the chain

${\displaystyle \bot \;\leq \;f(\bot )\;\leq \;f\left(f(\bot )\right)\;\leq \;\dots \;\leq \;f^{n}(\bot )\;\leq \;\dots }$

obtained by iterating f on the least element ⊥ of L. Expressed in a formula, the theorem states that

${\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}$

where ${\displaystyle {\textrm {lfp}}}$ denotes the least fixed point.

Dually, the greatest fixed point (gfp) of f is the infimum of the descending Kleene chain of f, that is

${\displaystyle \top \;\geq \;f(\top )\;\geq \;f(f(\top ))\;\geq \;\dots \;\geq \;f^{n}(\top )\;\geq \;\dots }$

obtained by iterating f on the greatest element ⊤ of L. I.e. it is stated that

${\displaystyle {\textrm {gfp}}(f)=\inf \left(\left\{f^{n}(\top )\mid n\in \mathbb {N} \right\}\right)}$

where ${\displaystyle {\textrm {gfp}}}$ denotes the greatest fixed point.

See also

• Knaster–Tarski theorem
• Other fixed-point theorems