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

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

Формулировка

Любое непрерывное по Скотту отображение $f$ полного частично упорядоченного множества $(M,\leqslant )$ в себя имеет единственную наименьшую неподвижную точку.

Пояснения

Непрерывными по Скотту отображениями полных частично упорядоченных множеств считаются отображения, образ точной верхней грани любой неубывающей последовательности $a_{1},...,a_{n},...$ элементов множества $M_{1}$ при которых равен точной верхней грани последовательности образов $f(a_{1}),...,f(a_{n}),...$ , то есть справедливо равенство $f(\sup a_{n})=\sup f(a_{n})$ .

См. также

Теорема Кнастера — Тарского

Литература

Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — С. 85-89. — ISBN 5-7038-2886-4.
Sakharov, Alex. "Kleene's Recursion Theorem" From MathWorld--A Wolfram Web Resource (англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.