Kleene's fixed points — the order route to recursion

Parent: logic

"Kleene" names three different theorems; the equivalence one is kleene-theorem. The fixed-point ones are the meaning of recursion.

1. Kleene fixed-point theorem (domain theory — the semantics of recursion)

Least fixed point by climbing from

⊥ On a CPO (a partial order with a least element ⊥ and sups of ascending chains) and a Scott-continuous f, the least fixed point is lfp(f) = ⊔ₙ fⁿ(⊥) = ⊥ ⊑ f(⊥) ⊑ f²(⊥) ⊑ … — the supremum of the chain you get by iterating f from the bottom.

This is what a recursive definition means. A recursive function is the least solution of X = F(X) (its defining functional F); Kleene says that solution exists and is reached by unfolding from the undefined function ⊥ — approximation n = "the function computed after n unrollings." The Y combinator (lambda-calculus) is this fixed point made syntactic.

2. Kleene recursion (fixed-point) theorem (computability — self-reference)

Programs can see their own code

For every total computable f there is a program e with $\varphi_e = \varphi_{f(e)}$ — i.e. e computes the same function as f(e).

So a program can obtain and use its own source — the principle behind quines, compilers that bootstrap, and diagonalization arguments. A different "fixed point": not of a function on data, but of a transformation on programs.

Where it shows up (it's everywhere)

• Regular languages: Arden's rule X = A X | B ⟹ X = A*B is a least fixed point; the Kleene star is a fixed-point operator (kleene-theorem, regular-expressions).
• Bellman / RL: value iteration reaches the value function as the least fixed point of the Bellman operator, climbing from below (sequential-and-control).
• Types: inductive types = least fixed points of functors (initial algebras); coinductive = greatest fixed points (final coalgebras) (type-theory).

The punchline — two routes to the same fixed point

Recursion always means "solve X = F(X)", and there are two ways to guarantee a solution:

• Kleene / order: F monotone/continuous on a CPO → the least fixed point, reached by climbing from ⊥;
• Banach / metric: F a contraction on a complete metric space → the unique fixed point, reached by shrinking (geometric convergence).

Order vs metric; least vs unique; climb vs contract. Our convergence story is the metric half — this is its missing order-theoretic twin.