В математической области теории порядка свойства полноты утверждают существование определенных нижних или верхних границ данного частично упорядоченного множества (посета). Наиболее известным примером является полнота действительных чисел . Специальное использование термина относится к полным частичным порядкам или полным решеткам . Однако существует много других интересных понятий полноты.
Мотивация рассмотрения свойств полноты вытекает из большой важности suprema (наименьших верхних границ, joins , " ") и infima (наибольших нижних границ, meets , " ") для теории частичных порядков. Нахождение supremum означает выделение одного выделенного наименьшего элемента из множества верхних границ. С одной стороны, эти специальные элементы часто воплощают определенные конкретные свойства, которые интересны для данного приложения (например, быть наименьшим общим кратным набора чисел или объединением набора множеств). С другой стороны, знание того, что определенные типы подмножеств гарантированно имеют suprema или infima, позволяет нам рассматривать оценку этих элементов как общие операции на частично упорядоченном множестве. По этой причине частично упорядоченные множества с определенными свойствами полноты часто можно описать как алгебраические структуры определенного вида. Кроме того, изучение свойств вновь полученных операций дает дополнительные интересные предметы.
Все свойства полноты описываются по схожей схеме: описывается некоторый класс подмножеств частично упорядоченного множества, которые должны иметь супремум или должны иметь инфимум. Следовательно, каждое свойство полноты имеет свое двойственное , полученное путем инвертирования зависящих от порядка определений в данном утверждении. Некоторые из понятий обычно не дуализируются, в то время как другие могут быть самодвойственными (т. е. эквивалентными своим двойственным утверждениям).
Самый простой пример супремума — пустой, т. е. супремум пустого множества . По определению, это наименьший элемент среди всех элементов, которые больше каждого члена пустого множества. Но это всего лишь наименьший элемент всего посета, если он есть, поскольку пустое подмножество посета P традиционно считается как ограниченным сверху, так и снизу, причем каждый элемент P является как верхней, так и нижней границей пустого подмножества. Другие распространенные названия для наименьшего элемента — низ и ноль (0). Двойственное понятие, пустая нижняя граница, — это наибольший элемент , вершина или единица (1).
Посеты, имеющие дно, иногда называются заостренными, а посеты с вершиной называются единичными или увенчанными. Порядок, имеющий как наименьший, так и наибольший элемент, ограничен. Однако это не следует путать с понятием ограниченной полноты, приведенным ниже.
Дальнейшие простые условия полноты возникают из рассмотрения всех непустых конечных множеств . Порядок, в котором все непустые конечные множества имеют как супремум, так и инфимум, называется решеткой . Достаточно потребовать, чтобы все супремумы и инфимумы двух элементов существовали, чтобы получить все непустые конечные; прямое индукционное рассуждение показывает, что каждый конечный непустой супремум/инфимум может быть разложен на конечное число бинарных супремумов/инфимумов. Таким образом, центральными операциями решеток являются бинарные супремумы и инфимумы . Именно в этом контексте термины meet for и join for являются наиболее распространенными.
Поэтому частично упорядоченное множество, в котором известны только непустые конечные супремумы, называется join-полурешеткой . Двойственное понятие — meet-полурешетка .
Самая сильная форма полноты — это существование всех супремумов и всех инфимумов. ЧУМы с этим свойством — это полные решетки . Однако, используя заданный порядок, можно ограничиться дополнительными классами (возможно, бесконечных) подмножеств, которые не дают эту сильную полноту сразу.
Если все направленные подмножества частично упорядоченного множества имеют супремум, то порядок является направленно-полным частичным порядком (dcpo). Они особенно важны в теории доменов . Редко рассматриваемое двойственное понятие к dcpo — это отфильтрованно-полный частично упорядоченный набор. Dcpos с наименьшим элементом («указанные dcpos») — одно из возможных значений фразы полный частичный порядок (cpo).
Если каждое подмножество, имеющее некоторую верхнюю границу, также имеет наименьшую верхнюю границу, то соответствующее частично упорядоченное множество называется ограниченным полным . Этот термин широко используется с этим определением, которое фокусируется на супремумах, и для двойственного свойства нет общего названия. Однако ограниченная полнота может быть выражена в терминах других условий полноты, которые легко дуализируются (см. ниже). Хотя понятия с названиями «полный» и «ограниченный» уже были определены, путаница вряд ли возникнет, поскольку редко говорят об «ограниченном полном частично упорядоченном множестве», имея в виду «ограниченное cpo» (которое является просто «cpo с наибольшим элементом»). Аналогично, «ограниченная полная решетка» почти недвусмысленна, поскольку не указывают свойство ограниченности для полных решеток, где оно в любом случае подразумевается. Также обратите внимание, что пустое множество обычно имеет верхние границы (если частично упорядоченное множество непустое), и, таким образом, ограниченно-полное частично упорядоченное множество имеет наименьший элемент.
Можно также рассмотреть подмножества частично упорядоченного множества, которые полностью упорядочены , т.е. цепи . Если все цепи имеют супремум, порядок называется цепочечно полным . Опять же, эта концепция редко требуется в двойственной форме.
Уже было отмечено, что бинарные meets/joins дают все непустые конечные meets/joins. Аналогично, многие другие (комбинации) вышеуказанных условий эквивалентны.
Как объяснялось выше, наличие определенных условий полноты позволяет рассматривать формирование определенных супремумов и инфимумов как полные операции частично упорядоченного множества. Оказывается, во многих случаях можно охарактеризовать полноту, рассматривая только соответствующие алгебраические структуры в смысле универсальной алгебры , которые снабжены операциями типа или . Налагая дополнительные условия (в форме подходящих тождеств ) на эти операции, можно затем действительно вывести лежащий в основе частичный порядок исключительно из таких алгебраических структур. Подробности этой характеризации можно найти в статьях о «решетчатых» структурах, для которых это обычно рассматривается: см. полурешетка , решетка , алгебра Гейтинга и булева алгебра . Обратите внимание, что последние две структуры расширяют применение этих принципов за пределы простых требований полноты, вводя дополнительную операцию отрицания .
Другой интересный способ характеризовать свойства полноты обеспечивается с помощью концепции (монотонных) связей Галуа , т.е. присоединений между частичными порядками. Фактически, этот подход предлагает дополнительные сведения как о природе многих свойств полноты, так и о важности связей Галуа для теории порядка. Общее наблюдение, на котором основана эта переформулировка полноты, заключается в том, что построение определенных супремумов или инфимумов обеспечивает левые или правые присоединенные части подходящих связей Галуа.
Рассмотрим частично упорядоченное множество ( 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 ) (downset-решетку). Более того, существует очевидное вложение e : X → D ( X ), которое отображает каждый элемент x из X в его главный идеал { y в X | y ≤ x }. Небольшое размышление теперь показывает, что e имеет нижний сопряженный элемент тогда и только тогда, когда X является полной решеткой. Фактически, этот нижний сопряженный элемент отобразит любое нижнее множество X в его супремум в X . Составляя этот нижний сопряженный элемент с функцией, которая отображает любое подмножество X в его нижнее замыкание (снова дополнение для включения нижних множеств в powerset ), мы получаем обычное отображение супремума из powerset 2 X в X . Как и прежде, другая важная ситуация возникает всякий раз, когда это отображение супремума также является верхним сопряженным: в этом случае полная решетка X конструктивно вполне дистрибутивна . См. также статьи о полной дистрибутивности и дистрибутивности (теория порядка) .
Рассмотрения в этом разделе предполагают переформулирование (частей) теории порядка в терминах теории категорий , где свойства обычно выражаются путем ссылки на отношения ( морфизмы , более конкретно: присоединения) между объектами, вместо рассмотрения их внутренней структуры. Более подробные рассмотрения этих отношений см. в статье о категориальной формулировке теории порядка.
