The Kleene fixed-point theorem
ProvedFamousTheorems.kleene_fixed_pointThe Kleene fixed-point theorem. Let be a monotone map on a complete lattice that is Scott-continuous (preserves suprema of increasing sequences). Then its least fixed point is
It computes the least fixed point constructively as the limit of iterates from the bottom element. It is the basis of the denotational semantics of recursive programs, of dataflow analysis, and of fixed-point characterisations in logic, such as the least Herbrand model.
Formalization note. Mathlib's fixedPoints.lfp_eq_sSup_iterate; OrderHom.lfp f is the least fixed point given by Knaster–Tarski, and OmegaCompletePartialOrder.ωScottContinuous f is the continuity hypothesis.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem kleene_fixed_point {α : Type*} [CompleteLattice α] (f : α →o α) (hf : OmegaCompletePartialOrder.ωScottContinuous f) :
OrderHom.lfp f = ⨆ n : ℕ, f^[n] ⊥ := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `fixedPoints.lfp_eq_sSup_iterate`. Proof here reduces to that Mathlib result.