Непрерывность по Скотту

Непрерывность по Скотту — свойство функций над частично упорядоченными множествами, выражающееся в сохранении точной верхней грани относительно отношения частичного порядка.

Топология Скотта — структура над полной решёткой или, в более общем случае, над полным частично упорядоченным множеством, в которой открытыми считаются верхние множества, недоступные для прямых соединений, или эквивалентно, топология, в рамках которой функции над частично упорядоченными множествами, сохраняющие точную верхнюю грань, являются непрерывными.

Понятия были разработаны в 1970-е годы Даной Скоттом, благодаря им построены первая непротиворечивая модель бестипового λ-исчисления и денотационная семантика. В частности, функции аппликации и каррирования являются непрерывными по Скотту.

Определения

Если $P$ и $Q$ — частично упорядоченные множества, то функция $f\colon P\to Q$ между ними является непрерывной по Скотту если для любого направленного подмножества $D\subseteq P$ существует точная верхняя грань его образа $\sup f(D)$, притом выполнено следующее условие: $\sup f(D)=f(\sup D)$.

Топология Скотта на полном частично упорядоченном множестве $\langle D,\sqsubseteq \rangle$ вводится определением открытого множества $O$ как обладающего следующими свойствами:

1. из того, что $x\in O$ и $x\sqsubseteq y$ следует $y\in O$;
2. если $\bigsqcup X\in O$, где $X\subseteq D$ и $X$ направленно, то $X\cap O\neq \varnothing$.

Топология Скотта была впервые введена для полных решёток, впоследствии была обобщена до полных частично упорядоченных множеств.

Категория, объектами которой являются полные частично упорядоченные множества, а морфизмами — непрерывные по Скотту отображения, обозначается ${\mathsf {CPO}}$.

Свойства

Функции, непрерывные по Скотту, всегда монотонны относительно отношения частичного порядка.

Подмножество частично упорядоченного множество замкнуто в топологии Скотта тогда и только тогда, когда оно является нижним множеством и включает точные верхние грани всех своих подмножеств.

Полное частично упорядоченное множество, наделённое топологией Скотта, всегда является T₀-пространством, а хаусдорфовым — тогда и только тогда, когда отношение порядка тривиально.

Для любой непрерывной по Скотту функции, отображающей полное частично упорядоченное множество на себя, выполнена теорема Клини, согласно которой каждое такое отображение обладает единственной наименьшей неподвижной точкой. Кроме того, отображение $\mathbf {Fix}$, определённое на множестве непрерывных по Скотту функций $f\colon D\to D$ и возвращающее для каждой функции значение её неподвижной точки ($\mathbf {Fix} (f)=x\Leftrightarrow f(x)=x$), само является непрерывным по Скотту.

Категория ${\mathsf {CPO}}$ является декартово замкнутой.

Аналоги

Близкой по свойствам к топологии Скотта конструкцией является категория $f_{0}$-пространств, разработанная Юрием Ершовым в 1975 году — с её помощью также может быть построена непротиворечивая модель λ-исчисления. В качестве её преимущества отмечается, что категория $f_{0}$-пространств является декартово замкнутой, каждый объект в ней является топологическим пространством, топология на произведении является произведением топологий сомножителей, а топология в пространстве функций оказывается топологией поточечной сходимости. Такими удобными свойствами топология Скотта не обладает, в частности, произведение топологий Скотта на полных частично упорядоченных множеств в общем случае топологией Скотта на произведении множеств не является.

Литература

• Abramsky, Samson and Jung, Achim. Domain Theory // Semantic Structures. — Handbook of Logic in Computer Science. — Oxford: Oxford University Press, 1995. — Т. 3. — 512 с. — ISBN 978-0198537625.
• Барендрегт, Хенк. Ламбда-исчисление. Его синтаксис и семантика = The Lambda Calculus. Its syntax and semantics (рус.). — М.: Мир, 1985. — 606 с. — 4800 экз.
• Scott, Dana. Continous Lattices (англ.) // Lecture Notes in Mathematics. — 1972. — Vol. 274. — P. 97–136. — doi:10.1007/BFb0073967.
• Vickers, Steven. Topology via Logic. — Cambridge: Cambridge University Press, 1989. — 206 с. — ISBN 0-521-36062-5.