Interested Article - Непрерывность по Скотту
- 2020-02-12
- 2
Непрерывность по Скотту — свойство функций над частично упорядоченными множествами , выражающееся в сохранении точной верхней грани относительно отношения частичного порядка .
Топология Скотта — структура над или, в более общем случае, над полным частично упорядоченным множеством , в которой открытыми считаются верхние множества , недоступные для прямых соединений, или эквивалентно, топология, в рамках которой функции над частично упорядоченными множествами , сохраняющие точную верхнюю грань, являются непрерывными .
Понятия были разработаны в 1970-е годы Даной Скоттом , благодаря им построены первая непротиворечивая модель бестипового λ-исчисления и . В частности, функции аппликации и каррирования являются непрерывными по Скотту .
Определения
Если и — частично упорядоченные множества, то функция между ними является непрерывной по Скотту если для любого направленного подмножества существует точная верхняя грань его образа , притом выполнено следующее условие: .
Топология Скотта на полном частично упорядоченном множестве вводится определением открытого множества как обладающего следующими свойствами:
- из того, что и следует ;
- если , где и направленно , то .
Топология Скотта была впервые введена для , впоследствии была обобщена до полных частично упорядоченных множеств .
Категория , объектами которой являются полные частично упорядоченные множества, а морфизмами — непрерывные по Скотту отображения, обозначается .
Свойства
Функции, непрерывные по Скотту, всегда монотонны относительно отношения частичного порядка .
Подмножество частично упорядоченного множество замкнуто в топологии Скотта тогда и только тогда, когда оно является нижним множеством и включает точные верхние грани всех своих подмножеств .
Полное частично упорядоченное множество, наделённое топологией Скотта, всегда является T 0 -пространством , а хаусдорфовым — тогда и только тогда, когда отношение порядка тривиально .
Для любой непрерывной по Скотту функции, отображающей полное частично упорядоченное множество на себя, выполнена теорема Клини , согласно которой каждое такое отображение обладает единственной наименьшей неподвижной точкой . Кроме того, отображение , определённое на множестве непрерывных по Скотту функций и возвращающее для каждой функции значение её неподвижной точки ( ), само является непрерывным по Скотту .
Категория является декартово замкнутой .
Аналоги
Близкой по свойствам к топологии Скотта конструкцией является категория -пространств, разработанная Юрием Ершовым в 1975 году — с её помощью также может быть построена непротиворечивая модель λ-исчисления. В качестве её преимущества отмечается , что категория -пространств является декартово замкнутой, каждый объект в ней является топологическим пространством, топология на произведении является произведением топологий сомножителей, а топология в пространстве функций оказывается топологией поточечной сходимости . Такими удобными свойствами топология Скотта не обладает, в частности, произведение топологий Скотта на полных частично упорядоченных множеств в общем случае топологией Скотта на произведении множеств не является.
Примечания
- , Теорема 1.2.6, с. 23.
- , Теоремы 1.2.13, 1.2.14, с. 25.
- ↑ , с. 24.
- .
- ↑ .
- , Теорема 1.2.17, с. 25-26.
- , Теорема 1.2.16, с. 25.
- Ершов, Юрий . Теория нумераций. — М. : Наука , 1977. — 416 с.
- , с. 22.
Литература
- Abramsky, Samson and Jung, Achim. // 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 . (англ.) // . — 1972. — Vol. 274 . — P. 97–136 . — doi : .
- Vickers, Steven. Topology via Logic. — Cambridge : Cambridge University Press , 1989. — 206 с. — ISBN 0-521-36062-5 .
- 2020-02-12
- 2