Дистрибутивность (теория порядка)

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

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

Вероятно, наиболее распространенным типом дистрибутивности является тот, который определен для решеток , где формирование бинарных верхних и нижних точек обеспечивает совокупность операций соединения ( $\vee$) и встретиться ( $\wedge$). Дистрибутивность этих двух операций затем выражается требованием, чтобы тождество

$x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)$

справедливы для всех элементов x , y и z . Этот закон дистрибутивности определяет класс дистрибутивных решеток . Обратите внимание, что это требование можно перефразировать, сказав, что двоичный код соответствует сохранению двоичных соединений. Известно, что приведенное выше утверждение эквивалентно двойственному ему порядку

$x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)$

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

Дистрибутивность для полурешеток

Диаграмма Хассе для определения дистрибутивности встречной полурешетки.

Полурешетка частично — это упорядоченное множество, содержащее только одну из двух решетчатых операций: встречу или соединение-полурешетку . Учитывая, что существует только одна бинарная операция, очевидно, что дистрибутивность не может быть определена стандартным способом. Тем не менее из-за взаимодействия одиночной операции с заданным порядком остается возможным следующее определение дистрибутивности. Встреча -полурешетка является дистрибутивной , если для всех a , b и x :

Если a ∧ b ≤ x, то существуют a ′ и b ′ такие, что a ⩽ a ′ , b ⩽ b' и x = a ′ ∧ b' .

Дистрибутивные полурешетки соединения определяются двойственно : полурешетка соединения является дистрибутивной , если для всех a , b и x :

Если x ≤ a ∨ b, то существуют a ′ и b ′ такие, что a ′ ≤ a , b ′ ≤ b и x = a ′ ∨ b' .

В любом случае a' и b' не обязательно должны быть уникальными.Эти определения оправданы тем фактом, что для любой решетки L следующие утверждения эквивалентны:

• L дистрибутивна как встреча-полурешетка
• L дистрибутивна как соединение-полурешетка
• L — дистрибутивная решетка.

Таким образом, любая дистрибутивная полурешетка, в которой существуют бинарные соединения, является дистрибутивной решеткой. Объединение-полурешетка дистрибутивна тогда и только тогда, когда решетка ее идеалов (по включению) дистрибутивна.

Это определение дистрибутивности позволяет обобщить некоторые утверждения о дистрибутивных решетках на дистрибутивные полурешетки.

Законы дистрибутивности для полных решеток

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

$x\wedge \bigvee S=\bigvee \{x\wedge s\mid s\in S\}$

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

$x\vee \bigwedge S=\bigwedge \{x\vee s\mid s\in S\}$

определяющий класс дуальных фреймов или полных ко-гейтинговых алгебр.

Теперь можно пойти еще дальше и определить порядок, в котором произвольные соединения распределяются по произвольным соединениям. Такие структуры называются вполне дистрибутивными решетками . Однако для выражения этого необходимы более технические формулировки. Рассмотрим семейство с двойным индексом { x _{j , k} | j в J , k в K ( j )} элементов полной решетки, и пусть F — множество функций выбора f, выбирающих для каждого индекса j из J некоторый индекс f ( j ) в K ( j ). Полная решетка является вполне дистрибутивной , если для всех таких данных справедливо следующее утверждение:

$\bigwedge _{j\in J}\bigvee _{k\in K(j)}x_{j,k}=\bigvee _{f\in F}\bigwedge _{j\in J}x_{j,f(j)}$

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

Дистрибутивные элементы в произвольных решетках

Пятиугольная решетка N ₅

В произвольной решетке элемент x называется дистрибутивным элементом , если ∀ y , z : x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ). Элемент x называется двойственным дистрибутивным элементом , если ∀ y , z : x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ).

В дистрибутивной решетке каждый элемент, конечно, одновременно дистрибутивен и двойственен дистрибутиву.В недистрибутивной решетке могут быть элементы дистрибутивные, но не дуальные дистрибутивные (и наоборот).Например, в изображенной пятиугольной решетке N ₅ элемент x является дистрибутивным, но не двойственный дистрибутив, поскольку Икс ∧ ( у ∨ z ) = Икс ∧ 1 знак равно Икс ≠ z знак равно 0 ∨ z знак равно ( Икс ∧ y ) ∨ ( Икс ∧ z ).

В произвольной решетке L следующие условия эквивалентны:

• х – распределительный элемент;
• Отображение φ, определенное формулой φ( y ) = x ∨ y, является решеточным гомоморфизмом из L в верхнее замыкание ↑ x = { y ∈ L : x ≤ y };
• Бинарное отношение Θ _x на L, определяемое формулой y Θ _x z, если x ∨ y = x ∨ z , является отношением конгруэнтности , то есть отношением эквивалентности , совместимым с ∧ и ∨.

произвольной решетке, если и _тоже x2 являются _{дистрибутивными элементами, то} и x1 _∨ x1 x2 _В .

Литература

Дистрибутивность — это базовое понятие, которое рассматривается в любом учебнике по теории решеток и порядка. См. литературу, посвященную статьям по теории порядка и теории решеток . Более конкретная литература включает:

• Г. Н. Рэни, Полностью распределительные полные решетки , Труды Американского математического общества , 3: 677–680, 1952.