Распределительность (теория порядка)

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

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

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

${\displaystyle x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z)}$

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

${\displaystyle x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z)}$

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

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

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

Полурешетка — это частично упорядоченное множество с одной из двух операций решетки, либо meet- , либо join-полурешеткой . Учитывая, что существует только одна бинарная операция, дистрибутивность, очевидно, не может быть определена стандартным способом. Тем не менее, из-за взаимодействия одной операции с данным порядком, следующее определение дистрибутивности остается возможным. Meet-полурешетка является дистрибутивной , если для всех 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 — дистрибутивная решетка.

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

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

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

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

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

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

${\displaystyle 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 ). Полная решетка полностью дистрибутивна, если для всех таких данных выполняется следующее утверждение:

${\displaystyle \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 является дистрибутивным, ^[2] но не дуально-дистрибутивным, поскольку x ∧ ( y ∨ z ) = x ∧ 1 = x ≠ z = 0 ∨ z = ( x ∧ y ) ∨ ( x ∧ z ).

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

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

В произвольной решетке, если x ₁ и x ₂ являются дистрибутивными элементами, то таковым является и x ₁ ∨ x ₂ . ^[4]

Литература

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

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

Ссылки

1. G. Grätzer (2011). Теория решеток: Основы . Springer/Birkhäuser.; здесь: Раздел II.5.1, стр.167
2. Джордж Гретцер (2003). Общая теория решеток (2-е изд.). Базель: Birkhäuser. ISBN 3-7643-6996-5.Здесь: Определение III.2.1 и последующее замечание, стр.181.
3. Grätzer (2003), Thm.III.2.2 [первоначально O. Ore 1935], стр.181-182.
4. Гретцер (2003), Теория III.2.9.(i), стр.188