Распределительная решетка - Distributive lattice

В математике , дистрибутивной решеткой является решетка , в которой операции соединения и встречаются распределить друг над другом. Типичными примерами таких структур являются наборы множеств, для которых операции решетки могут быть заданы объединением множеств и пересечением . В самом деле, эти решетки множеств полностью описывают декорации: каждая дистрибутивная решетка - с точностью до изоморфизма - задана как такая решетка множеств.

Определение

Как и в случае произвольных решеток, можно рассматривать дистрибутивную решетку L либо как структуру теории порядка, либо как универсальную алгебру . Оба взгляда и их взаимное соответствие обсуждаются в статье о решетках . В данной ситуации более удобным представляется алгебраическое описание:

Решетка ( L , ∨, ∧) дистрибутивна, если для всех x , y и z в L выполняется следующее дополнительное тождество :

х ∧ ( у ∨ г ) = ( х ∧ у ) ∨ ( х ∧ г ).

Если рассматривать решетки как частично упорядоченные множества, это означает, что операция встречи сохраняет непустые конечные соединения. Основным фактом теории решеток является то, что указанное выше условие эквивалентно двойственному ему :

х ∨ ( у ∧ г ) = ( х ∨ у ) ∧ ( х ∨ г ) для всех х , у и г в L .

В каждой решетке, определяя p ≤ q, как обычно, означающим p ∧ q = p , выполняется неравенство x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ), а также двойственное неравенство x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ). Решетка дистрибутивна, если также выполняется одно из обратных неравенств. Более подробную информацию о связи этого условия с другими условиями дистрибутивности теории порядка можно найти в статье о дистрибутивности (теория порядка) .

Морфизмы

Морфизм дистрибутивных решеток - это просто решеточный гомоморфизм, как указано в статье о решетках , то есть функция, совместимая с двумя решеточными операциями. Поскольку такой морфизм решеток сохраняет структуру решетки, следовательно, он также сохранит дистрибутивность (и, таким образом, будет морфизмом дистрибутивных решеток).

Примеры

Решетка Юнга

Распределительные решетки - это повсеместные, но довольно специфические структуры. Как уже упоминалось, основным примером дистрибутивных решеток являются решетки множеств, где соединения и встречи задаются обычными теоретико-множественными операциями. Дополнительные примеры включают:

• Lindenbaum алгебра большинства логик , что поддержка конъюнкция и дизъюнкция является дистрибутивной решеткой, то есть «и» распространяет более «или» и наоборот.
• Каждая булева алгебра является дистрибутивной решеткой.
• Каждая алгебра Гейтинга является дистрибутивной решеткой. Особенно это касается всех локалей и, следовательно, всех открытых решеток множеств топологических пространств . Также обратите внимание, что алгебры Гейтинга можно рассматривать как алгебры Линденбаума интуиционистской логики , что делает их частным случаем первого примера.
• Каждый полностью упорядоченный набор представляет собой распределительную решетку с max как join и min как meet.
• В натуральные числа образуют (условно полной) распределительную решетку, беря наибольший общий делитель , как пересекаются и наименьшее общее кратное , как присоединиться. Эта решетка также имеет наименьший элемент, а именно 1, который, следовательно, служит элементом идентичности для соединений.
• Учитывая положительное целое число п , множество всех положительных делителей из п форм дистрибутивной решетки, снова наибольший общий делитель , как пересекаются и наименьшее общее кратное , как присоединиться. Это алгебра Булева тогда и только тогда , когда п является бесквадратным .
• Решетка упорядоченное векторное пространство является дистрибутивной решеткой.
• Решетка Юнга, заданная порядком включения диаграмм Юнга, представляющих целочисленные разбиения, является дистрибутивной решеткой.
• Точки дистрибутивного многогранника ( выпуклого многогранника, замкнутого относительно покоординатных операций минимума и покоординатного максимума), где эти две операции являются соединением и пересекаются с операциями решетки.

