Завершение Дедекинда – МакНейла

редактировать
Наименьшая полная решетка, содержащая частично упорядоченный набор Диаграмма Хассе частично упорядоченного набора (слева) и ее завершение Дедекинда – МакНейла (справа).

В математике, в частности теории порядка, завершение Дедекинда – МакНейла частично упорядоченного набора (также называется завершением по разрезам или нормальным завершением ) - это наименьшая полная решетка, которая ее содержит. Он назван в честь Холбрука Манна МакНейла, чья статья 1937 года впервые определила и построила его, и в честь Ричарда Дедекинда, потому что его конструкция обобщает Дедекиндовские разрезы, используемые Дедекиндом для построения действительные числа из рациональных чисел.

Содержание

  • 1 Порядок внедрения и завершения решетки
  • 2 Определение
  • 3 Примеры
  • 4 Свойства
  • 5 Алгоритмы
    • 5.1 Построение множества разрезов
    • 5.2 Построение покрывающего графа
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

Порядковые вложения и дополнения решетки

A частично упорядоченный набор ( poset) состоит из набора элементов вместе с двоичным отношением x ≤ y на парах элементов, которое является рефлексивным (x ≤ x для каждого x), транзитивный (если x ≤ y и y ≤ z, то x ≤ z) и антисимметричный (если выполняются оба x ≤ y и y ≤ x, то x = y). Обычный числовой порядок в целых или действительных числах удовлетворяет этим свойствам; однако, в отличие от порядков чисел, частичный порядок может иметь два несравнимых элемента: ни x ≤ y, ни y ≤ x не выполняется. Другой известный пример частичного упорядочения - это включение упорядочение ⊆ на парах множеств.

Если S является частично упорядоченным множеством, завершение S означает полную решетку L с упорядоченным вложением S в L. Понятие полной решетка означает, что каждое подмножество элементов L имеет точную нижнюю грань и верхнюю грань ; это обобщает аналогичные свойства действительных чисел. Понятие упорядоченного вложения требует, чтобы различные элементы S отображались в разные элементы L и чтобы каждая пара элементов в S имела такой же порядок в L, как и в S. Расширенное вещественное число числовая строка (действительные числа вместе с + ∞ и −∞) является дополнением в этом смысле рациональных чисел: набор рациональных чисел {3, 3.1, 3.14, 3.141, 3.1415, 3.14159,...} действительно не имеет рациональной наименьшей верхней границы, но в вещественных числах имеет наименьшую верхнюю границу π.

Данный частично упорядоченный набор может иметь несколько различных завершений. Например, одним завершением любого частично упорядоченного набора S является набор его закрытых вниз подмножеств, упорядоченных по включению. S вкладывается в эту (полную) решетку, отображая каждый элемент x в нижний набор элементов, которые меньше или равны x. Результатом является дистрибутивная решетка, которая используется в теореме представления Биркгофа. Однако в нем может быть намного больше элементов, чем необходимо для формирования пополнения S. Среди всех возможных пополнений решетки пополнение Дедекинда – МакНейла является наименьшей полной решеткой со встроенной в нее S.

Определение

Для каждого подмножества A частично упорядоченного множества S пусть A обозначает набор верхних границ A; то есть элемент x из S принадлежит A всякий раз, когда x больше или равен каждому элементу в A. Симметрично, пусть A обозначает набор нижних границ A, элементы, которые меньше или равны каждому элементу в A.Тогда пополнение Дедекинда – МакНейля S состоит из всех подмножеств A, для которых

(A) = A;

оно упорядочено включением: A ≤ B в пополнении тогда и только тогда, когда A ⊆ B как множества.

Элемент x из S вкладывается в завершение как его главный идеал, набор ↓ x элементов, меньших или равных x. Тогда (↓ x) - это набор элементов, больших или равных x, и ((↓ x)) = ↓ x, показывая, что ↓ x действительно является членом завершения. Несложно проверить, что отображение x в ↓ x является упорядоченным вложением.

