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

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

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

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

Определения

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

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

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

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

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

Свойства

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

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

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

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

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

Аналоги

Близкой по свойствам к топологии Скотта конструкцией является категория ${\displaystyle f_{0}}$-пространств, разработанная Юрием Ершовым в 1975 году^[8] — с её помощью также может быть построена непротиворечивая модель λ-исчисления. В качестве её преимущества отмечается^[9], что категория ${\displaystyle 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.

Эта страница в последний раз была отредактирована 7 июня 2016 в 14:00.