В математических полях порядка и теории домена , домен Скотт является алгебраическим , ограниченно-полным фо . Они названы в честь Даны С. Скотт , который первым изучил эти структуры при появлении теории предметной области. Области Скотта очень тесно связаны с алгебраическими решетками , отличаясь только возможным отсутствием наибольшего элемента . Они также тесно связаны с информационными системами Скотта , которые составляют «синтаксическое» представление доменов Скотта.
Хотя термин «домен Скотта» широко используется в приведенном выше определении, термин «домен» не имеет такого общепринятого значения, и разные авторы будут использовать разные определения; Сам Скотт использовал «домен» для структур, которые теперь называются «доменами Скотта». Кроме того, в некоторых публикациях домены Скотта появляются под другими названиями, такими как «алгебраическая полурешетка».
Первоначально Дана Скотт требовала полной решетки , и русский математик Юрий Ершов построил изоморфную структуру cpo . Но это не было признано до тех пор, пока после падения железного занавеса научные коммуникации не улучшились . В честь их работы в ряде математических работ эту фундаментальную конструкцию теперь называют областью «Скотта – Ершова».
Определение
Формально непустое частично упорядоченное множество ( D , ≤) называется областью Скотта, если выполняется следующее:
- D будет направлен полным , то есть все направленные подмножества из D имеет грань .
- D является ограниченно полным , т. Е. Все подмножества D, которые имеют некоторую верхнюю границу, имеют супремум.
- D является алгебраическим , то есть каждый элемент D может быть получен как супремум направленного множества компактных элементов из D .
Характеристики
Поскольку пустое множество заведомо имеет некоторую верхнюю границу, мы можем сделать вывод о существовании наименьшего элемента (супремум пустого множества) из ограниченной полноты.
Свойство быть ограниченным полным эквивалентно существование нижних граней всех непустых подмножеств D . Хорошо известно, что существование всех инфим подразумевает существование всех супремумов и, таким образом, превращает частично упорядоченное множество в полную решетку . Таким образом, когда верхний элемент (нижняя грань пустого множества) присоединяется к области Скотта, можно сделать вывод, что:
- новый верхний элемент является компактным (так как ранее заказ был завершен) и
- результирующий ЧУМ будет алгебраической решеткой (то есть полной решеткой, которая является алгебраической).
Следовательно, области Скотта являются в некотором смысле «почти» алгебраическими решетками. Однако удаление верхнего элемента из полной решетки не всегда дает домен Скотта. (Рассмотрим полную решетку. Конечные подмножества образуют направленное множество, но не имеют верхней границы в .)
Области Скотта становятся топологическими пространствами благодаря введению топологии Скотта .
Объяснение
Домены Скотта предназначены для представления частичных алгебраических данных , упорядоченных по содержанию информации. Элементэто часть данных, которая может быть не полностью определена. Заявление средства " содержит всю информацию, которая делает".
При такой интерпретации мы видим, что супремум подмножества это элемент, который содержит всю информацию, которую любой элементсодержит, но не более того . Очевидно, что такой супремум существует (т.е. имеет смысл) только при условии, чтоне содержит противоречивой информации; следовательно, область направлена и ограниченно полная, но не все супремы обязательно существуют. Аксиома алгебраичности по существу гарантирует, что все элементы получают всю свою информацию от (нестрого) более низкого порядка; в частности, переход от компактных или «конечных» элементов к некомпактным или «бесконечным» элементам не вносит скрытно никакой дополнительной информации, которая не может быть достигнута на некотором конечном этапе. Нижний элемент - это верхняя грань пустого множества, т. Е. Элемент, не содержащий вообще никакой информации; его существование подразумевает ограниченную полноту, поскольку пустое множество пусто имеет верхнюю границу в любом непустом чум.
С другой стороны, инфимум это элемент, который содержит всю информацию, которая является общей для всех элементов, и не меньше . Если не содержит непротиворечивой информации, то его элементы не имеют общей информации, поэтому его нижняя грань равна . Таким образом, существует вся непустая инфима, но не вся инфима обязательно интересна.
Это определение в терминах частичных данных позволяет определить алгебру как предел последовательности все более определенных частичных алгебр - другими словами, фиксированная точка оператора, который постепенно добавляет больше информации в алгебру. Для получения дополнительной информации см. Теория предметной области .
Примеры
- Каждый конечный ч.у. направлен полон и алгебраичен. Таким образом, любое ограниченно-полное конечное ч.у.м. тривиально является областью Скотта.
- В натуральных числах с дополнительным верхним элементом со представляют собой алгебраическую решетку, следовательно , домен Скотта. Дополнительные примеры в этом направлении см. В статье об алгебраических решетках .
- Рассмотрим множество всех конечных и бесконечных слов в алфавите {0,1}, упорядоченных по порядку префиксов на словах. Таким образом, слово w меньше некоторого слова v, если w является префиксом v , т.е. если существует некоторое (конечное или бесконечное) слово v ' такое, что w v' = v . Например, 101 ≤ 10110. Пустое слово является нижним элементом этого порядка, и каждый направленный набор (который всегда представляет собой цепочку ), как легко увидеть, имеет верхнюю грань. Точно так же сразу проверяется ограниченная полнота. Однако в результирующем poset определенно отсутствует вершина с множеством максимальных элементов (например, 111 ... или 000 ...). Он также является алгебраическим, поскольку каждое конечное слово оказывается компактным, и мы, конечно, можем аппроксимировать бесконечные слова цепочками из конечных. Таким образом, это область Скотта, которая не является алгебраической решеткой.
- В качестве отрицательного примера рассмотрим действительные числа в единичном интервале [0,1], упорядоченные по их естественному порядку. Эта ограниченно-полная cpo не является алгебраической. Фактически, его единственный компактный элемент - 0.
Литература
См. Литературу по теории предметной области .