Теорема Клини о неподвижной точке

Теорема Клини о неподвижной точке — утверждение о существовании наименьшей неподвижной точки у всякого непрерывного по Скотту отображения полного частично упорядоченного множества на себя. Результат относят к Стивену Клини; используется в теории областей (англ. domain theory), теории решёток, теории графов, теории автоматов.

Ещё одно из утверждений класса теорем о неподвижной точке^[en] — теорема Кнастера — Тарского — гарантирует существование наименьшей неподвижной точки для отображений полных решёток на себя; теорема Клини о неподвижной точке говорит о существовании таковой для отображений любых полных частично упорядоченных множеств, но её действие распространено не на любые монотонные функции, а только на функции, непрерывные в топологии Скотта. Кроме того, теорема Клини, в отличие от теоремы Кнастера — Тарского, обеспечивает способ вычисления наименьшей неподвижной точки отображения $f:<!--\; :\; -->P\to <!--\; \to \; -->P$$f\colon P\to P$ как точной верхней грани его цепи Клини ото дна $\mathrm{\perp <!--\; \perp \; -->}$$\bot$ частичного упорядоченного множества $⟨<!--\; ⟨\; -->P,⊑<!--\; ⊑\; -->⟩<!--\; ⟩\; -->$$\langle P,\sqsubseteq \rangle$:

$\mathrm{\perp <!--\; \perp \; -->}⊑<!--\; ⊑\; -->f(\mathrm{\perp <!--\; \perp \; -->})⊑<!--\; ⊑\; -->f(f(\mathrm{\perp <!--\; \perp \; -->}))⊑<!--\; ⊑\; -->\cdots <!--\; \cdots \; -->⊑<!--\; ⊑\; -->f^n(\mathrm{\perp <!--\; \perp \; -->})⊑<!--\; ⊑\; -->\cdots <!--\; \cdots \; -->$$\bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots$.