Завершение Дедекинда – МакНила - Dedekind–MacNeille completion

В Диаграмма Хассе частично упорядоченного множества (слева) и его пополнение Дедекинда – МакНейля (справа).

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

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

А частично заказанный набор (посет) состоит из набор элементов вместе с бинарное отношение $Икс \leq у$ на парах элементов, то есть рефлексивный ( $Икс \leq Икс$ для каждого Икс), переходный (если $Икс \leq у$ и $у \leq z$ тогда $Икс \leq z$ ), и антисимметричный (если оба $Икс \leq у$ и $у \leq Икс$ подожди, тогда $Икс = у$ ). Обычный числовой порядок на целые числа или действительные числа удовлетворяют этим свойствам; однако, в отличие от порядков номеров, частичный порядок может иметь два элемента, которые несравненный: ни один $Икс \leq у$ ни $у \leq Икс$ держит. Еще один знакомый пример частичного упорядочивания - это включение упорядочение ⊆ на парах множеств.

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

Данный частично упорядоченный набор может иметь несколько различных дополнений. Например, одно завершение любого частично упорядоченного набора $S$ это набор его закрытые вниз подмножества заказан включение. $S$ вкладывается в эту (полную) решетку, отображая каждый элемент $Икс$ к нижнему набору элементов, которые меньше или равны $Икс$ . В результате распределительная решетка и используется в Теорема Биркгофа о представлении. Однако в нем может быть намного больше элементов, чем необходимо для завершения $S$ .^[3] Среди всех возможных пополнений решетки пополнение Дедекинда – МакНейля - это наименьшая полная решетка с $S$ встроен в него.^[4]

Определение

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

(А ты) л = А

;

заказывается включением: $А \leq B$ в завершении тогда и только тогда, когда $А \subseteq B$ ресурсы.

Элемент $Икс$ из $S$ встраивается в завершение как его главный идеал, набор $↓ Икс$ элементов меньше или равных $Икс$ . потом $(↓ Икс) ты$ набор элементов больше или равных $Икс$ , и $((↓ Икс) ты) л = ↓ Икс$ , показывая, что $↓ Икс$ действительно является членом завершения.^[5] Несложно проверить, что отображение из $Икс$ к $↓ Икс$ это вложение порядка.

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

При альтернативном определении операции соединения и встречи полной решетки имеют симметричные описания: если $(А я, B я)$ разрезы в любом семействе разрезов, то пересечение этих разрезов - это разрез $(L, L ты)$ куда $L = \cap я А я$ , а соединение - это разрез $(U л, U)$ куда $U = \cap я B я$ .

Примеры

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

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

Если $О$ - любой конечный набор объектов, и $А$ любой конечный набор унарных атрибутов для объектов в $О$ , то можно сформировать частичный порядок высоты два, в котором элементами частичного порядка являются объекты и атрибуты, а в котором $Икс \leq у$ когда $Икс$ это объект с атрибутом $у$ . Для частичного порядка, определенного таким образом, завершение Дедекинда – МакНейля $S$ известен как решетка понятий, и он играет центральную роль в области формальный анализ концепции.

Характеристики

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

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

Завершение Дедекинда – МакНила Булева алгебра это полная булева алгебра; этот результат известен как Теорема Гливенко – Стоуна., после Валерий Иванович Гливенко и Маршалл Стоун.^[10] Аналогичным образом завершение Дедекинда – МакНейля остаточная решетка полная решетка с делениями.^[11] Однако завершение распределительная решетка не обязательно сам по себе быть распределительным, и завершение модульная решетка могут не оставаться модульными.^[12]

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

Завершение Дедекинда – МакНила $S$ имеет то же самое размер заказа так же как и $S$ сам.^[14]

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

Алгоритмы

Несколько исследователей исследовали алгоритмы построения пополнения Дедекинда – МакНейля конечного частично упорядоченного множества. Поскольку завершение Дедекинда – МакНейла может быть экспоненциально больше, чем частичный порядок, из которого оно происходит,^[16] необходимо измерить временные рамки для таких алгоритмов как с точки зрения количества $п$ элементов входного частичного порядка, но и по количеству $c$ элементов его завершения, а иногда и с точки зрения дополнительных мер сложности ввода и вывода. Формат, в котором представлена выходная решетка, также может влиять на время работы алгоритмов ее построения; например, если он представлен как логическая матрица определяя результат сравнения между каждой парой элементов решетки, размер вывода равен $Θ (c 2)$ и это будет нижняя граница времени для алгоритма построения.

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

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

В качестве Журдан, Рэмпон и Джард (1994) Обратите внимание, что задача перечисления всех разрезов в частично упорядоченном множестве может быть сформулирована как частный случай более простой задачи перечисления всех максимальных антицепи в другом частично упорядоченном наборе. Если $п$ - любое частично упорядоченное множество, пусть $Q$ частичный порядок, элементы которого содержат две копии $п$ : для каждого элемента $Икс$ из $п$ , $Q$ содержит два элемента $Икс 0$ и $Икс 1$ , с $Икс я < у j$ если и только если $Икс < у$ и $я < j$ . Затем порезы в $п$ взаимно однозначно соответствуют максимальным антицепям в $Q$ : элементы в нижнем наборе разреза соответствуют элементам с индексом 0 в антицепи, а элементы в верхнем наборе разреза соответствуют элементам с индексом 1 в антицепи. Jourdan et al. описать алгоритм поиска максимальных антицепей, который применительно к задаче перечисления всех разрезов в $п$ , требуется время $О (c (nw + ш 3))$ , улучшение алгоритма Гантер и Кузнецов (1998) когда ширина $ш$ маленький. В качестве альтернативы максимальная антицепь в $Q$ это то же самое, что и максимальное независимое множество в график сопоставимости из $Q$ , или максимальная клика в дополнение к графу сопоставимости, поэтому алгоритмы для проблема клики или проблема независимого множества также может быть применена к этой версии проблемы завершения Дедекинда – МакНейля.

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

