Русская Википедия:Непрерывность по Скотту
Непрерывность по Скотту — свойство функций над частично упорядоченными множествами, выражающееся в сохранении точной верхней грани относительно отношения частичного порядка.
Топология Скотта — структура над полной решёткой или, в более общем случае, над полным частично упорядоченным множеством, в которой открытыми считаются верхние множества, недоступные для прямых соединений, или эквивалентно, топология, в рамках которой функции над частично упорядоченными множествами, сохраняющие точную верхнюю грань, являются непрерывнымиШаблон:Sfn.
Понятия были разработаны в 1970-е годы Даной Скоттом, благодаря им построены первая непротиворечивая модель бестипового λ-исчисления и Шаблон:Iw. В частности, функции аппликации и каррирования являются непрерывными по СкоттуШаблон:Sfn.
Определения
Если <math>P</math> и <math>Q</math> — частично упорядоченные множества, то функция <math>f\colon P\to Q</math> между ними является непрерывной по Скотту если для любого направленного подмножества <math>D \subseteq P</math> существует точная верхняя грань его образа <math>\sup f(D)</math>, притом выполнено следующее условие: <math>\sup f(D) = f(\sup D)</math>.
Топология Скотта на полном частично упорядоченном множестве <math>\langle D, \sqsubseteq \rangle</math> вводится определением открытого множества <math>O</math> как обладающего следующими свойствами:
- из того, что <math>x \in O</math> и <math>x \sqsubseteq y</math> следует <math>y \in O</math>;
- если <math>\bigsqcup X \in O</math>, где <math>X \subseteq D</math> и <math>X</math> направленно, то <math>X \cap O \neq \varnothing</math>Шаблон:Sfn.
Топология Скотта была впервые введена для полных решётокШаблон:Sfn, впоследствии была обобщена до полных частично упорядоченных множествШаблон:Sfn.
Категория, объектами которой являются полные частично упорядоченные множества, а морфизмами — непрерывные по Скотту отображения, обозначается <math>\mathsf{CPO}</math>.
Свойства
Функции, непрерывные по Скотту, всегда монотонны относительно отношения частичного порядка.
Подмножество частично упорядоченного множество замкнуто в топологии Скотта тогда и только тогда, когда оно является нижним множеством и включает точные верхние грани всех своих подмножествШаблон:Sfn.
Полное частично упорядоченное множество, наделённое топологией Скотта, всегда является T0-пространством, а хаусдорфовым — тогда и только тогда, когда отношение порядка тривиальноШаблон:Sfn.
Для любой непрерывной по Скотту функции, отображающей полное частично упорядоченное множество на себя, выполнена теорема Клини, согласно которой каждое такое отображение обладает единственной наименьшей неподвижной точкой. Кроме того, отображение <math>\mathbf{Fix}</math>, определённое на множестве непрерывных по Скотту функций <math>f \colon D \to D</math> и возвращающее для каждой функции значение её неподвижной точки (<math>\mathbf{Fix}(f)=x \Leftrightarrow f(x)=x</math>), само является непрерывным по СкоттуШаблон:Sfn.
Категория <math>\mathsf{CPO}</math> является декартово замкнутойШаблон:Sfn.
Аналоги
Близкой по свойствам к топологии Скотта конструкцией является категория <math>f_0</math>-пространств, разработанная Юрием Ершовым в 1975 году[1] — с её помощью также может быть построена непротиворечивая модель λ-исчисления. В качестве её преимущества отмечаетсяШаблон:Sfn, что категория <math>f_0</math>-пространств является декартово замкнутой, каждый объект в ней является топологическим пространством, топология на произведении является произведением топологий сомножителей, а топология в пространстве функций оказывается топологией поточечной сходимости. Такими удобными свойствами топология Скотта не обладает, в частности, произведение топологий Скотта на полных частично упорядоченных множеств в общем случае топологией Скотта на произведении множеств не является.
Примечания
Литература
