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

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

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

Частично упорядоченное множество ( посет) состоит из множества элементов вместе с бинарным отношением x ≤ y на парах элементов, которое является рефлексивным ( x ≤ x для каждого x ), транзитивным (если x ≤ y и y ≤ z , то x ≤ z ) и антисимметричным (если оба x ≤ y и y ≤ x выполняются, то x = y ). Обычные числовые упорядочения на целых или действительных числах удовлетворяют этим свойствам; однако, в отличие от упорядочений на числах, частичный порядок может иметь два элемента, которые несравнимы : ни x ≤ y , ни y ≤ 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 u обозначает множество верхних границ A ; то есть элемент x из S принадлежит A u всякий раз, когда x больше или равен каждому элементу в A . Симметрично, пусть A l обозначает множество нижних границ A , элементов, которые меньше или равны каждому элементу в A . Тогда пополнение Дедекинда–МакНейла S состоит из всех подмножеств A , для которых

( А у ) л = А ;

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

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

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

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

Примеры

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

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

Если O — любой конечный набор объектов, а A — любой конечный набор унарных атрибутов для объектов в O , то можно сформировать частичный порядок высоты два, в котором элементами частичного порядка являются объекты и атрибуты, и в котором x ≤ 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]

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

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

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

Примечания

  1. ^ Дэйви и Пристли (2002, стр. 166); Шредер (2003, стр. 119).
  2. ^ Роман (2007).
  3. ^ Шредер (2003), определение 5.3.1, с. 119.
  4. ^ О'Лири (2015).
  5. ^ Карпинето, Клаудио; Романо, Джованни (2004), Концептуальный анализ данных: теория и приложения , John Wiley and Sons, стр. 10, ISBN 978-0-470-85055-8.
  6. ^ ab Bishop (1978); Schröder (2003), Теорема 5.3.8, стр. 121.
  7. ^ ab MacNeille (1937), Лемма 11.8, стр. 444; Davey & Priestley (2002), Лемма 3.9(i), стр. 166.
  8. ^ Это определение первоначально использовал, например, МакНейл (1937).
  9. ^ ab MacNeille (1937).
  10. ^ Дэйви и Пристли (2002), Пример 7.44(1), стр. 168; Шредер (2003), Пример 5.3.3(2), стр. 120.
  11. ^ Дэйви и Пристли (2002), Пример 7.44(2), стр. 168.
  12. ^ abcd Гантер и Кузнецов (1998).
  13. ^ Шредер (2003), Предложение 5.3.7, с. 121.
  14. ^ Шмидт (1956).
  15. ^ Биркгофф (1995), Теорема 27, стр. 130.
  16. ^ Габбай, Шехтман и Скворцов (2009).
  17. ^ Котлар (1944); Фунаяма (1944).
  18. ^ Биркгоф (1995).
  19. ^ Этот результат часто приписывается неопубликованной почетной диссертации Гарвардского университета 1961 года К. А. Бейкера «Размерность, независимость от объединения и ширина в частично упорядоченных множествах». Она была опубликована Новаком (1969).
  20. ^ Банашевски и Брунс (1967).
  21. ^ Журдан, Рэмпон и Жард (1994).
  22. ^ Об эквивалентности алгоритмов для антицепей в частичных порядках и для независимых множеств в графах сравнимости см. Cameron (1985), стр. 251.
  23. ^ Нурин и Рейно (2002).

Ссылки

  • Банашевски, Б.; Брунс, Г. (1967), «Категорическая характеристика пополнения Макнейла», Archiv der Mathematik , 18 (4): 369– 377, doi :10.1007/BF01898828, MR  0221984, S2CID  121216988.
  • Биркгофф, Гарретт (1995), «VI.9 Завершение с помощью разрезов», Теория решеток, Colloquium Publications, т. 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. Nac. Tucumán. Revista A. , 4 : 105–157 , MR  0014062.
  • Дэйви, BA; Пристли, Хилари А. (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) , Lecture Notes in Computer Science, т. 1453, Springer-Verlag, стр.  295–302 , doi :10.1007/BFb0054922, MR  1673860, Zbl  0928.06004.
  • Jourdan, Guy-Vincent; Rampon, Jean-Xavier; Jard, Claude (1994), "Вычисление решетки максимальных антицепей частично упорядоченных множеств в режиме онлайн" (PDF) , Order , 11 (3): 197– 210, doi :10.1007/BF02115811, MR  1308475, S2CID  120755660, Zbl  0814.06004.
  • MacNeille, HM (1937), «Частично упорядоченные множества», Transactions of the American Mathematical Society , 42 (3): 416– 460, doi : 10.2307/1989739 , JFM  63.0833.04, JSTOR  1989739, MR  1501929, Zbl  0017.33904.
  • Нурин, Лхуари; Рейно, Оливье (1999), «Быстрый алгоритм построения решеток», Information Processing Letters , 71 ( 5– 6): 199– 204, CiteSeerX  10.1.1.502.3181 , doi :10.1016/S0020-0190(99)00108-8, MR  1726978, Zbl  0998.06005.
  • Нурин, Льюари; Рейно, Оливье (2002), «Быстрый инкрементальный алгоритм для построения решеток», Журнал экспериментального и теоретического искусственного интеллекта , 14 (2): 217– 227, doi : 10.1080/09528130210164152, S2CID  38160433, Zbl  1022.68027.
  • Новак, Витезслав (1969), «Über eine Eigenschaft der Dedekind-MacNeilleschen Hülle», Mathematische Annalen , 179 : 337–342 , doi : 10.1007/BF01350778, MR  0240010, S2CID  120963245.
  • О'Лири, Майкл Л. (2015), Первый курс математической логики и теории множеств, John Wiley & Sons, стр. 276, ISBN 978-0-470-90588-3
  • Роман, Стивен (2007), Продвинутая линейная алгебра, Graduate Texts in Mathematics, т. 135 (3-е изд.), Springer, стр.  10–11 , ISBN 978-0-387-72831-5
  • Шмидт, Юрген (1956), «Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Hülle», Archiv der Mathematik (на немецком языке), 7 : 241–249 , doi : 10.1007/BF01900297, MR  0084484
  • Шредер, Бернд С.В. (2003), «5.3 Вложения/Пополнение Дедекинда/МакНила», Упорядоченные множества: Введение, Birkhäuser, стр.  119–122 , ISBN 978-1-4612-6591-7.
  • Завершение МакНейла в PlanetMath
  • Завершение МакНейла в n Lab
Взято с "https://en.wikipedia.org/w/index.php?title=Dedekind–MacNeille_completion&oldid=1194892042"