В переходная редукция или покрывающий граф завершения Дедекинда – МакНейля кратко описывает отношение порядка между его элементами: каждый сосед разреза должен удалить элемент исходного частичного порядка из верхнего или нижнего множества разреза, так что каждая вершина имеет не более $п$ соседи. Таким образом, покрывающий граф имеет $c$ вершины и самое большее $сп /2$ соседей, число, которое может быть намного меньше, чем $c 2$ записи в матрице, определяющей все попарные сравнения между элементами. Нурин и Рейно показать, как эффективно вычислить этот покрывающий граф; в более общем смысле, если $B$ - любое семейство множеств, они показывают, как вычислить покрывающий граф решетки объединений подмножеств $B$ . В случае решетки Дедекинда – МакНейля $B$ может считаться семьей комплекты дополнений главных идеалов, и объединение подмножеств $B$ являются дополнениями нижних наборов разрезов. Основная идея их алгоритма - генерировать объединения подмножеств $B$ постепенно (для каждого набора в $B$ , образуя его объединение со всеми ранее сгенерированными объединениями), представляют собой получившееся семейство множеств в три, и используйте представление trie для проверки определенных пар-кандидатов множеств на смежность в покрывающем отношении; это требует времени $О (сп 2)$ . В более поздних работах те же авторы показали, что алгоритм можно сделать полностью инкрементным (с возможностью добавления элементов в частичный порядок по одному) с той же общей временной границей.^[17]

Примечания

^ Дэйви и Пристли (2002), п. 166); Зигфрид и Шредер (2003 г., п. 119).
^ Зигфрид и Шредер (2003), определение 5.3.1, п. 119.
^ Карпинето, Клаудио; Романо, Джованни (2004), Концептуальный анализ данных: теория и приложения, Джон Уайли и сыновья, стр. 10, ISBN 978-0-470-85055-8.
^ ^а ^б Епископ (1978); Зигфрид и Шредер (2003), Теорема 5.3.8, с. 121.
^ Макнейл (1937), Лемма 11.8, с. 444; Дэйви и Пристли (2002), Лемма 3.9 (i), с. 166.
^ Это определение первоначально использовалось Макнейл (1937), например.
^ Дэйви и Пристли (2002), Пример 7.44 (1), с. 168; Зигфрид и Шредер (2003), Пример 5.3.3 (2), с. 120.
^ Дэйви и Пристли (2002), Пример 7.44 (2), с. 168.
^ Зигфрид и Шредер (2003), Предложение 5.3.7, с. 121.
^ Биркгоф (1995), Теорема 27, с. 130.
^ Габбай, Шехтман и Скворцов (2009).
^ Котлар (1944); Фунаяма (1944).
^ Биркгоф (1995).
^ Этот результат часто связывают с неопубликованной дипломной работой Гарвардского университета 1961 года К. А. Бейкера «Размерность, независимость от соединений и широта в частично упорядоченных множествах». Это было опубликовано Новак (1969).
^ Банашевски и Брунс (1967).
^ Гантер и Кузнецов (1998).
^ Нурин и Рейно (2002).

внешняя ссылка

[1] Дэйви и Пристли (2002), п. 166); Зигфрид и Шредер (2003 г., п. 119).

[2] Зигфрид и Шредер (2003), определение 5.3.1, п. 119.

[3] Карпинето, Клаудио; Романо, Джованни (2004), Концептуальный анализ данных: теория и приложения, Джон Уайли и сыновья, стр. 10, ISBN 978-0-470-85055-8.

[smallest-completion-4] а ^б Епископ (1978); Зигфрид и Шредер (2003), Теорема 5.3.8, с. 121.

[5] Макнейл (1937), Лемма 11.8, с. 444; Дэйви и Пристли (2002), Лемма 3.9 (i), с. 166.

[6] Это определение первоначально использовалось Макнейл (1937), например.

[7] Дэйви и Пристли (2002), Пример 7.44 (1), с. 168; Зигфрид и Шредер (2003), Пример 5.3.3 (2), с. 120.

[8] Дэйви и Пристли (2002), Пример 7.44 (2), с. 168.

[9] Зигфрид и Шредер (2003), Предложение 5.3.7, с. 121.

[10] Биркгоф (1995), Теорема 27, с. 130.

[11] Габбай, Шехтман и Скворцов (2009).

[12] Котлар (1944); Фунаяма (1944).

[13] Биркгоф (1995).

[14] Этот результат часто связывают с неопубликованной дипломной работой Гарвардского университета 1961 года К. А. Бейкера «Размерность, независимость от соединений и широта в частично упорядоченных множествах». Это было опубликовано Новак (1969).

[15] Банашевски и Брунс (1967).

[16] Гантер и Кузнецов (1998).

[17] Нурин и Рейно (2002).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]