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

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

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

Понятия были разработаны в 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}}$.

Свойства

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

Функция между полными частично упорядоченными множествами $f\colon D\to D^{\prime }$ тогда и только тогда является непрерывной по Скотту

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

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

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

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

См. также

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

Литература

• 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..