В математике , в частности , порядок теории , то завершение Дедекинду MacNeille из частично упорядоченного множества является наименьшим полная решетка , которая содержит его. Он назван в честь Холбрука Манна МакНейла, чья статья 1937 года впервые определила и построила его, и в честь Ричарда Дедекинда, потому что его конструкция обобщает дедекиндовские разрезы, используемые Дедекиндом для построения действительных чисел из рациональных чисел . Это также называется завершением по разрезу или нормальным завершением . [1]
Порядковые вложения и пополнения решеток
Частично упорядоченное множество (ч.у.м.) состоит из множества элементов вместе с бинарным отношением х ≤ у на паре элементов , которая является рефлексивным ( х ≤ х для каждого х ), переходного (если X ≤ у и у ≤ г , то х ≤ z ) и антисимметричным (если выполняются и x ≤ y, и y ≤ x , то x = y ). Обычный числовой порядок целых или действительных чисел удовлетворяет этим свойствам; однако, в отличие от порядков чисел, частичный порядок может иметь два несравнимых элемента : не выполняется ни x ≤ y, ни y ≤ x . Другой известный пример частичного упорядочения - это порядок включения ⊆ на парах множеств.
Если S является частично упорядоченным набор, пополнение из S означает полную решетку L с порядком-вложениями из S в L . [2] Понятие полной решетки означает, что каждое подмножество элементов L имеет точную нижнюю грань и супремум ; это обобщает аналогичные свойства действительных чисел . Понятие обеспечивает соблюдение порядка-вложение требования , что различные элементы из S должны быть отображены в различные элементы L , и что каждая пара элементов в S имеет тот же порядок в L , как они делают в S . Расширенная линия действительного числа (действительные числа вместе с + ∞ и -∞) является завершением в этом смысле рациональных чисел: множество рациональных чисел {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} делает не имеет рациональной наименьшей верхней границы, но в вещественных числах имеет наименьшую верхнюю границу π .
Данный частично упорядоченный набор может иметь несколько различных дополнений. Например, одно завершение любого частично упорядоченного множества S - это набор его замкнутых вниз подмножеств, упорядоченных по включению . S вкладывается в эту (полную) решетку, отображая каждый элемент x в нижний набор элементов, которые меньше или равны x . Результатом является дистрибутивная решетка, которая используется в теореме Биркгофа о представлении . Тем не менее, она может иметь гораздо больше элементов , чем необходимо , чтобы сформировать завершение S . [3] Среди всех возможных пополнений решетки пополнение Дедекинда – МакНейля является наименьшей полной решеткой, в которую вложено S. [4]
Определение
Для каждого подмножества A частично упорядоченного множества S пусть A u обозначает набор верхних границ A ; то есть, элемент х из S принадлежит к А ¯u всякий раз , когда х больше или равен каждому элементу в A . Симметрично, пусть А л обозначит множество нижних граней А , элементы, которые меньше или равны каждый элемент A . Тогда пополнение Дедекинда – МакНейля S состоит из всех подмножеств A, для которых
- ( A u ) l = A ;
он упорядочен по включению: A ≤ B в пополнении тогда и только тогда, когда A ⊆ B как множества.
Элемент x из S вкладывается в пополнение как свой главный идеал , множество ↓ x элементов, меньших или равных x . Тогда (↓ x ) u - это множество элементов, больших или равных x , и ((↓ x ) u ) l = ↓ x , показывая, что ↓ x действительно является членом пополнения. [5] Несложно проверить, что отображение из x в ↓ x является упорядоченным вложением.
Иногда используется альтернативное определение завершения Дедекинда – МакНейла, которое больше напоминает определение разреза Дедекинда. [6] В частично упорядоченном множестве S определите разрез как пару множеств ( A , B ), для которых A u = B и A = B l . Если ( A , B ) разрез, то A удовлетворяет уравнению ( A u ) l = A , и наоборот, если ( A u ) l = A, то ( A , A u ) является разрезом. Следовательно, набор разрезов, частично упорядоченный включением в нижнем множестве разреза (или обратном отношению включения в верхнем множестве), дает эквивалентное определение пополнения Дедекинда – МакНейла.
При альтернативном определении обе операции соединения и пересечения полной решетки имеют симметричные описания: если ( A i , B i ) - разрезы в любом семействе разрезов, то пересечение этих разрезов - это разрез ( L , L u ), где L = i A i , а соединение - это разрез ( U l , U ), где U = ∩ i B i .
Примеры
Если Q - это набор рациональных чисел , рассматриваемый как полностью упорядоченный набор с обычным числовым порядком, то каждый элемент пополнения Дедекинда – МакНейля Q можно рассматривать как разрез Дедекинда , а завершение Дедекинда – МакНейля Q - полный порядок действительных чисел вместе с двумя дополнительными значениями ± ∞. [7] Построение действительных чисел из рациональных чисел является примером завершения Дедекинда полностью упорядоченного множества , а завершение Дедекинда – МакНейла обобщает эту концепцию от полных порядков до частичных порядков.
Если S - антицепь (набор элементов, два из которых не сопоставимы), то завершение Дедекинда – МакНейля S состоит из самого S вместе с двумя дополнительными элементами: нижним элементом, который находится под каждым элементом в S, и верхним элементом, который выше каждый элемент в S . [8]
Если O - любой конечный набор объектов, а A - любой конечный набор унарных атрибутов для объектов в O , то можно сформировать частичный порядок высоты два, в котором элементами частичного порядка являются объекты и атрибуты, а в который x ≤ y, когда x - объект с атрибутом y . Для частичного порядка, определенного таким образом, пополнение Дедекинда – МакНейля S известно как решетка понятий , и оно играет центральную роль в области анализа формальных понятий .
Характеристики
Завершение Дедекинда MacNeille частично упорядоченное множество S является наималейшей полной решеткой с S встроенной в него, в том смысле , что, если L является любой решеткой завершения S , то пополнение Дедекинда MacNeille является частично упорядоченным подмножеством L . [4] Когда S конечна, его завершение также конечна, и имеет наименьшее число элементов среди всех конечных полных решеток , содержащих S .
Частично упорядоченное множество S плотно при соединении и плотно при пересечении в пополнении Дедекинда – МакНейля; то есть, каждый элемент завершения является объединение некоторого множества элементов S , а также встречаются некоторое множество элементов в S . [9] Пополнение Дедекинда – МакНейла среди пополнений S характеризуется этим свойством.
Пополнение Дедекинда – МакНейля булевой алгебры является полной булевой алгеброй ; этот результат известен как теорема Гливенко – Стоуна в честь Валерия Ивановича Гливенко и Маршалла Стоуна . [10] Аналогично, пополнение Дедекинда – МакНейля решетки с вычетом является полной решеткой с вычетом. [11] Однако завершение распределительной решетки само по себе не обязательно должно быть распределительным, и завершение модульной решетки может не оставаться модульным. [12]
Завершение Дедекинда – Мак-Нила самодвойственно: завершение двойственного частичного порядка совпадает с двойственным завершением. [13]
Пополнение Дедекинда – МакНила S имеет ту же размерность порядка, что и сама S. [14]
В категории частично упорядоченные множества и монотонных функций между частично упорядоченными множествами, полные решетки образуют Инъективно объекты для порядка-вложений , и завершение Дедекинда MacNeille из S является инъективной оболочкой из S . [15]
Алгоритмы
Несколько исследователей исследовали алгоритмы построения пополнения Дедекинда – МакНейля конечного частично упорядоченного множества. Поскольку завершение Дедекинда – МакНейла может быть экспоненциально больше, чем частичный порядок, из которого оно происходит, [16] необходимо измерить временные границы для таких алгоритмов как с точки зрения числа n элементов входного частичного порядка, так и с точки зрения с точки зрения количества c элементов его завершения, а иногда и с точки зрения дополнительных мер сложности ввода и вывода. Формат, в котором представлена выходная решетка, также может влиять на время работы алгоритмов ее построения; например, если он представлен как логическая матрица, определяющая результат сравнения между каждой парой элементов решетки, размер вывода будет ( c 2 ), и это будет нижняя граница времени для алгоритма построения.
Построение набора разрезов
Гантер и Кузнецов (1998) описывают инкрементный алгоритм, в котором частичный входной порядок создается путем добавления одного элемента за раз; на каждом шаге завершение меньшего частичного заказа расширяется, чтобы сформировать завершение большего частичного заказа. В их методе завершение представлено явным списком сокращений. Каждый разрез расширенного частичного порядка, за исключением того, два набора которого пересекаются в новом элементе, является либо разрезом из предыдущего частичного порядка, либо формируется путем добавления нового элемента к одной или другой стороне разреза из предыдущего частичный порядок, поэтому их алгоритму нужны только тестовые пары наборов этой формы, чтобы определить, какие из них являются разрезами. Время использования их метода для добавления одного элемента к завершению частичного порядка составляет O ( cnw ), где w - ширина частичного порядка, то есть размер его наибольшей антицепи . Следовательно, время для вычисления завершения данного частичного порядка равно O ( cn 2 w ) = O ( cn 3 ) .
Как отмечают Журдан, Рэмпон и Джард (1994) , проблема перечисления всех разрезов в частично упорядоченном множестве может быть сформулирована как частный случай более простой задачи перечисления всех максимальных антицепей в другом частично упорядоченном множестве. Если Р любое частично упорядоченное множество, пусть Q будет частичный порядок, элементы которого содержат две копии P : для каждого элемента х из Р , Q содержит два элемента х 0 и х 1 , с х я < у J тогда и только тогда , когда х < y и i < j . Тогда разрезы в P соответствуют один к одному максимальным антицепям в Q : элементы в нижнем наборе разреза соответствуют элементам с индексом 0 в антицепи, а элементы в верхнем множестве разреза соответствуют элементы с индексом 1 в антицепи. Jourdan et al. описывают алгоритм поиска максимальных антицепей, который в применении к задаче перечисления всех разрезов в P требует времени O ( c ( nw + w 3 )) , что является усовершенствованием алгоритма Гантера и Кузнецова (1998), когда ширина w маленький. В качестве альтернативы, максимальная антицепь в Q такой же , как максимальное независимое множество в сравнимости граф из Q , или максимальная клика в дополнении к сравнимости графа, поэтому алгоритмы для задачи кликова или независимого множество также может быть применены к эта версия проблемы завершения Дедекинда – МакНейла.
Построение покрывающего графа
Транзитивно сокращение или покрытие график завершения Дедекинда MacNeille описывает отношение порядка между его элементами в сжатой форме: каждый сосед разреза должен удалить элемент из исходного частичного порядка либо из верхнего или нижнего набора разреза, так каждая вершина имеет не более n соседей. Таким образом, покрывающий граф имеет c вершин и не более cn / 2 соседей, число, которое может быть намного меньше, чем c 2 элементов в матрице, определяющей все попарные сравнения между элементами. Нурин и Рейно (1999) показывают, как эффективно вычислить этот покрывающий граф; в более общем случае , если B является любым семейством множеств, они показывают , как вычислить охватывающий график решетки штуцеров подмножеств B . В случае решетки Дедекинда – МакНейла B можно рассматривать как семейство дополнительных множеств главных идеалов, а объединение подмножеств B является дополнением нижних множеств разрезов. Основная идея их алгоритма состоит в том, чтобы генерировать объединения подмножеств B постепенно (для каждого набора в B , формируя его объединение со всеми ранее сгенерированными объединениями), представлять результирующее семейство наборов в дереве и использовать представление дерева для проверки определенных пары-кандидаты множеств для смежности в покрывающем отношении; требуется время O ( cn 2 ) . В более поздних работах те же авторы показали, что алгоритм можно сделать полностью инкрементным (с возможностью добавления элементов в частичный порядок по одному) с той же общей временной границей. [17]
Заметки
- ↑ Davey & Priestley (2002 , стр. 166); Зигфрид и Шредер (2003 , с. 119).
- ^ Зигфрид и Шредер (2003) , определение 5.3.1, стр. 119.
- ^ Карпинето, Клаудио; Романо, Джованни (2004), Анализ концептуальных данных: теория и приложения , John Wiley and Sons, стр. 10, ISBN 978-0-470-85055-8.
- ^ Б Бишоп (1978) ; Зигфрид и Шредер (2003) , теорема 5.3.8, стр. 121.
- ^ MacNeille (1937) , лемма 11.8, стр. 444; Дэйви и Пристли (2002) , лемма 3.9 (i), стр. 166.
- ^ Это определение, которое первоначально использовал, например, МакНейл (1937) .
- ^ Davey & Priestley (2002) , пример 7.44 (1), стр. 168; Зигфрид и Шредер (2003) , пример 5.3.3 (2), стр. 120.
- ^ Davey & Priestley (2002) , пример 7.44 (2), стр. 168.
- Перейти ↑ Siegfried & Schröder (2003) , Proposition 5.3.7, p. 121.
- ↑ Биркгоф (1995) , теорема 27, с. 130.
- ^ Gabbay, Шехтман и Скворцов (2009) .
- ^ Котлар (1944) ; Фунаяма (1944 г.) .
- Перейти ↑ Birkhoff (1995) .
- ^ Этот результат часто приписывают неопубликованной дипломной работе Гарвардского университета 1961 г. К. А. Бейкера "Размерность, независимость от соединений и широта в частично упорядоченных множествах". Его опубликовал Новак (1969) .
- ^ Банашевский и Брунс (1967) .
- ^ Гантер и Кузнецов (1998) .
- ^ Nourine & Рейно (2002) .
Рекомендации
- Banaschewski, B .; Брунс, Г. (1967), "Категориальная характеристика завершения MacNeille", Archiv дер Mathematik , 18 (4): 369-377, DOI : 10.1007 / BF01898828 , МР 0221984 , S2CID 121216988.
- Биркгоф, Гаррет (1995), «Завершение VI.9 с помощью разрезов», Теория решеток , публикации коллоквиума, 25 (3-е изд.), Американское математическое общество, стр. 126–128, ISBN 978-0-8218-1025-5.
- Бишоп, Алан А. (1978), "Универсальная характеристика отображения с завершением сокращений", Алгебра Universalis , 8 (3): 349-353, DOI : 10.1007 / bf02485405 , МР 0469839 , S2CID 121624631.
- Котлар, Миша (1944), "Метод построения структур и его применение к топологическим пространствам и абстрактной арифметике", Univ. Nac. Тукуман. Ревиста А. , 4 : 105–157, MR 0014062.
- Дэйви, BA; Пристли, Хилари А. (2002), «7.38 Завершение Дедекинда – МакНила» , Введение в решетки и порядок (2-е изд.), Cambridge University Press , стр. 166, ISBN 978-0-521-78451-1, Zbl 1002,06001.
- Funayama, Nenosuke (1944), "О пополнении разрезами распределительных решеток", Proc. Imp. Акад. Токио , 20 : 1-2, DOI : 10,3792 / Пиа / 1195573210 , MR 0014063 , Zbl 0063,01484.
- Габбай, Дов М .; Шехтман, Валентин; Скворцов, Димитрий (2009), «3.4.12 Пополнение Дедекинда – МакНила решетки с делениями», Квантификация в неклассической логике, Том 1 , Исследования по логике и основам математики, 153 , Elsevier, стр. 177–178, ISBN 978-0-444-52012-8, Zbl 1211,03002.
- Гантер, Бернхард; Кузнецов, Сергей О. (1998), "Пошаговое построение пополнения Дедекинда-МакНейля", Тр. 6-й Int. Конф. Концептуальные структуры: теория, инструменты и приложения (ICCS98) , Lecture Notes в области компьютерных наук, 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.
- MacNeille, HM (1937), «Частично упорядоченные множества», Trans. Амер. Математика. Soc. , 42 (3): 416-460, DOI : 10,2307 / 1989739 , СУЛ 63.0833.04 , JSTOR 1989739 , МР 1501929 , Zbl +0017,33904.
- Нурин, Луари; Рейно, Оливье (1999), «Быстрый алгоритм построения решеток», Письма об обработке информации , 71 (5–6): 199–204, 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", Math. Аня. , 179 : 337-342, DOI : 10.1007 / BF01350778 , МР 0240010 , S2CID 120963245.
- Зигфрид, Бернд; Шредер, Вальтер (2003), "5.3 Вложения / Завершение Дедекинда / Мак-Нейля ", Упорядоченные множества: Введение , Биркхойзер, стр. 119–122, ISBN 978-0-8176-4128-3.
Внешние ссылки
- Завершение MacNeille в PlanetMath
- Доработка MacNeille в nLab