Свойства полноты в теории порядка

Введение

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

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

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

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

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

Определенная полнота

Дальнейшие простые условия полноты вытекают из рассмотрения всех непустых конечных множеств. Порядок, в котором все непустые конечные множества имеют как супремум, так и инфимум, называется решеткой. Достаточно потребовать существования супремума и инфимума для любых двух элементов, чтобы обеспечить существование супремума и инфимума для всех непустых конечных множеств; прямое доказательство по индукции показывает, что любой конечный непустой супремум/инфимум можно разложить на конечное число бинарных супремумов/инфимумов. Таким образом, центральными операциями решеток являются бинарные супремумы и инфимумы. Именно в этом контексте наиболее часто используются термины "meet" (наименьшая верхняя грань) и "join" (наибольшая нижняя грань). Частично упорядоченное множество, в котором гарантированно существуют только непустые конечные супремумы, называется полурешеткой присоединения. Двойственным понятием является полурешетка пересечения.

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

Сильнейшая форма полноты – это существование всех супремумов и всех инфимумов. Посеты, обладающие этим свойством, называются полными решетками. Однако, используя заданный порядок, можно рассматривать более узкие классы (возможно, бесконечных) подмножеств, которые не обеспечивают такой сильной полноты сразу. Если все направленные подмножества посета имеют супремум, то порядок является направленным полным частичным порядком (dcpo). Они особенно важны в теории областей. Двойственным понятием к dcpo, которое редко рассматривается, является фильтрованный полный посет. Dcpo с наименьшим элементом ("указанные dcpo") являются одним из возможных значений фразы "полный частичный порядок" (cpo). Если каждое подмножество, имеющее верхнюю границу, также имеет наименьшую верхнюю границу, то соответствующий посет называется ограниченно полным. Термин широко используется в этом определении, которое фокусируется на супремумах, и нет общепринятого названия для двойственного свойства. Однако ограниченная полнота может быть выражена через другие условия полноты, которые легко дуализируются (см. ниже). Хотя понятия "полный" и "ограниченный" уже были определены, путаница маловероятна, поскольку редко говорят об "ограниченно полном посете", имея в виду "ограниченный cpo" (который является просто "cpo с наибольшим элементом"). Аналогично, "ограниченно полная решетка" почти однозначна, поскольку свойство ограниченности обычно не указывается для полных решеток, где оно подразумевается. Также следует отметить, что пустое множество обычно имеет верхние границы (если посет непуст), и, следовательно, ограниченно полный посет имеет наименьший элемент. Можно также рассматривать подмножества посета, которые полностью упорядочены, то есть цепочки. Если все цепочки имеют супремум, то порядок называется цепью-полным. Опять же, эта концепция редко требуется в двойственной форме.

Связь между свойствами полноты

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

Полная версия универсальной алгебры

Как объяснено выше, наличие определенных условий полноты позволяет рассматривать образование определенных супремумов и инфимумов как тотальные операции частично упорядоченного множества. Оказывается, что во многих случаях можно охарактеризовать полноту исключительно, рассматривая соответствующие алгебраические структуры в смысле универсальной алгебры, которые оснащены операциями, подобными ∨ или ∧. Налагая дополнительные условия (в виде подходящих тождеств) на эти операции, можно тогда действительно получить лежащий в основе частичный порядок исключительно из таких алгебраических структур. Подробности об этой характеристике можно найти в статьях о структурах, "подобных решетке", для которых это обычно рассматривается: см. полурешетки, решетки, алгебры Хейтинга и булевы алгебры. Следует отметить, что последние две структуры расширяют применение этих принципов за пределы требований полноты, вводя дополнительную операцию отрицания.

Полная информация о дополнениях

