Непрерывность по Скотту (Uyhjyjdfukvm, hk Vtkmmr)

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

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

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

Определения

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

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

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

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

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

Свойства

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

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

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

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

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

Аналоги

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

Примечания

↑ Барендрегт, 1985, Теорема 1.2.6, с. 23.
↑ Барендрегт, 1985, Теоремы 1.2.13, 1.2.14, с. 25.
↑ ¹ ² Барендрегт, 1985, с. 24.
↑ Скотт, 1972.
↑ ¹ ² Абрамский, 1995.
↑ Барендрегт, 1985, Теорема 1.2.17, с. 25-26.
↑ Барендрегт, 1985, Теорема 1.2.16, с. 25.
↑ Ершов, Юрий. Теория нумераций. — М.: Наука, 1977. — 416 с.
↑ Барендрегт, 1985, с. 22.

Литература

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.

[_70e62b4054419d53-1] Барендрегт, 1985, Теорема 1.2.6, с. 23.

[_fb27d84e33add639-2] Барендрегт, 1985, Теоремы 1.2.13, 1.2.14, с. 25.

[_1bcab1dba0548bb6-3] ¹ ² Барендрегт, 1985, с. 24.

[_4a18a55067c4f5a3-4] Скотт, 1972.

[_ef9a5512ef1f5e14-5] ¹ ² Абрамский, 1995.

[_faee7f58511fb55c-6] Барендрегт, 1985, Теорема 1.2.17, с. 25-26.

[_5b631f38ff851c10-7] Барендрегт, 1985, Теорема 1.2.16, с. 25.

[8] Ершов, Юрий. Теория нумераций. — М.: Наука, 1977. — 416 с.

[_1bcab1dba0548bb0-9] Барендрегт, 1985, с. 22.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]