Иногда используется альтернативное определение завершения Дедекинда – МакНейла, которое больше напоминает определение разреза Дедекинда. В частично упорядоченном множестве S определите разрез как пару множеств (A, B), для которых A = B и A = B. Если (A, B) - разрез, то A удовлетворяет уравнению (A) = A, и наоборот, если (A) = A, то (A, A) разрез. Следовательно, набор разрезов, частично упорядоченный включением в нижнем множестве разреза (или обратном отношению включения в верхнем множестве), дает эквивалентное определение пополнения Дедекинда – МакНейла.

Согласно альтернативному определению, обе операции соединения и пересечения полной решетки имеют симметричное описание: если (A i,Bi) - разрезы в любом семействе разрезов, то пересечение этих разрезов будет cut (L, L), где L = ∩ iAi, а соединение - это разрез (U, U), где U = ∩ iBi.

Примеры

Если Q - это множество рациональных чисел, рассматриваемых как полностью упорядоченный набор с обычным числовым порядком, то каждый элемент завершения Дедекинда – МакНейля Q может рассматриваться как разрез Дедекинда, а завершение Дедекинда – МакНейла Q - это полное упорядочение по действительным числам вместе с двумя дополнительными значениями ± ∞. Построение действительных чисел из рациональных чисел является примером завершения Дедекинда для полностью упорядоченного множества, а завершение Дедекинда – МакНейла обобщает эту концепцию от полных порядков до частичных порядков.

Если S является антицепью (набором элементов, два из которых не сопоставимы), то завершение S Дедекинда – МакНила состоит из самого S вместе с двумя дополнительными элементами, нижним элементом который находится под каждым элементом в S и верхний элемент, который находится над каждым элементом в S.

Если O - любой конечный набор объектов, а A - любой конечный набор унарных атрибутов для объектов в O, то можно сформировать частичный порядок высоты два, в котором элементами частичного порядка являются объекты и атрибуты, и в котором x ≤ y, когда x является объектом, имеющим атрибут y. Для частичного порядка, определенного таким образом, завершение S Дедекинда – МакНейла известно как решетка понятий, и оно играет центральную роль в области анализа формальных понятий.

Свойства

Пополнение Дедекинда – МакНейля частично упорядоченного множества S - это наименьшая полная решетка, в которую вложено S, в том смысле, что, если L - любое решеточное пополнение S, то пополнение Дедекинда – МакНейля является частично упорядоченное подмножество L. Когда S конечно, его пополнение также конечно и имеет наименьшее число элементов среди всех конечных полных решеток, содержащих S.

Частично упорядоченное множество S плотно соединено и плотно на пересечении в завершении Дедекинда – МакНейла; то есть каждый элемент пополнения является объединением некоторого набора элементов S, а также является пересечением некоторого набора элементов в S. Пополнение Дедекинда – МакНейла характеризуется среди пополнений S этим свойством.

Пополнение Дедекинда – МакНейля булевой алгебры является полной булевой алгеброй ; этот результат известен как теорема Гливенко – Стоуна после Валерия Ивановича Гливенко и Маршалла Стоуна. Точно так же пополнение Дедекинда – МакНейля решетки с вычетом является полной решеткой с вычетом. Однако завершение распределительной решетки само по себе не обязательно должно быть распределительным, и завершение модульной решетки может не оставаться модульным.

Завершение Дедекинда – МакНейла является самодвойственный: завершение двойного частичного порядка совпадает с двойным завершением.

Завершение Дедекинда – МакНила S имеет такое же измерение порядка , как и сам S.

В категории частично упорядоченных множеств и монотонных функций между частично упорядоченными множествами полные решетки образуют инъективные объекты для упорядоченных вложений, а завершение S по Дедекинду – МакНейлю является инъективной оболочкой S.

Алгоритмы

Несколько исследователей исследовали алгоритмы для построения пополнение Дедекинда – Мак-Нейля конечного частично упорядоченного множества. Поскольку завершение Дедекинда – МакНейла может быть экспоненциально больше, чем частичный порядок, из которого оно происходит, необходимо измерить временные границы для таких алгоритмов как с точки зрения количества n элементов входного частичного порядка, так и с точки зрения число c элементов его завершения, а иногда также в виде дополнительных мер сложности ввода и вывода. Формат, в котором представлена ​​выходная решетка, также может влиять на время работы алгоритмов ее построения; например, если он представлен как логическая матрица, определяющая результат сравнения между каждой парой элементов решетки, размер вывода будет (c), и это будет нижняя граница времени для алгоритм построения.

