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

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

Заказать вложения и пополнения решетки

( Частично упорядоченный набор poset) состоит из набора элементов вместе с бинарным отношением $x \leq y$ на парах элементов, которое является рефлексивным ( $x \leq x$ для каждого x ), транзитивным (если $x \leq y$ и $y \leq z,$ то $x \leq z$ ) и антисимметричным (если выполняются оба $x ⩽ y$ и $y ⩽ x$ , то $x = y$ ). Этим свойствам удовлетворяет обычный числовой порядок целых или действительных чисел; однако, в отличие от упорядочения чисел, частичный порядок может иметь два несравнимых элемента : ни $x \leq y,$ ни $y \leq x$ не соблюдаются. Другой знакомый пример частичного упорядочения — порядок включения ⊆ на парах множеств. ^[2]

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

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

Определение

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

(А в) л = А

;

оно упорядочено включением: $A ⩽ B$ в пополнение тогда и только тогда, когда $A \subseteq B$ как множества. ^[7]

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

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

Согласно альтернативному определению, операции соединения и встречи полной решетки имеют симметричные описания: если $(A i, B i)$ являются разрезами в любом семействе разрезов, то соединение этих разрезов является разрезом $(L, L в),$ где $L = \cap i A i$ , а соединение представляет собой разрез $(U л, U)$ где $U знак равно \cap я B я$ . ^[9]

Примеры

Если $\mathbb {Q}$ – это набор рациональных чисел , рассматриваемый как полностью упорядоченный набор с обычным числовым порядком, тогда каждый элемент пополнения Дедекинда – МакНила $\mathbb {Q}$ можно рассматривать как разрез Дедекинда и завершение Дедекинда-МакНила. $\mathbb {Q}$ — это общий порядок действительных чисел вместе с двумя дополнительными значениями $\pm \infty$ . ^[10]

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

Если $O$ — любой конечный набор объектов, а $A$ — любой конечный набор унарных атрибутов для объектов в $O$ , то можно сформировать частичный порядок высоты два, в котором элементами частичного порядка являются объекты и атрибуты, и в где $x \leq y$ , когда $x$ — объект с атрибутом $y$ . Дедекинда – МакНила $Для частичного порядка, определенного таким образом, пополнение S$ известно как решетка понятий и играет центральную роль в области анализа формальных понятий . ^[12]

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

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

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

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

Пополнение Дедекинда – МакНила самодвойственно: пополнение двойственного частичному порядку то же самое, что и пополнение двойственного пополнения. ^[18]

Пополнение Дедекинда – МакНила $S$ имеет ту же порядковую размерность , что и $S.$ само ^[19]

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

Алгоритмы

Несколько исследователей исследовали алгоритмы построения пополнения Дедекинда – МакНила конечного частично упорядоченного множества. Пополнение Дедекинда – МакНила может быть экспоненциально больше, чем частичный порядок, из которого оно получено: ^[12] и временные ограничения для таких алгоритмов обычно устанавливаются с учетом выходных данных и зависят как от количества $n$ элементов входного частичного порядка, так и от количества $c$ элементов его завершения.

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

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

Как отмечают Журдан, Рэмпон и Жард (1994) , проблему перечисления всех разрезов в частично упорядоченном множестве можно сформулировать как частный случай более простой задачи — перечисления всех максимальных антицепей в другом частично упорядоченном множестве. Если $P$ частично упорядоченное множество, пусть $Q$ — частичный порядок, элементы которого содержат две копии $P$ : для каждого элемента $x$ из $P$ Q $— любое$ содержит два элемента $x 0$ и $x 1$ , причем $x i < y j$ тогда и только тогда, когда $x < y$ и $я < j$ . Тогда разрезы в $P$ взаимно однозначно соответствуют максимальным антицепям в $Q$ : элементы нижнего множества разреза соответствуют элементам с индексом 0 в антицепи, а элементы верхнего множества разреза соответствуют элементам элементы с индексом 1 в антицепи. Журдан и др. описать алгоритм поиска максимальных антицепей, который при применении к задаче перечисления всех разрезов в $P$ занимает время $O (c (nw + w 3))$ , улучшение алгоритма Гантера и Кузнецова (1998), когда ширина $w$ мала. ^[21] Альтернативно, максимальная антицепь в $Q$ — это то же самое, что максимальное независимое множество в графе сравнимости Q $к$ или максимальная клика в дополнении графа сравнимости, поэтому алгоритмы проблемы клики или проблемы независимого множества также могут быть применены эта версия проблемы пополнения Дедекинда – МакНила. ^[22]

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

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

Примечания

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

Ссылки

