Kleene fixed-point theorem
Theorem in order theory
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
(
L
,
⊑
)
{\displaystyle (L,\sqsubseteq )}
is a directed-complete partial order (dcpo) with a least element, and let
f
:
L
→
L
{\displaystyle f:L\to L}
be a Scott-continuous (and therefore monotone) function. Then
f
{\displaystyle f}
has a least fixed point, which is the supremum of the ascending Kleene chain of
f
.
{\displaystyle f.}
The ascending Kleene chain of f is the chain
⊥
⊑
f
(
⊥
)
⊑
f
(
f
(
⊥
)
)
⊑
⋯
⊑
f
n
(
⊥
)
⊑
⋯
{\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }
obtained by iterating f on the least element ⊥ of L. Expressed in a formula, the theorem states that
lfp
(
f
)
=
sup
(
{
f
n
(
⊥
)
∣
n
∈
N
}
)
{\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}
where
lfp
{\displaystyle {\textrm {lfp}}}
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. Moreover, the Kleene fixed-point theorem can be extended to monotone functions using transfinite iterations.
Proof
Source:
We first have to show that the ascending Kleene chain of
f
{\displaystyle f}
exists in
L
{\displaystyle L}
. To show that, we prove the following:
Lemma. If
L
{\displaystyle L}
is a dcpo with a least element, and
f
:
L
→
L
{\displaystyle f:L\to L}
is Scott-continuous, then
f
n
(
⊥
)
⊑
f
n
+
1
(
⊥
)
,
n
∈
N
0
{\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}}
Proof. We use induction:
Assume n = 0.
Begin with the source’s own compact description: “Kleene fixed-point theorem” is theorem in order theory. The dossier treats that line as a proposition to test through Kleene, fixed-point and theorem, not as a finished interpretation.
Why this record matters
The phrase “theorem in order theory” supplies a clear boundary for inquiry. It also exposes the unanswered questions: who defined that boundary, when it became stable and which sources sit outside it.
Vocabulary and entity names are the principal evidence signals here, because they determine the precision of every later search. The source revision retrieved here is dated May 10, 2025. The linked authority identifier is Q3527263. None of the 0 selected statements returned an explicit reference.
Overview language is designed for orientation and should not be treated as a substitute for the evidence cited beneath it. The source lead contains qualifying language; that uncertainty should survive quotation, summary and reuse. Authority statements aid reconciliation but still require their own references, qualifiers and ranks to be checked.
How to read it
Use the entry as an orientation point, then follow its citations and revision history. Names, dates and institutional relationships should be checked against the original record.
- Subject orientation
- Search vocabulary
- Locating named sources
The closest primary source, responsible institution and strongest cited specialist reference.
Three-step research path
- Establish the record: confirm the title “Kleene fixed-point theorem”, its source revision and the description used here.
- Expand the search: follow Kleene fixed-point theorem primary sources, Kleene fixed-point theorem archive and Kleene research across catalogues and specialist indexes.
- Test the account: compare the strongest cited source with the responsible institution’s current record and note any disagreement.
Questions for further research
- Which source most directly establishes the central claim about “Kleene fixed-point theorem”?
- Which cited source is closest to the event, object or claim?
- What terminology or title could unlock a more precise catalogue search?
Search terms from this dossier
This entry incorporates text from “Kleene fixed-point theorem” on English Wikipedia. Contributors are listed in the page history. Text is available under the Creative Commons Attribution-ShareAlike 4.0 License. Selected authority identifiers and statements are retrieved from Wikidata under CC0; their references and qualifiers remain part of the verification path.