Kleene fixed-point theorem
From Wikipedia, the free encyclopedia
This article is about Kleene's fixed-point theorem in lattice theory. For the fixed-point theorem in computability theory, see Kleene's recursion theorem.
In the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following:
- Kleene Fixed-Point Theorem. Suppose is a directed-complete partial order (dcpo) with a least element, and let be a Scott-continuous (and therefore monotone) function. Then has a least fixed point, which is the supremum of the ascending Kleene chain of
The ascending Kleene chain of f is the chain
obtained by iterating f on the least element ⊥ of L. Expressed in a formula, the theorem states that
where denotes the least fixed point.
Although Tarski's fixed point theorem does not consider how fixed points can be computed by iterating f from some seed (also, it pertains to monotone functions on complete lattices), this result is often attributed to Alfred Tarski who proves it for additive functions [1] Moreover, Kleene Fixed-Point Theorem can be extended to monotone functions using transfinite iterations.[2]