В начале развития теории решеток Чарльз С. Пирс считал, что все решетки дистрибутивны, то есть дистрибутивность следует из остальных аксиом решетки. Однако доказательства независимости были даны Шредером , Фойгтом, ^{( де )} Люротом , Корсельтом и Дедекиндом .

Характерные свойства

Существуют различные эквивалентные формулировки приведенного выше определения. Например, L дистрибутивен тогда и только тогда, когда для всех элементов x , y , z в L выполняется следующее :

( x y ) ( y z ) ( z x ) = ( x y ) ( y z ) ( z x ).${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ Displaystyle \ клин}$${\ displaystyle \ vee}$

Аналогично, L дистрибутивна тогда и только тогда, когда

x z = y z и x z = y z всегда подразумевают x = y .${\ Displaystyle \ клин}$${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ displaystyle \ vee}$

• Диаграммы Хассе двух прототипных недистрибутивных решеток
• 

  Алмазная решетка M ₃ недистрибутивна : x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ 0 = 0 ∨ 0 = ( x ∧ y ) ∨ ( x ∧ z ) .

• 

  Решетка пятиугольника N ₅ недистрибутивна : x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ z = 0 ∨ z = ( x ∧ y ) ∨ ( x ∧ z ) .

Распределительная решетка , которая содержит N5 (сплошные линии, слева) и М3 (справа) в суб наборе , но не как к югу от решетки

Простейшими недистрибутивными решетками являются M ₃ , «решетка алмаза», и N ₅ , «решетка пятиугольника». Решетка дистрибутивна тогда и только тогда, когда ни одна из ее подрешеток не изоморфна M ₃ или  N ₅ ; подрешетка - это подмножество, которое замкнуто относительно операций пересечения и соединения исходной решетки. Обратите внимание, что это не то же самое, что подмножество, представляющее собой решетку в исходном порядке (но, возможно, с другими операциями соединения и встречи). Дальнейшие характеристики выводятся из теории представлений в следующем разделе.

Другой способ констатировать тот же факт состоит в том, что каждая дистрибутивная решетка является подпрямым продуктом копий двухэлементной цепочки или что единственный подпрямо неразложимый член класса дистрибутивных решеток - это двухэлементная цепочка. Как следствие, каждая булева решетка также обладает этим свойством.

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

Кроме того, каждая распределительная решетка также является модульной .

Теория представлений

Введение уже намекало на наиболее важную характеристику дистрибутивных решеток: решетка дистрибутивна тогда и только тогда, когда она изоморфна решетке множеств (замкнутой относительно объединения и пересечения множеств ). (Последнюю структуру иногда называют кольцом множеств в этом контексте.) То, что объединение множеств и пересечение действительно дистрибутивны в указанном выше смысле, является элементарным фактом. Другое направление менее тривиально, поскольку требует изложенных ниже теорем о представлении. Важный вывод из этой характеристики состоит в том, что тождества (уравнения), которые выполняются во всех дистрибутивных решетках, являются в точности теми, которые выполняются во всех решетках множеств в указанном выше смысле.

Теорема о представлении Биркгофа для дистрибутивных решеток состояний , что каждые конечные дистрибутивная решетка изоморфна решетке нижних множеств в посете из его нарисуйте штрих (эквивалентно: нарисуйте неприводимый) элементы. Это устанавливает биекцию (с точностью до изоморфизма ) между классом всех конечных множеств и классом всех конечных дистрибутивных решеток. Эта биекция может быть расширена до двойственности категорий между гомоморфизмами конечных дистрибутивных решеток и монотонными функциями конечных множеств. Однако обобщение этого результата на бесконечные решетки требует добавления дополнительной структуры.

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

Еще одно важное представление было установлено Хилари Пристли в ее теореме о представлении для дистрибутивных решеток . В этой формулировке дистрибутивная решетка используется для построения топологического пространства с дополнительным частичным порядком в его точках, что дает (полностью разделенное порядком) упорядоченное пространство Стоуна (или пространство Пристли ). Исходная решетка восстанавливается как набор незамкнутых нижних множеств этого пространства.

