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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Полное частично упорядоченное множество, наделённое топологией Скотта всегда является T0-пространством, а хаусдорфовым — тогда и только тогда, когда отношение порядка тривиально[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

Литература[править | править исходный текст]