Полнота (теория порядка)

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

Мотивация рассмотрения свойств полноты проистекает из огромной важности супремумов (наименьших верхних границ, объединений , $\vee$") и инфима (наибольшая нижняя граница, соответствует , " $\wedge$") к теории частичных порядков. Нахождение супремума означает выделение одного выделенного наименьшего элемента из множества верхних границ. С одной стороны, эти специальные элементы часто воплощают в себе некоторые конкретные свойства, интересные для данного приложения (например, (наименьшее общее кратное набора чисел или объединения набора множеств). С другой стороны, знание того, что определенные типы подмножеств гарантированно имеют верхние или нижние значения, позволяет нам рассматривать оценку этих элементов как общую. ЧУП По этой причине с определенными свойствами полноты часто можно описать как алгебраические структуры определенного типа. Кроме того, изучение свойств вновь полученных операций дает дополнительные интересные темы.

Типы свойств полноты

Все свойства полноты описываются по сходной схеме: описывается определенный класс подмножеств частично упорядоченного множества, для которых требуется наличие верхней границы или обязательно наличие нижней нижней границы. Следовательно, каждое свойство полноты имеет двойственное , полученное путем обращения зависимых от порядка определений в данном утверждении. Некоторые из понятий обычно не дуализированы, тогда как другие могут быть самодуальными (т.е. эквивалентными своим двойственным утверждениям).

Наименьшие и наибольшие элементы

Самый простой пример супремума — пустой, т.е. супремум пустого множества . По определению, это наименьший элемент среди всех элементов, которые больше каждого члена пустого множества. Но это всего лишь наименьший элемент всего ЧУ-множества, если он у него есть, поскольку пустое подмножество ЧУ-множества P традиционно считается ограниченным одновременно сверху и снизу, причем каждый элемент P является одновременно верхней и нижней границей. пустого подмножества. Другие распространенные названия наименьшего элемента — нижний и нулевой (0). Двойственное понятие, пустая нижняя граница, — это наибольший элемент , вершина или единица (1).

Посеты, имеющие нижнюю часть, иногда называют заостренными, а посеты с вершиной — унитальными или вершинными. Порядок, в котором есть как наименьший, так и наибольший элемент, является ограниченным. Однако это не следует путать с понятием ограниченной полноты , приведенным ниже.

Конечная полнота

Дальнейшие простые условия полноты возникают из рассмотрения всех непустых конечных множеств . Порядок, в котором все непустые конечные множества имеют верхнюю и нижнюю грани, называется решеткой . Достаточно потребовать, чтобы все верхние и нижние элементы двух элементов существовали, чтобы получить все непустые конечные; простой аргумент индукции показывает, что каждую конечную непустую верхнюю/нижнюю грань можно разложить на конечное число двоичных верхних/нижних граней. Таким образом, центральными операциями решеток являются бинарные супремумы. $\vee$ и самый низкий $\wedge$. Именно в этом контексте термины совпадают для $\wedge$ и присоединяйтесь к $\vee$ являются наиболее распространенными.

Поэтому ЧУ-множество, в котором известно, что существуют только непустые конечные верхние числа, называется объединенной полурешеткой . Двойственное понятие — встреча-полурешетка .

Дальнейшие условия полноты

Самая сильная форма полноты — это существование всех супремумов и всех инфимов. Частные множества с этим свойством являются полными решетками . Однако, используя данный порядок, можно ограничиться дополнительными классами (возможно, бесконечными) подмножеств, которые не дают сразу такой сильной полноты.

Если все направленные подмножества частичного порядка имеют верхнюю границу, то порядок является направленно-полным частичным порядком (dcpo). Они особенно важны в теории предметной области . Редко рассматриваемое двойственное понятие для dcpo — это фильтрованно-полный ЧУМ. Dcpos с наименьшим элементом («заостренный dcpos») — одно из возможных значений фразы полный частичный порядок (cpo).

Если каждое подмножество, имеющее некоторую верхнюю границу, также имеет и наименьшую верхнюю границу, то соответствующее частичное множество называется ограниченным полным . Этот термин широко используется в этом определении, в котором основное внимание уделяется супремамам, и не существует общего названия для двойственного свойства. Однако ограниченная полнота может быть выражена через другие условия полноты, которые легко дуализируются (см. ниже). Хотя понятия с названиями «полный» и «ограниченный» уже были определены, путаница вряд ли произойдет, поскольку редко можно говорить об «ограниченном полном частично упорядоченном множестве», когда имеется в виду «ограниченный cpo» (который представляет собой просто «cpo с наибольшим элементом "). Аналогично, «ограниченная полная решетка» почти однозначна, поскольку нельзя утверждать свойство ограниченности для полных решеток, где оно и так подразумевается. Также обратите внимание, что пустое множество обычно имеет верхние границы (если ЧУ-множество не пусто), и, следовательно, ограниченно-полное ЧУ-множество имеет наименьший элемент.

Можно также рассмотреть подмножества ЧУУ, которые полностью упорядочены , т.е. цепи . Если все цепочки имеют верхнюю границу, порядок называется цепочкой завершенной . Опять же, эта концепция редко используется в двойственной форме.

Отношения между свойствами полноты

Уже было замечено, что бинарные встречи/соединения дают все непустые конечные встречи/соединения. Аналогично, многие другие (комбинации) вышеуказанных условий эквивалентны.

• Самый известный пример — существование всех супремумов, что фактически эквивалентно существованию всех инфимов. Действительно, для любого подмножества X частичного множества можно рассмотреть его множество нижних границ B . Верхняя грань B тогда равна нижней грани X : поскольку каждый элемент X является верхней границей B , sup B меньше, чем все элементы X , т. е. sup находится в B. B Это наибольший элемент B нижняя грань X. и, следовательно , Двояким образом существование всех инфим подразумевает существование всех супремумов.
• Ограниченную полноту можно охарактеризовать и по-разному. С помощью аргумента, аналогичного приведенному выше, можно обнаружить, что верхняя грань набора с верхними границами является нижней границей множества верхних границ. Следовательно, ограниченная полнота эквивалентна существованию всех непустых инфим.
• ЧУ-множество является полной решеткой тогда и только тогда, когда оно является cpo и полурешеткой соединения. Действительно, для любого подмножества X множество всех конечных супремумов (соединений) X направлено, и верхняя грань этого множества (которая существует в силу направленной полноты) равна супремуму X . Таким образом, каждое множество имеет верхнюю границу, и по приведенному выше наблюдению мы имеем полную решетку. Другое направление доказательства тривиально.
• Предполагая аксиому выбора , ЧУУ является цепочечным тогда и только тогда, когда оно является dcpo.

с точки зрения

Как объяснялось выше, наличие определенных условий полноты позволяет рассматривать образование тех или иных супремумов и минимумов как тотальные операции частично упорядоченного множества. Оказывается, во многих случаях охарактеризовать полноту можно лишь рассматривая соответствующие алгебраические структуры в смысле универсальной алгебры , снабженные операциями типа $\vee$ или $\wedge$. Налагая дополнительные условия (в виде подходящих тождеств ) на эти операции, можно действительно вывести основной частичный порядок исключительно из таких алгебраических структур. Подробности об этой характеристике можно найти в статьях о «решетчатых» структурах, для которых это обычно рассматривается: см. полурешетка , решетка , алгебра Гейтинга и булева алгебра . Обратите внимание, что последние две структуры расширяют применение этих принципов за пределы простых требований полноты, вводя дополнительную операцию отрицания .

Полнота с точки зрения дополнений

Другой интересный способ охарактеризовать свойства полноты обеспечивается с помощью концепции (монотонных) связей Галуа , то есть соединений между частичными порядками. Фактически этот подход предлагает дополнительное понимание как природы многих свойств полноты, так и важности связей Галуа для теории порядка. Общее наблюдение, на котором основана эта переформулировка полноты, состоит в том, что построение определенных супремум или нижних даёт левые или правые присоединенные части подходящих связей Галуа.

Рассмотрим частично упорядоченное множество ( X , ≤). В качестве первого простого примера пусть 1 = {*} — заданный набор из одного элемента с единственно возможным частичным упорядочением. Существует очевидное отображение j : X 1 с j ( x ) = * для всех x в X. → X имеет наименьший элемент тогда и только тогда, когда функция j имеет нижний сопряженный j ^* 1 → Х. : Действительно, определение связностей Галуа дает, что в этом случае j ^* (*) ≤ x тогда и только тогда, когда * ≤ j ( x ), где правая часть очевидно справедлива для любого x . Двойственно, существование верхнего сопряженного для j эквивалентно тому, что X имеет наибольший элемент.

Другое простое отображение — это функция q : X → X × X, заданная формулой q ( x ) = ( x , x ). Естественно, предполагаемое отношение порядка для X × X — это обычный порядок произведения . q имеет нижний сопряженный q ^* тогда и только тогда, когда все двоичные соединения в X существуют. И наоборот, операция соединения $\vee$: X × X → X всегда может предоставить (обязательно уникальный) нижний сопряженный для q . Двойственно, q допускает верхнее сопряженное тогда и только тогда, когда X имеет все двоичные совпадения. Таким образом, операция встречи $\wedge$, если он существует, всегда является верхним сопряженным. Если оба $\vee$ и $\wedge$ существуют и, кроме того, $\wedge$ также является нижним сопряженным, то ЧУМ X является гейтинговой алгеброй — еще одним важным специальным классом частичных порядков.

Дальнейшие утверждения о полноте могут быть получены путем использования подходящих процедур завершения . Например, хорошо известно, что совокупность всех нижних множеств частичного множества X , упорядоченных по включению подмножеств , дает полную решетку D ( X ) (нижнюю решетку). Более того, существует очевидное вложение e : X → D ( X ), которое отображает каждый элемент x из X в его главный идеал { y в X | у ≤ х }. Небольшое размышление показывает, что e имеет нижний сопряженный тогда и только тогда, когда X — полная решетка. Фактически, этот нижний сопряженный отображает любое нижнее множество X в его верхнюю грань в X . Составляя это нижнее сопряженное с функцией, которая отображает любое подмножество X в его нижнее замыкание (опять-таки дополнение для включения нижних множеств в набор степеней ), можно получить обычное отображение супремума из набора степеней 2. ^Х до Х. ​Как и раньше, возникает еще одна важная ситуация, когда это отображение супремума является также верхним сопряженным: в этом случае полная решетка X дистрибутивна конструктивно вполне . См. также статьи о полной дистрибутивности и дистрибутивности (теории порядка) .

Соображения в этом разделе предлагают переформулировать теорию (части) порядка в терминах теории категорий , где свойства обычно выражаются путем ссылки на отношения ( морфизмы , точнее: соединения) между объектами, вместо рассмотрения их внутренней структуры. Более подробное рассмотрение этой взаимосвязи см. в статье о категориальной формулировке теории порядка .

См. также

• Полностью распределительная решетка
• Функция сохранения пределов по сохранению существующих супремумов/инфимов.
• Общий порядок - заказ, все элементы которого сопоставимы.

Ссылки

• Г. Марковский и Б.К. Розен. Базисы для частично упорядоченных множеств IBM Journal of Research and Development. Март 1976 года.
• Стивен Блум. Разновидности упорядоченных алгебр Журнал компьютерных и системных наук. Октябрь 1976 года.
• Майкл Смит. Силовые домены Журнал компьютерных и системных наук. 1978.
• Дэниел Леманн. Об алгебре порядка Журнал компьютерных и системных наук. Август 1980 года.