Как следствие теорем Стоуна и Пристли, легко видеть, что любая дистрибутивная решетка действительно изоморфна решетке множеств. Однако доказательства обоих утверждений требуют булевой теоремы о простом идеале , слабой формы избранной аксиомы .

Бесплатные распределительные решетки

Свободные распределительные решетки на нулевом, одном, двух и трех образующих. Элементы с метками «0» и «1» представляют собой пустое соединение и пересечение, а элемент с меткой «большинство» равен ( x ∧ y ) ∨ ( x ∧ z ) ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( х ∨ г ) ∧ ( у ∨ г ).

Свободная дистрибутивная решетку над множеством генераторов G можно построить гораздо легче , чем в общей свободной решетке. Первое наблюдение состоит в том, что, используя законы дистрибутивности, каждый член, образованный бинарными операциями и на множестве генераторов, может быть преобразован в следующую эквивалентную нормальную форму : ${\ displaystyle \ lor}$${\ displaystyle \ land}$

${\ Displaystyle M_ {1} \ lor M_ {2} \ lor \ cdots \ lor M_ {n},}$

где конечно отвечает элементы G . Более того, поскольку и встреча, и соединение являются ассоциативными , коммутативными и идемпотентными , можно игнорировать дубликаты и порядок и представлять соединение встреч, подобное приведенному выше, как набор наборов: ${\ displaystyle M_ {i}}$

${\ Displaystyle \ {N_ {1}, N_ {2}, \ ldots, N_ {n} \},}$

где конечные подмножества G . Однако все же возможно, что два таких члена обозначают один и тот же элемент распределительной решетки. Это происходит, когда есть индексы j и k , которые являются подмножеством. В этом случае встреча будет ниже точки встречи, и, следовательно, можно безопасно удалить избыточный набор, не меняя интерпретацию всего термина. Следовательно, набор конечных подмножеств G будет называться неизбыточным, если все его элементы взаимно несравнимы (относительно упорядочения подмножеств); то есть, когда он образует антицепь конечных множеств . ${\ displaystyle N_ {i}}$${\ displaystyle N_ {j}}$${\ displaystyle N_ {k}.}$${\ displaystyle N_ {k}}$${\ displaystyle N_ {j},}$${\ displaystyle N_ {k}}$${\ displaystyle N_ {i}}$

Теперь свободный дистрибутивной решеткой над множеством образующих G определяется на множестве всех конечных тупиковых множеств конечных подмножеств G . Соединение двух конечных неизбыточных множеств получается из их объединения путем удаления всех лишних множеств. Точно так же встреча двух множеств S и T является неизбыточной версией метода . Проверка того, что эта структура является дистрибутивной решеткой с требуемым универсальным свойством, является рутинной. ${\ displaystyle \ {N \ cup M \ mid N \ in S, M \ in T \}.}$

Количество элементов в свободных дистрибутивных решетках с n образующими задается числами Дедекинда . Эти числа быстро растут и известны только для n  ≤ 8; они есть

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (последовательность A000372 в OEIS ).

Приведенные выше числа подсчитывают количество элементов в свободных распределительных решетках, в которых операции решетки являются соединениями и встречами конечных наборов элементов, включая пустой набор. Если пустые соединения и пустые встречи запрещены, в результирующих свободных распределительных решетках будет на два элемента меньше; их количества элементов образуют последовательность

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786 (последовательность A007153 в OEIS ).

Смотрите также

• Полностью распределительная решетка - решетка, в которой бесконечные соединения распределяются по бесконечным встречам.
• Теория двойственности для дистрибутивных решеток
• Спектральное пространство

использованная литература

дальнейшее чтение

• Беррис, Стэнли Н .; Санкаппанавар, HP (1981). Курс универсальной алгебры . Springer-Verlag. ISBN 3-540-90578-2.
• Последовательность OEIS A006982 (количество немаркированных дистрибутивных решеток с n элементами)