Домен Скотта

В математических областях теории порядка и области домен Скотта представляет собой алгебраический , ограниченно-полный и направленно-полный частичный порядок (dcpo). Они названы в честь Даны С. Скотт , которая первой изучила эти структуры при появлении теории доменов. Области Скотта очень тесно связаны с алгебраическими решетками и отличаются только отсутствием наибольшего элемента . Они также тесно связаны с информационными системами Скотта , которые представляют собой «синтаксическое» представление доменов Скотта.

Хотя термин «домен Скотта» широко используется вместе с приведенным выше определением, термин «домен» не имеет такого общепринятого значения, и разные авторы будут использовать разные определения; Сам Скотт использовал «домен» для структур, которые теперь называются «доменами Скотта». Кроме того, в некоторых публикациях домены Скотта появляются под другими названиями, например «алгебраическая полурешетка».

Первоначально Дана Скотт требовал полной решетки , а русский математик Юрий Ершов построил изоморфную структуру dcpo . Но это не было признано до тех пор, пока научные коммуникации не улучшились после падения железного занавеса . В честь своей работы ряд математических статей теперь называют эту фундаментальную конструкцию областью «Скотта – Ершова».

Определение [ править ]

Формально это непустое частично упорядоченное множество. $(D,\leq )$ называется доменом Скотта , если выполняются следующие условия:

$D$ направленно -полно все направленные подмножества D $, т. е .$ имеют верхнюю грань .
$D$ является ограниченно-полным , т.е. все подмножества $D$ , имеющие некоторую верхнюю границу, имеют верхнюю грань.
$D$ является алгебраическим каждый элемент $D$ может быть получен как верхняя грань направленного множества компактных D. $, т.е.$ элементов

Свойства [ править ]

Поскольку пустое множество заведомо имеет некоторую верхнюю границу, мы можем заключить, что существует наименьший элемент $\bot$ (супремум пустого множества) из ограниченной полноты.

Свойство ограниченно-полноты эквивалентно существованию нижних всех непустых подмножеств $D$ . Хорошо известно, что существование всех нижних влечет за собой существование всех верхних чисел и, таким образом, превращает частично упорядоченное множество в полную решетку . Таким образом, когда верхний элемент (нижняя грань пустого множества) присоединяется к области Скотта, можно заключить, что:

новый верхний элемент компактен (поскольку заказ был завершен ранее) и
результирующее ЧУУ будет алгебраической решеткой (т. е. полной алгебраической решеткой).

Следовательно, области Скотта являются в некотором смысле «почти» алгебраическими решетками. Однако удаление верхнего элемента из полной решетки не всегда приводит к созданию домена Скотта. (Рассмотрим полную решетку ${\mathcal {P}}(\mathbb {N} )$ . Конечные подмножества $\mathbb {N}$ образуют ориентированное множество, но не имеют верхней границы ${\mathcal {P}}(\mathbb {N} )\setminus \{\mathbb {N} \}$ .)

Домены Скотта становятся топологическими пространствами благодаря введению топологии Скотта .

Объяснение [ править ]

Домены Скотта предназначены для представления частичных алгебраических данных , упорядоченных по информационному содержанию. Элемент $x\in D$ представляет собой часть данных, которая может быть не полностью определена. Заявление $x\leq y$ означает " $y$ содержит всю информацию, которая $x$ делает». Нижний элемент — это элемент, не содержащий вообще никакой информации. Компактные элементы — это элементы, представляющие ограниченное количество информации.

При такой интерпретации мы видим, что супремум $\bigvee X$ из подмножества $X\subseteq D$ это элемент, который содержит всю информацию, которую любой элемент $X$ содержит, но не более того . Очевидно, что такая верхняя грань существует (т. е. имеет смысл) только при условии, что $X$ не содержит противоречивой информации; следовательно, область направлена и ограничена, но не все супремы обязательно существуют. Аксиома алгебраичности по существу гарантирует, что все элементы получают всю свою информацию (не строго) снизу в порядке; в частности, переход от компактных или «конечных» к некомпактным или «бесконечным» элементам скрыто не вносит никакой дополнительной информации, которая не может быть достигнута на каком-то конечном этапе.

С другой стороны, нижняя грань $\bigwedge X$ это элемент, который содержит всю информацию, которая является общей для всех элементов $X$ , и не меньше . Если $X$ не содержит последовательной информации, то его элементы не имеют общей информации, и поэтому его нижняя грань равна $\bot$ . Таким образом, все непустые инфимы существуют, но не все инфимы обязательно интересны.

Это определение в терминах частичных данных позволяет определить алгебру как предел последовательности все более определенных частичных алгебр - другими словами, фиксированную точку оператора, который добавляет к алгебре все больше информации. Дополнительные сведения см. в разделе Теория предметной области .

Примеры [ править ]

Каждое конечное ЧУ множество направленно-полно и алгебраично (хотя и не обязательно ограниченно-полно). Таким образом, любое ограниченно-полное конечное ЧУМ является областью Скотта.
Натуральные числа с дополнительным верхним элементом ω составляют алгебраическую решетку и, следовательно, область Скотта. Дополнительные примеры в этом направлении см. в статье об алгебраических решетках .
Рассмотрим множество всех конечных и бесконечных слов в алфавите ${0,1$ }, упорядоченных по префиксному порядку слов. Таким образом, слово $w$ меньше некоторого слова $v,$ если $w$ является префиксом слова $v$ , т. е. если существует какое-то (конечное или бесконечное) слово $v'$ такое, что $wv'=v$ . Например, $101\leq 10110$ . Пустое слово является нижним элементом этого порядка, и каждое направленное множество (которое всегда представляет собой цепочку легко увидеть, что ) имеет верхнюю грань. Аналогичным образом немедленно проверяется ограниченная полнота. Однако в полученном ЧУ-множестве определенно отсутствует вершина, имеющая вместо этого множество максимальных элементов (а именно, все бесконечные слова). Оно также является алгебраическим, поскольку каждое конечное слово оказывается компактным, и мы, конечно, можем аппроксимировать бесконечные слова цепочками конечных. Таким образом, это область Скотта, которая не является алгебраической решеткой.
В качестве отрицательного примера рассмотрим действительные числа в единичном интервале $[0,1]$ , упорядоченные по их естественному порядку. Эта ограниченно-полная dcpo не является алгебраической. Фактически его единственный компактный элемент — 0.

Ссылки [ править ]

Литература [ править ]

См. литературу по теории предметной области .