nLab Kleene's fixed point theorem

Redirected from "Kleene's fixed-point theorem".
Contents

Contents

Idea

Kleene’s fixed point theorem theorem constructs least fixed points of endofunctions on posets by iterating them. Adámek's fixed point theorem generalizes this to constructing initial algebras.

Construction

Theorem

Let f:PPf : P \to P be a monotone function on a poset PP. If PP has a least element \bot and joins of increasing sequences, and if ff preserves joins of increasing sequences, then a least fixed point of ff can be constructed as the join of the increasing sequence:

f()f 2(). \bot \;\leq\; f(\bot) \;\leq\; f^2(\bot) \;\leq\; \cdots \,.

References

Named after Stephen Kleene.

See also:

Last revised on November 29, 2023 at 16:41:41. See the history of this page for a list of all contributions to it.