Другой интересный способ характеризовать свойства полноты предоставляется через концепцию (монотонных) связей Галуа, то есть адъюнкций между частично упорядоченными множествами. Фактически, этот подход предлагает дополнительные сведения как о природе многих свойств полноты, так и о важности связей Галуа для теории порядка. Общее наблюдение, на котором основана эта переформулировка полноты, заключается в том, что построение определенных супремумов или инфимумов предоставляет левые или правые адъюнктные части подходящих связей Галуа. Рассмотрим частично упорядоченное множество (X, ≤). В качестве первого простого примера, пусть 1 = {*} будет заданным одноэлементным множеством с единственно возможным частичным порядком. Существует очевидное отображение j: X → 1, такое что j(x) = * для всех x из X. Множество X имеет наименьший элемент тогда и только тогда, когда функция j имеет нижний адъюнкт j*: 1 → X. Действительно, определение связей Галуа дает, что в этом случае 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 | y ≤ x}. Небольшое размышление показывает, что e имеет нижний адъюнкт тогда и только тогда, когда X является полной решеткой. Фактически, этот нижний адъюнкт будет отображать любое нижнее множество X в его супремум в X. Композиция этого нижнего адъюнкта с функцией, которая отображает любое подмножество X в его нижнее замыкание (опять же, адъюнкция для включения нижних множеств в булеан), дает обычное отображение супремума из булеана 2X в X. Как и прежде, другая важная ситуация возникает всякий раз, когда это отображение супремума также является верхним адъюнктом: в этом случае полная решетка X конструктивно полностью дистрибутивна. См. также статьи о полной дистрибутивности и дистрибутивности (теория порядка). Рассмотрения в этом разделе предполагают переформулировку (частей) теории порядка в терминах теории категорий, где свойства обычно выражаются путем ссылки на отношения (морфизмы, в частности: адъюнкции) между объектами, вместо рассмотрения их внутренней структуры. Для более подробного рассмотрения этой связи см. статью о категориальной формулировке теории порядка.

Another interesting way to characterize completeness properties is provided through the concept of (monotone) Galois connections, i. e. adjunctions between partial orders. In fact this approach offers additional insights both into the nature of many completeness properties and into the importance of Galois connections for order theory. The general observation on which this reformulation of completeness is based is that the construction of certain suprema or infima provides left or right adjoint parts of suitable Galois connections. Consider a partially ordered set (X, ≤). As a first simple example, let 1 = {*} be a specified one element set with the only possible partial ordering. There is an obvious mapping j: X → 1 with j(x) = * for all x in X. X has a least element if and only if the function j has a lower adjoint j*: 1 → X. Indeed the definition for Galois connections yields that in this case j*(*) ≤ x if and only if * ≤ j(x), where the right hand side obviously holds for any x. Dually, the existence of an upper adjoint for j is equivalent to X having a greatest element. Another simple mapping is the function q: X → X × X given by q(x) = (x, x). Naturally, the intended ordering relation for X × X is just the usual product order. q has a lower adjoint q* if and only if all binary joins in X exist. Conversely, the join operation : X × X → X can always provide the (necessarily unique) lower adjoint for q. Dually, q allows for an upper adjoint if and only if X has all binary meets. Thus the meet operation , if it exists, always is an upper adjoint. If both and exist and, in addition, is also a lower adjoint, then the poset X is a Heyting algebra—another important special class of partial orders. Further completeness statements can be obtained by exploiting suitable completion procedures. For example, it is well known that the collection of all lower sets of a poset X, ordered by subset inclusion, yields a complete lattice D(X) (the downset lattice). Furthermore, there is an obvious embedding e: X → D(X) that maps each element x of X to its principal ideal {y in X | y ≤ x}. A little reflection now shows that e has a lower adjoint if and only if X is a complete lattice. In fact, this lower adjoint will map any lower set of X to its supremum in X. Composing this lower adjoint with the function that maps any subset of X to its lower closure (again an adjunction for the inclusion of lower sets in the powerset), one obtains the usual supremum map from the powerset 2X to X. As before, another important situation occurs whenever this supremum map is also an upper adjoint: in this case the complete lattice X is constructively completely distributive. See also the articles on complete distributivity and distributivity (order theory). The considerations in this section suggest a reformulation of (parts of) order theory in terms of category theory, where properties are usually expressed by referring to the relationships (morphisms, more specifically: adjunctions) between objects, instead of considering their internal structure. For more detailed considerations of this relationship see the article on the categorical formulation of order theory.