Kleene fixed-point theorem

In mathematics, the Kleene fixpoint theorem of order theory states that given any complete lattice L, and any continuous (and therefore monotone) function

${\displaystyle f:L\to L,}$

the least fixed point (lfp) of f is the least upper bound of the ascending Kleene chain of f, that is

${\displaystyle {\textrm {bot}}_{L}\leq f({\textrm {bot}}_{L})\leq f(f({\textrm {bot}}_{L}))\leq ...}$

obtained by iterating f on the bottom element of L. Expressed in a formula, the Kleene fixpoint theorem states that

${\displaystyle {\textrm {lfp}}(f)={\textrm {lub}}\left(\left\{f^{i}({\textrm {bot}}_{L})\mid i\in \mathbb {N} \right\}\right)}$

where ${\displaystyle {\textrm {lfp}}}$ denotes the least fixed point, ${\displaystyle {\textrm {lub}}}$ denotes the least upper bound, and ${\displaystyle {\textrm {bot}}_{L}}$ is the bottom element of ${\displaystyle L}$.

See also

• Other fixed-point theorems