Kleene fixed-point theorem

The Kleene fixed-point theorem states that every Scott-continuous function on a pointed directed-complete partial order has a least fixed point, given by the supremum of its iterates from the least element.

Directed-complete partial order: A partially ordered set in which every directed subset has a supremum. The theorem's domain must contain suprema for the increasing sequence of iterates.
Partial order: A reflexive, antisymmetric, transitive relation on a set. The theorem compares approximations using an order rather than numerical distance.
Denotational semantics: An approach to programming-language semantics that assigns mathematical meanings to programs. Recursive program meanings are often defined as least fixed points of semantic functions.
Banach fixed-point theorem: A theorem guaranteeing a unique fixed point for a contraction on a complete metric space. It obtains fixed points through metric contraction, rather than order and directed continuity.
Scott-continuous function: A monotone function on a directed-complete partial order that preserves suprema of directed subsets. Preservation of the iterate chain's supremum makes that supremum a fixed point.
Directed set: A nonempty partially ordered set in which every pair of elements has a common upper bound. Directedness ensures the successive approximations form a set with a supremum.
Recursive definition: A definition that specifies an object in terms of simpler instances of itself. The theorem gives a precise interpretation when recursive definitions induce continuous functions.
Tarski fixed-point theorem: A theorem stating that a monotone function on a complete lattice has a complete lattice of fixed points. It requires a complete lattice and monotonicity, while Kleene's theorem uses directed completeness and continuity.
Least element: An element below every element of a partially ordered set. Iteration begins here, ensuring the resulting fixed point is least.
Monotone function: A function between ordered sets that preserves their order relations. Scott continuity includes monotonicity, which makes the iterates increase from the least element.

Linked from 2 pages

S-m-n theoremRelated: Parameterization is a key ingredient in obtaining fixed points for program transformations.