В математической области теории порядка , полнота свойство утверждать существование определенных нижних граней или супремумов данного частично упорядоченное множество (посет). Самый знакомый пример - это полнота действительных чисел . Особое использование этого термина относится к полным частичным порядкам или полным решеткам . Однако существует много других интересных понятий полноты.
Мотивация для рассмотрения свойств полноты проистекает из огромной важности супрем (наименьшие верхние границы, соединения , " ") и инфима (наибольшие нижние границы, соответствует " ") для теории частичных порядков. Нахождение супремума означает выделение одного выделенного наименьшего элемента из набора верхних границ. С одной стороны, эти специальные элементы часто воплощают определенные конкретные свойства, которые интересны для данного приложения (например, наименьшее общее кратное набора чисел или объединение набора наборов). С другой стороны, знание того, что определенные типы подмножествгарантированно имеют верхнюю или нижнюю границу, что позволяет нам рассматривать вычисление этих элементов как полные операции на частично упорядоченном множестве. По этой причине множества с определенными свойствами полноты часто можно описать как алгебраические структуры определенного типа. Кроме того, изучение свойств вновь полученных операций дает дополнительные интересные темы.
Типы свойств полноты [ править ]
Все свойства полноты описываются по аналогичной схеме: один описывает определенный класс подмножеств частично упорядоченного множества, которые должны иметь верхнюю грань или точную нижнюю грань. Следовательно, каждое свойство полноты имеет двойственное свойство , полученное обращением зависимых от порядка определений в данном утверждении. Некоторые из понятий обычно не дуализируются, в то время как другие могут быть самодвойственными (т. Е. Эквивалентными своим двойственным утверждениям).
Наименьшие и самые большие элементы [ править ]
Самый простой пример супремума - это супремум, то есть супремум пустого множества . По определению, это наименьший элемент среди всех элементов, которые больше каждого члена пустого набора. Но это всего лишь наименьший элемент всего чугуна, если он есть, поскольку пустое подмножество чугуна P традиционно считается ограниченным сверху и снизу, причем каждый элемент P является как верхней, так и нижней границей. пустого подмножества. Другие общие имена для наименьшего элемента - нижний и нулевой (0). Двойственное понятие, пустая нижняя граница, является наибольшим элементом , верхом или единицей (1).
Посеты с низом иногда называют заостренными, а позы с вершиной - единичными или вершинными. Порядок, в котором есть как наименьший, так и наибольший элемент, ограничен. Однако это не следует путать с приведенным ниже понятием ограниченной полноты .
Конечная полнота [ править ]
Дальнейшие простые условия полноты возникают из рассмотрения всех непустых конечных множеств . Порядок, в котором все непустые конечные множества имеют как верхнюю, так и нижнюю грань, называется решеткой . Достаточно потребовать, чтобы все верхние и нижние границы двух элементов существовали, чтобы получить все непустые конечные; простой аргумент индукции показывает, что каждая конечная непустая верхняя / нижняя грань может быть разложена на конечное число двоичных верхних / нижних граней. Таким образом, центральные операции решеток - это двоичные верхняя и нижняя граница . Именно в этом контексте наиболее распространены термины «встреча для» и «присоединиться для» .
Таким образом, ч.у.у., в котором известно, что существуют только непустые конечные супремы, называется полурешёткой соединения . Двойственное понятие - это полурешетка .
Дальнейшие условия полноты [ править ]
Самая сильная форма полноты - это наличие всех супрем и инфим. Посети с этим свойством являются полными решетками . Однако, используя данный порядок, можно ограничиться дополнительными классами (возможно, бесконечными) подмножествами, которые не дают сразу этой сильной полноты.
Если все направленные подмножества чугуна имеют верхнюю грань, то порядок является направленно-полным частичным порядком (dcpo). Это особенно важно в теории предметной области . Редко рассматриваемое двойственное понятие для dcpo - это отфильтрованный полный poset. Dcpos с наименьшим элементом ("заостренные dcpos") - одно из возможных значений фразы полный частичный порядок (cpo).
Если каждое подмножество, которое имеет некоторую верхнюю границу, также имеет наименьшую верхнюю границу, то соответствующее ЧУМ называется ограниченным полным.. Этот термин широко используется в этом определении, в котором основное внимание уделяется супреме, и нет общего названия для двойного свойства. Однако ограниченная полнота может быть выражена в терминах других условий полноты, которые легко дуализуются (см. Ниже). Хотя понятия с именами «полный» и «ограниченный» уже были определены, путаница вряд ли возникнет, поскольку редко можно говорить об «ограниченном полном poset», имея в виду «ограниченный cpo» (который является просто «cpo с наибольшим элементом "). Точно так же «ограниченная полная решетка» почти однозначна, поскольку нельзя было бы утверждать свойство ограниченности для полных решеток, где оно все равно подразумевается. Также обратите внимание, что пустое множество обычно имеет верхнюю границу (если ЧУМ непусто) и, таким образом, ограниченно-полное ЧУМ имеет наименьший элемент.
Можно также рассматривать подмножества ч.у., которые полностью упорядочены , то есть цепи . Если все цепочки имеют верхнюю грань, порядок называется завершенной цепочкой . Опять же, эта концепция редко бывает нужна в двойной форме.
Отношения между свойствами полноты [ править ]
Уже было замечено, что двоичные встречи / соединения дают все непустые конечные встречи / соединения. Точно так же многие другие (комбинации) вышеперечисленных условий эквивалентны.
- Самый известный пример - существование всех супремумов, что фактически эквивалентно существованию всех инфим, при условии, что существует дно. В самом деле, для любого подмножества X ч.у.набора можно рассматривать его набор нижних границ B , который не является пустым, поскольку он содержит по крайней мере нижнюю часть. Супремум В этом случае будет равен инфимумом X : так как каждый элемент X представляет собой верхнюю грань B , SUP B меньше , чем все элементы X , т.е. глотки B находится в B . Это наибольший элемент B и, следовательно, точная нижняя грань X. Двойным образом существование всех инфим подразумевает существование всех супрем.
- Ограниченную полноту также можно охарактеризовать по-разному. С помощью рассуждений, аналогичных приведенным выше, можно найти, что верхняя грань множества с верхними границами является точной гранью набора верхних границ. Следовательно, ограниченная полнота равносильна существованию всех непустых инфим.
- ЧУМ является полной решеткой тогда и только тогда, когда он является cpo и полурешеткой соединения. Действительно, для любого подмножества X , множество всех конечных супремумов (присоединяется) из X направляются и супремум этого множества (который существует путем направленной полноты) равен супремуму X . Таким образом, каждое множество имеет верхнюю грань, и согласно вышеизложенному наблюдению мы имеем полную решетку. Другое направление доказательства тривиально.
- Принимая аксиому выбора , poset является цепно полным тогда и только тогда, когда это dcpo.
Полнота в терминах универсальной алгебры [ править ]
Как объяснялось выше, наличие определенных условий полноты позволяет рассматривать формирование определенных супрем и инфим как совокупные операции частично упорядоченного множества. Оказывается, во многих случаях можно охарактеризовать полноту, только рассматривая соответствующие алгебраические структуры в смысле универсальной алгебры , которые снабжены операциями типа или . Налагая дополнительные условия (в форме подходящих тождеств ) на эти операции, можно действительно вывести основной частичный порядок исключительно из таких алгебраических структур. Подробности об этой характеристике можно найти в статьях о "решетчатых" структурах, для которых это обычно рассматривается: см. Полурешетка, решетка , алгебра Гейтинга и булева алгебра . Обратите внимание, что последние две структуры расширяют применение этих принципов за рамки простых требований полноты, вводя дополнительную операцию отрицания .
Полнота с точки зрения добавлений [ править ]
Другой интересный способ охарактеризовать свойства полноты - это концепция (монотонных) связей Галуа , то есть присоединений между частичными порядками. Фактически, этот подход предлагает дополнительное понимание как природы многих свойств полноты, так и важности связей Галуа для теории порядка. Общее наблюдение, на котором основана эта переформулировка полноты, состоит в том, что конструкция определенной супремы или инфимы обеспечивает левую или правую сопряженную часть подходящих связностей Галуа.
Рассмотрим частично упорядоченное множество ( X , ≤). В качестве первого простого примера пусть 1 = {*} будет заданным одноэлементным набором с единственно возможным частичным упорядочением. Существует очевидное отображение J : X → 1 с J ( х ) = * для всех х в X . Х имеет наименьший элемент тогда и только тогда , когда функция J имеет более низкую присоединенное J * : 1 → Х . Действительно, из определения связности Галуа следует, что в этом случае j * (*) ≤ x тогда и только тогда, когда * ≤ j ( x), где правая часть, очевидно, верна для любого x . Двойственно, существование верхнего сопряженного элемента j эквивалентно тому, что X имеет наибольший элемент.
Другое простое отображение - это функция q : X → X × X, заданная формулой q ( x ) = ( x , x ). Естественно, предполагаемое отношение упорядочения для X × X - это просто обычный заказ продукта . q имеет нижний сопряженный q * тогда и только тогда, когда все двоичные соединения в X существуют. Наоборот, операция соединения : X × X → X всегда может предоставить (обязательно единственный) нижний сопряженный элемент для q . Вдвойне,q допускает верхний сопряженный элемент тогда и только тогда, когда X имеет все двоичные пересечения. Таким образом, операция встречи , если она существует, всегда является сопряженной сверху. Если оба и существуют и, кроме того, также является нижним сопряженным, то ч.у. X является алгеброй Гейтинга - другим важным специальным классом частичных порядков.
Дальнейшие заявления о полноте можно получить, используя подходящие процедуры завершения . Например, хорошо известно, что совокупность всех нижних множеств ч.у. X , упорядоченная по включению подмножества , дает полную решетку D ( X ) (решётку вниз). Кроме того, существует очевидное вложение e : X → D ( X ), которое отображает каждый элемент x из X в его главный идеал { y в X | у ≤ х}. Небольшое размышление теперь показывает, что e имеет сопряженный снизу тогда и только тогда, когда X - полная решетка. На самом деле, эта нижняя сопряженный сопоставляются любого нижнего набора X к его супремуму в X . Компоновка это с помощью функции , которая отображает любое подмножество X к его нижнему закрытию (опять примыкания для включения нижних множеств в Powerset ), получает обычную карту супремума из Powerset 2 X к X . Как и раньше, еще одна важная ситуация возникает всякий раз , когда это супремумом карта также верхний сопряженный: в этом случае полная решетка X является конструктивно полностью дистрибутивный. См. Также статьи о полной дистрибутивности и дистрибутивности (теория порядка) .
Соображения в этом разделе предлагают переформулировать (части) теории порядка в терминах теории категорий , где свойства обычно выражаются посредством ссылки на отношения ( морфизмы , более конкретно: присоединения) между объектами, вместо рассмотрения их внутренней структуры. Более подробное рассмотрение этой связи см. В статье о категориальной формулировке теории порядка .
См. Также [ править ]
- Лимитосохраняющая функция по сохранению существующих супрем / инфима.
- Общий заказ
Заметки [ править ]
Ссылки [ править ]
- Г. Марковский и Б. К. Розен. Основы для цепно-полных поз. IBM Journal of Research and Development. Март 1976 г.
- Стивен Блум. Разновидности упорядоченных алгебр Журнал компьютерных и системных наук. Октябрь 1976 г.
- Майкл Смит. Power domains Журнал компьютерных и системных наук. 1978 г.
- Даниэль Леманн. Об алгебре порядка Journal of Computer and System Sciences. Август 1980 г.