Построение набора разрезов

Гантер и Кузнецов (1998) описывают инкрементный алгоритм, в котором входной частичный порядок создается путем добавления одного элемента за раз; на каждом шаге завершение меньшего частичного заказа расширяется, чтобы сформировать завершение большего частичного заказа. В их методе завершение представлено явным списком сокращений. Каждый разрез расширенного частичного порядка, за исключением того, два набора которого пересекаются в новом элементе, является либо разрезом из предыдущего частичного порядка, либо формируется путем добавления нового элемента к одной или другой стороне разреза из предыдущего частичный порядок, поэтому их алгоритму нужны только тестовые пары наборов этой формы, чтобы определить, какие из них являются разрезами. Время использования их метода для добавления одного элемента в завершение частичного порядка составляет O (cnw), где w - ширина частичного порядка, то есть размер его наибольшей антицепи . Следовательно, время для вычисления завершения данного частичного порядка равно O (cnw) = O (cn).

Как отмечают Jourdan, Rampon Jard (1994), проблема перечисления всех разрезов в частично упорядоченном множестве может быть сформулирована как частный случай более простой задачи перечисления всех максимальных антицепи в другом частично упорядоченном наборе. Если P - любое частично упорядоченное множество, пусть Q будет частичным порядком, элементы которого содержат две копии P: для каждого элемента x из P Q содержит два элемента x 0 и x 1, с x i< yjтогда и только тогда, когда x < y and i < j. Then the cuts in P correspond one-for-one with the maximal antichains in Q: the elements in the lower set of a cut correspond to the elements with subscript 0 in an antichain, and the elements in the upper set of a cut correspond to the elements with subscript 1 in an antichain. Jourdan et al. describe an algorithm for finding maximal antichains that, when applied to the problem of listing all cuts in P, takes time O(c(nw + w)), an improvement on the algorithm of Ganter Kuznetsov (1998), когда ширина w мала. В качестве альтернативы максимальная антицепь в Q совпадает с максимальным независимым набором в графе сопоставимости Q или максимальной кликой в дополнении сопоставимости граф, поэтому алгоритмы для проблемы клики или проблемы независимого множества также могут быть применены к этой версии проблемы завершения Дедекинда – МакНейла.

Построение покрывающего графа

транзитивная редукция или покрывающий граф завершения Дедекинда – МакНейля кратко описывает отношение порядка между его элементами: каждый сосед разреза должен удалить элемент исходного частичного порядка либо из верхнего, либо из нижнего множества разреза, поэтому каждая вершина имеет не более n соседей. Таким образом, покрывающий граф имеет c вершин и не более cn / 2 соседей, число, которое может быть намного меньше, чем c элементов в матрице, определяющей все попарные сравнения между элементами. Nourine Raynaud ошибка harvtxt: нет цели: CITEREFNourineRaynaud (help ) показывает, как эффективно вычислить этот покрывающий граф; в более общем смысле, если B - это любое семейство множеств, они показывают, как вычислить покрывающий граф решетки объединений подмножеств B. В случае решетки Дедекинда – МакНейла B можно рассматривать как семейство множества дополнительных главных идеалов, а объединения подмножеств B являются дополнениями нижних множеств разрезов. Основная идея их алгоритма состоит в том, чтобы генерировать объединения подмножеств B постепенно (для каждого набора в B, формируя его объединение со всеми ранее сгенерированными объединениями), представлять полученное семейство наборов в trie и использовать представление trie для проверки определенных пар-кандидатов множеств на смежность в покрывающем отношении; требуется время O (cn). В более поздних работах те же авторы показали, что алгоритм можно сделать полностью инкрементным (с возможностью добавления элементов в частичный порядок по одному) с той же общей временной границей.

Примечания

Ссылки

Внешние ссылки

Последняя правка сделана 2021-05-17 11:00:33
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте