В математике дистрибутивная решетка — это решетка , в которой операции соединения и встречи распределяются друг по другу. Прототипическими примерами таких структур являются коллекции множеств, для которых операции над решеткой могут быть заданы объединением и пересечением множеств . Действительно, эти решетки множеств полностью описывают декорации: каждая дистрибутивная решетка — с точностью до изоморфизма — задана как таковая решетка множеств.
Как и в случае с произвольными решетками, дистрибутивную решетку L можно рассматривать либо как структуру теории порядка , либо как структуру универсальной алгебры . Оба взгляда и их взаимное соответствие обсуждаются в статье о решетках . В данной ситуации алгебраическое описание представляется более удобным.
Решетка ( L , ∨, ∧) является дистрибутивной , если для всех x , y и z в L выполняется следующее дополнительное тождество :
Рассматривая решетки как частично упорядоченные множества, это говорит о том, что операция встречи сохраняет непустые конечные соединения. Основной факт теории решеток состоит в том, что приведенное выше условие эквивалентно двойственному ему : [1]
Если в каждой решетке отношение порядка p ≤ q определяется, как обычно, как p ∧ q = p , то неравенство x ∧ ( y ∨ z ) ≥ ( x ∧ y ) ∨ ( x ∧ z ) и двойственное ему x ∨ ( y ∧ z ) ≤ ( x ∨ y ) ∧ ( x ∨ z ) всегда верны. Решетка называется дистрибутивной, если выполнено хотя бы одно из обратных неравенств. Более подробную информацию о связи этого условия с другими условиями дистрибутивности теории порядка можно найти в статье Дистрибутивность (теория порядка) .
Морфизм дистрибутивных решеток — это просто гомоморфизм решетки, как указано в статье о решетках , то есть функция, совместимая с двумя решеточными операциями. Поскольку такой морфизм решеток сохраняет структуру решетки, он, следовательно, сохранит и дистрибутивность (и, таким образом, будет морфизмом дистрибутивных решеток).
Дистрибутивные решетки являются повсеместными, но также и довольно специфическими структурами. Как уже упоминалось, основным примером дистрибутивных решеток являются решетки множеств, где соединение и соединение задаются обычными теоретико-множественными операциями. Дополнительные примеры включают в себя:
В начале разработки теории решеток Чарльз С. Пирс считал, что все решетки дистрибутивны, то есть дистрибутивность следует из остальных аксиом решетки. [3] [4] Однако доказательства независимости были даны Шредером , Фойгтом, (де) Люротом , Корсельтом , [5] и Дедекиндом . [3]
Существуют различные эквивалентные формулировки приведенному выше определению. Например, L является дистрибутивным тогда и только тогда, когда для всех элементов x , y , z в L выполняется следующее :
Простейшими нераспределительными решетками являются M 3 , «ромбовидная решетка», и N 5 , «пятиугольная решетка». Решетка дистрибутивна тогда и только тогда, когда ни одна из ее подрешеток не изоморфна M 3 или N 5 ; Подрешетка — это подмножество, замкнутое относительно операций соединения и соединения исходной решетки. Обратите внимание, что это не то же самое, что подмножество, представляющее собой решетку в исходном порядке (но, возможно, с другими операциями соединения и соединения). Дальнейшие характеристики вытекают из теории представлений в следующем разделе.
Альтернативный способ констатировать тот же факт состоит в том, что каждая дистрибутивная решетка является подпрямым произведением копий двухэлементной цепи или что единственным подпрямо неприводимым членом класса дистрибутивных решеток является двухэлементная цепь. Как следствие, каждая булева решетка также обладает этим свойством. [6]
Наконец, дистрибутивность влечет за собой несколько других приятных свойств. Например, элемент дистрибутивной решетки является встречно-простым тогда и только тогда, когда он является встречно-неприводимым , хотя последнее, как правило, является более слабым свойством. В силу двойственности то же самое верно для простых и неприводимых элементов. [7] Если решетка дистрибутивна, ее накрывающее отношение образует медианный граф . [8]
Более того, каждая дистрибутивная решетка также является модулярной .
Введение уже намекало на наиболее важную характеристику дистрибутивных решеток: решетка дистрибутивна тогда и только тогда, когда она изоморфна решетке множеств (замкнутой относительно объединения и пересечения множеств ). (Последнюю структуру в этом контексте иногда называют кольцом множеств .) То, что объединение и пересечение множеств действительно являются дистрибутивными в указанном выше смысле, является элементарным фактом. Другое направление менее тривиально, поскольку требует сформулированных ниже теорем о представлении . Важным выводом из этой характеристики является то, что тождества (уравнения), которые выполняются во всех дистрибутивных решетках, являются именно теми, которые выполняются во всех решетках множеств в указанном выше смысле.
Теорема Биркгофа о представлении дистрибутивных решеток утверждает, что каждая конечная дистрибутивная решетка изоморфна решетке нижних множеств ЧУУ ее простых по соединению (что эквивалентно: неприводимых по объединению) элементов. Это устанавливает биекцию (с точностью до изоморфизма ) между классом всех конечных частично упорядоченных множеств и классом всех конечных дистрибутивных решеток. Эту биекцию можно расширить до двойственности категорий между гомоморфизмами конечных дистрибутивных решеток и монотонными функциями конечных частично упорядоченных множеств. Однако обобщение этого результата на бесконечные решетки требует добавления дополнительной структуры.
Другая ранняя теорема о представлении теперь известна как теорема Стоуна о представлении дистрибутивных решеток (название в честь Маршалла Харви Стоуна , который первым ее доказал). Он характеризует дистрибутивные решетки как решетки компактных открытых множеств некоторых топологических пространств . Этот результат можно рассматривать как обобщение знаменитой теоремы Стоуна о представлении булевых алгебр , так и как специализацию общего положения двойственности Стоуна .
Еще одно важное представление было установлено Хилари Пристли в ее теореме о представлении дистрибутивных решеток . В этой формулировке дистрибутивная решетка используется для построения топологического пространства с дополнительным частичным порядком в его точках, что дает (полностью разделенное по порядку) упорядоченное пространство Стоуна (или пространство Пристли ). Исходная решетка восстанавливается как совокупность открытозамкнутых нижних множеств этого пространства.
Вследствие теорем Стоуна и Пристли легко увидеть, что любая дистрибутивная решетка действительно изоморфна решетке множеств. Однако для доказательства обоих утверждений требуется булева теорема о простых идеалах , слабая форма аксиомы выбора .
Свободную дистрибутивную решетку над множеством образующих G можно построить гораздо проще, чем общую свободную решетку . Первое наблюдение состоит в том, что, используя законы дистрибутивности, каждый член, образованный бинарными операциями и набором образующих, может быть преобразован в следующую эквивалентную нормальную форму :
где – конечные множества элементов G . Более того, поскольку и встречи, и соединения являются ассоциативными , коммутативными и идемпотентными , можно игнорировать дубликаты и порядок и представлять объединение встреч, подобное приведенному выше, как набор наборов:
где – конечные подмножества G . Однако все же возможно, что два таких термина обозначают один и тот же элемент дистрибутивной решетки. Это происходит, когда существуют индексы j и k , которые являются подмножеством. В этом случае совпадение будет ниже пересечения, и, следовательно, можно безопасно удалить избыточный набор , не меняя интерпретации всего термина. Следовательно, множество конечных подмножеств G будем называть неизбыточным , если все его элементы взаимно несравнимы (относительно порядка подмножества); то есть когда оно образует антицепь конечных множеств .
Теперь свободная дистрибутивная решетка над множеством образующих G определена на множестве всех конечных неизбыточных множеств конечных подмножеств G . Соединение двух конечных неизбыточных множеств получается их объединением удалением всех избыточных множеств. Точно так же встреча двух множеств S и T является неизбыточной версией. Проверка того, что эта структура является дистрибутивной решеткой с требуемым универсальным свойством, является рутинной.
Число элементов в свободных дистрибутивных решетках с n образующими определяется числами Дедекинда . Эти числа быстро растут и известны только для n ≤ 9; они есть
Числа, приведенные выше, подсчитывают количество элементов в свободных дистрибутивных решетках, в которых операции решетки представляют собой соединения и встречи конечных наборов элементов, включая пустое множество. Если пустые соединения и пустые встречи запрещены, в результирующих свободных распределительных решетках будет на два элемента меньше; их количество элементов образует последовательность