Банашевский, Б.; Брунс, Г. (1967), «Категорическая характеристика пополнения МакНила», Archiv der Mathematik , 18 (4): 369–377, doi : 10.1007/BF01898828 , MR 0221984 , S2CID 121216988 .
Биркгоф, Гарретт (1995), «VI.9 Завершение путем разрезов», Теория решетки , Публикации коллоквиума, том. 25 (3-е изд.), Американское математическое общество, стр. 126–128, ISBN. 978-0-8218-1025-5 .
Бишоп, Алан А. (1978), «Универсальная характеристика пополнения путем разрезов», Algebra Universalis , 8 (3): 349–353, doi : 10.1007/bf02485405 , MR 0469839 , S2CID 121624631 .
Кэмерон, Кэти (1985), «Антицепные последовательности», Order , 2 (3): 249–255, doi : 10.1007/BF00333130 , MR 0824698
Котлар, Миша (1944), «Метод построения структур и его применение к топологическим пространствам и абстрактной арифметике», Univ. Нак. Тукуман. Ревиста А. , 4 : 105–157, МР 0014062 .
Дэйви, бакалавр; Пристли, Хилари А. (2002), «7.38 Пополнение Дедекинда – МакНила» , Введение в решетки и порядок (2-е изд.), Cambridge University Press , стр. 166, ISBN 978-0-521-78451-1 , Збл 1002.06001 .
Фунаяма, Неносукэ (1944), «О дополнении разрезами распределительных решеток», Труды Императорской академии, Токио , 20 : 1–2, doi : 10.3792/pia/1195573210 , MR 0014063 , Zbl 0063.01484 .
Габбай, Дов М .; Шехтман, Валентин; Скворцов, Дмитрий (2009), «3.4.12 Пополнение Дедекинда – МакНила оставшейся решетки», Квантование в неклассической логике, Том 1 , Исследования по логике и основам математики, том. 153, Elsevier, стр. 177–178, ISBN. 978-0-444-52012-8 , Збл 1211.03002 .
Гантер, Бернхард; Кузнецов, Сергей О. (1998), «Поэтапное построение заканчивания Дедекинда-МакНила», Учеб. 6-й Межд. Конф. Концептуальные структуры: теория, инструменты и приложения (ICCS98) , Конспекты лекций по информатике, том. 1453, Springer-Verlag, стр. 295–302, doi : 10.1007/BFb0054922 , MR 1673860 , Zbl 0928.06004 .
Журдан, Ги-Винсент; Рэмпон, Жан-Ксавье; Жард, Клод (1994), «Онлайн-вычисление решетки максимальных антицепей частично упорядоченных множеств» (PDF) , Order , 11 (3): 197–210, doi : 10.1007/BF02115811 , MR 1308475 , S2CID 120755660 , Zbl 0814.06004 .
МакНил, HM (1937), «Частично упорядоченные множества», Труды Американского математического общества , 42 (3): 416–460, doi : 10.2307/1989739 , JFM 63.0833.04 , JSTOR 1989739 , MR 1501929 , Zbl 0017.339 04 .
Нурин, Луари; Рейно, Оливье (1999), «Быстрый алгоритм построения решеток», Information Processing Letters , 71 (5–6): 199–204, CiteSeerX 10.1.1.502.3181 , doi : 10.1016/S0020-0190(99)00108- 8 , МР 1726978 , Збл 0998.06005 .
Нурин, Луари; Рейно, Оливье (2002), «Быстрый инкрементный алгоритм построения решеток», Журнал экспериментального и теоретического искусственного интеллекта , 14 (2): 217–227, doi : 10.1080/09528130210164152 , S2CID 38160433 , Zbl 1022.68027 .
Новак, Витезслав (1969), «О свойстве оболочки Дедекинда-МакНила», Mathematical Annals , 179 : 337–342, doi : 10.1007/BF01350778 , MR 0240010 , S2CID 120963245 .
О'Лири, Майкл Л. (2015), Первый курс математической логики и теории множеств , John Wiley & Sons, стр. 276, ISBN 978-0-470-90588-3
Роман, Стивен (2007), Продвинутая линейная алгебра , Тексты для выпускников по математике, том. 135 (3-е изд.), Springer, стр. 10–11, ISBN. 978-0-387-72831-5
Шмидт, Юрген (1956), «Об идентификации оболочки Дедекинда-МакНила упорядоченной оболочки», Архив математики (на немецком языке), 7 : 241–249, doi : 10.1007/BF01900297 , MR 0084484
Шредер, Бернд С.В. (2003), «5.3 Вложения/Пополнение Дедекинда/МакНила», Упорядоченные множества: Введение , Birkhäuser, стр. 119–122, ISBN 978-1-4612-6591-7 .

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

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

[FOOTNOTERoman2007-2] Роман (2007) .

[3] Шредер (2003) , определение 5.3.1, с. 119.

[FOOTNOTEO'Leary2015-4] О'Лири (2015) .

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

[smallest-completion-6] Jump up to: ^а ^б Бишоп (1978) ; Шредер (2003) , Теорема 5.3.8, с. 121.

[def-7] Jump up to: ^а ^б Макнейл (1937) , лемма 11.8, с. 444; Дэйви и Пристли (2002) , лемма 3.9(i), с. 166.

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

[FOOTNOTEMacNeille1937-9] Jump up to: ^а ^б МакНил (1937) .

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

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

[FOOTNOTEGanterKuznetsov1998-12] Jump up to: ^а ^б ^с ^д Ganter & Kuznetsov (1998) .

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

[FOOTNOTESchmidt1956-14] Шмидт (1956) .

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

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

[17] Пары (1944) ; Фунаяма (1944) .

[FOOTNOTEBirkhoff1995-18] Биркгоф (1995) .

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

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

[FOOTNOTEJourdanRamponJard1994-21] Журдан, Рэмпон и Жард (1994) .

[22] Об эквивалентности алгоритмов для антицепей в частичных порядках и независимых множеств в графах сравнимости см. Cameron (1985) , p. 251.

[FOOTNOTENourineRaynaud2002-23] Нурин и Рейно (2002) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]