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

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

Ещё одно из утверждений класса Шаблон:Iw — теорема Кнастера — Тарского — гарантирует существование наименьшей неподвижной точки для отображений полных решёток на себя; теорема Клини о неподвижной точке говорит о существовании таковой для отображений любых полных частично упорядоченных множеств, но её действие распространено не на любые монотонные функции, а только на функции, непрерывные в топологии Скотта. Кроме того, теорема Клини, в отличие от теоремы Кнастера — Тарского, обеспечивает способ вычисления наименьшей неподвижной точки отображения $f:P\to P$ как точной верхней грани его цепи Клини ото дна $\mathrm{\perp }$ частичного упорядоченного множества $⟨P,⊑⟩$:

$\mathrm{\perp }⊑f(\mathrm{\perp })⊑f(f(\mathrm{\perp }))⊑\cdots ⊑f^n(\mathrm{\perp })⊑\cdots$.