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

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

Топология Скотта — структура над полной решёткой или, в более общем случае, над полным частично упорядоченным множеством, в которой открытыми считаются верхние множества, недоступные для прямых соединений, или эквивалентно, топология, в рамках которой функции над частично упорядоченными множествами, сохраняющие точную верхнюю грань, являются непрерывными^[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$ как обладающего следующими свойствами:

1. из того, что $x \in O$ и $x \sqsubseteq y$ следует $y \in O$;
2. если $\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$-пространств является декартово замкнутой, каждый объект в ней является топологическим пространством, топология на произведении является произведением топологий сомножителей, а топология в пространстве функций оказывается топологией поточечной сходимости. Такими удобными свойствами топология Скотта не обладает, в частности, произведение топологий Скотта на полных частично упорядоченных множеств в общем случае топологией Скотта на произведении множеств не является.

См. также

• Топология Александрова

Примечания

1. ↑ Барендрегт, 1985, Теорема 1.2.6, с. 23
2. ↑ Барендрегт, 1985, Теоремы 1.2.13, 1.2.14, с. 25
3. ↑ ^{1 2} Барендрегт, 1985, с. 24
4. ↑ Скотт, 1972
5. ↑ ^{1 2} Абрамский, 1995
6. ↑ Барендрегт, 1985, Теорема 1.2.17, с. 25-26
7. ↑ Барендрегт, 1985, Теорема 1.2.16, с. 25
8. ↑ Ершов, Юрий Теория нумераций. — М.: Наука, 1977. — 416 с.
9. ↑ Барендрегт, 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. — Т. 274. — С. 97–136. — DOI:10.1007/BFb0073967
• Vickers, Steven Topology via Logic. — Cambridge: Cambridge University Press, 1989. — 206 с. — ISBN 0-521-36062-5.