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

В математической области теории порядка, полнота properties подтверждают существование определенной infima или suprema данного частично упорядоченного набора (poset). Самый известный пример - это полнота вещественных чисел. Специальное использование этого термина относится к полным частичным заказам или полным решеткам. Однако существует много других интересных представлений о полноте.

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

• 1 Типы свойств полноты
  • 1.1 Наименьшие и наибольшие элементы
  • 1.2 Конечная полнота
  • 1.3 Дополнительные условия полноты
• 2 Взаимосвязи между свойствами полноты
• 3 Полнота с точки зрения универсальности алгебра
• 4 Полнота в терминах дополнений
• 5 См. также
• 6 Примечания
• 7 Ссылки

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

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

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

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

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

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

ЧУМ, в котором известно о существовании только непустых конечных супремумов, поэтому называется полурешёткой соединения. Двойственное понятие - это встреча-полурешетка.

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

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

Если все направленные подмножества из poset имеют верхнюю грань, то порядок является направленно-полным частичным порядком (dcpo). Это особенно важно в предметной области. Редко рассматриваемое двойственное понятие для dcpo - это отфильтрованный полный poset. Dcpos с наименьшим элементом ("заостренные dcpos") - одно из возможных значений фразы полный частичный порядок (cpo).

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

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

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

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

ЧУМ является цепно полным тогда и только тогда, когда оно является ДЦПО.

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

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

Рассмотрим частично упорядоченный набор (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 X, заданная формулой q (x) = (x, x). Естественно, предполагаемое отношение упорядочения для X x X - это просто обычный заказ продукта. q имеет нижний сопряженный q тогда и только тогда, когда все бинарные соединения в X существуют. И наоборот, операция соединения $\vee \; \{\backslash \; displaystyle\; \backslash \; vee\}$: X x X → X всегда может предоставить (обязательно уникальный) нижний сопряженный элемент для q. Двойственно q допускает верхний сопряженный элемент тогда и только тогда, когда X имеет все двоичные пересечения. Таким образом, операция встречи $\wedge \; \{\backslash \; displaystyle\; \backslash \; wedge\}$, если она существует, всегда является верхним сопряженным элементом. Если существуют оба $\vee \; \{\backslash \; displaystyle\; \backslash \; vee\}$и $\wedge \; \{\backslash \; displaystyle\; \backslash \; wedge\}$и, кроме того, $\wedge \; \{\backslash \; displaystyle\; \backslash \; wedge\; \}$также является нижним сопряженным, тогда ч.у. X является алгеброй Гейтинга - другим важным специальным классом частичных порядков.

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

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

• Функция сохранения пределов при сохранении существующих верхних и нижних пределов.
• Общий порядок

.

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