Решетка (порядок)

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

Транзитивные  бинарные отношения в т е
Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Всего, Полуконнекc Антирефлексивный ​ Отношение эквивалентности И ✗ ✗ ✗ ✗ ✗ И ✗ ✗ Предварительный заказ (квазизаказ) ✗ ✗ ✗ ✗ ✗ ✗ И ✗ ✗ Частичный заказ ✗ И ✗ ✗ ✗ ✗ И ✗ ✗ Всего предзаказов ✗ ✗ И ✗ ✗ ✗ И ✗ ✗ Общий заказ ✗ И И ✗ ✗ ✗ И ✗ ✗ Предварительный заказ ✗ ✗ И И ✗ ✗ И ✗ ✗ Хорошо-квази-упорядочение ✗ ✗ ✗ И ✗ ✗ И ✗ ✗ Хорошо упорядоченный ✗ И И И ✗ ✗ И ✗ ✗ Решетка ✗ И ✗ ✗ И И И ✗ ✗ Join-полурешетка ✗ И ✗ ✗ И ✗ И ✗ ✗ Встреча-полурешетка ✗ И ✗ ✗ ✗ И И ✗ ✗ Строгий частичный порядок ✗ И ✗ ✗ ✗ ✗ ✗ И И Строгий слабый порядок ✗ И ✗ ✗ ✗ ✗ ✗ И И Строгий общий порядок ✗ И И ✗ ✗ ✗ ✗ И И Симметричный Антисимметричный Подключен Обоснованный Имеет соединения Имеет встречает Рефлексивный Нерефлексивный Асимметричный Определения, для всех и${\displaystyle а,б}$${\displaystyle S\neq \varnothing:}$ ${\displaystyle {\begin{align}&aRb\\\Стрелка вправо {}&bRa\end{align}}}$ ${\displaystyle {\begin{align}aRb{\text{ и }}&bRa\\\Стрелка вправо a={}&b\end{align}}}$ ${\displaystyle {\begin{align}a\neq {}&b\Rightarrow \\aRb{\text{ или }}&bRa\end{align}}}$ ${\displaystyle {\begin{align}\min S\\{\text{exists}}\end{align}}}$ ${\displaystyle {\begin{align}a\vee b\\{\text{существует}}\end{align}}}$ ${\displaystyle {\begin{align}a\wedge b\\{\text{существует}}\end{align}}}$ ${\displaystyle аРа}$ ${\displaystyle {\text{не}}aRa}$ ${\displaystyle {\begin{align}aRb\Rightarrow \\{\text{not}}bRa\end{align}}}$
Иуказывает, что свойство столбца всегда верно для термина строки (слева), в то время как ✗ указывает, что свойство не гарантируется в общем случае (оно может выполняться, а может и не выполняться). Например, то, что каждое отношение эквивалентности симметрично, но не обязательно антисимметрично, обозначается в столбце «Симметрично» и ✗ в столбце «Антисимметрично» соответственно.И Все определения неявно требуют, чтобы однородное отношение было транзитивным : для всех, если и то Определение термина может требовать дополнительных свойств, которые не перечислены в этой таблице.${\displaystyle R}$${\displaystyle а,б,в,}$${\displaystyle aRb}$${\displaystyle bRc}$${\displaystyle aRc.}$

Алгебраические структуры
Группа -подобная Группа Полугруппа  / Моноид Стойка и квадрант Квазигруппа и петля Абелева группа Магма Группа Ли Теория групп
Кольцевой​ Кольцо Рнг Полукольцо Околокольцо Коммутативное кольцо Домен Интегральная область Поле Кольцо деления Кольцо лжи Теория колец
Решетчатый Решетка Полурешетка Дополненная решетка Общий заказ алгебра Гейтинга Булева алгебра Карта решеток Теория решеток
Модульный​ Модуль Группа с операторами Вектор пространства Линейная алгебра
Алгебра -подобная Алгебра Ассоциативный Неассоциативный Композиционная алгебра алгебра Ли Оцененный Биалгебра алгебра Хопфа
в т е

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

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

Раздел абстрактной алгебры , изучающий решетки, называется теорией решеток .

Решетку можно определить либо с точки зрения теории порядка как частично упорядоченное множество, либо как алгебраическую структуру.

Частично упорядоченное множество ( посет) называется решеткой , если оно является как join-, так и meet- полурешеткой , т.е. каждое двухэлементное подмножество имеет join (т.е. наименьшую верхнюю границу, обозначаемую ) и, соответственно, meet (т.е. наибольшую нижнюю границу, обозначаемую ). Это определение делает и бинарными операциями . Обе операции монотонны относительно заданного порядка: и подразумевает, что и${\displaystyle (L,\leq )}$${\displaystyle \{a,b\}\subseteq L}$${\displaystyle a\vee b}$${\displaystyle a\wedge b}$${\displaystyle \,\wedge \,}$${\displaystyle \,\vee \,}$ ${\displaystyle a_{1}\leq a_{2}}$${\displaystyle b_{1}\leq b_{2}}$${\displaystyle a_{1}\vee b_{1}\leq a_{2}\vee b_{2}}$${\displaystyle a_{1}\wedge b_{1}\leq a_{2}\wedge b_{2}.}$

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

Для данного подмножества решетки, встреча и соединение ограничиваются частичными функциями — они не определены, если их значение не принадлежит подмножеству. Результирующая структура на называется${\displaystyle H\subseteq L,}$${\displaystyle H.}$${\displaystyle H}$частичная решетка . В дополнение к этому внешнему определению как подмножества некоторой другой алгебраической структуры (решетки), частичная решетка может быть также внутренне определена как множество с двумя частичными бинарными операциями, удовлетворяющими определенным аксиомам.^[1]

Решетка — это алгебраическая структура , состоящая из множества и двух бинарных, коммутативных и ассоциативных операций , и удовлетворяющая следующим аксиоматическим тождествам для всех элементов ( иногда называемым законами поглощения ): ${\displaystyle (L,\vee ,\wedge )}$${\displaystyle L}$ ${\displaystyle \vee }$${\displaystyle \wedge }$${\displaystyle L}$${\displaystyle a,b\in L}$$${\displaystyle a\vee (a\wedge b)=a}$$$${\displaystyle a\wedge (a\vee b)=a}$$

Следующие два тождества также обычно рассматриваются как аксиомы, хотя они следуют из двух законов поглощения, взятых вместе. ^[2] Они называются идемпотентными законами .$${\displaystyle a\vee a=a}$$$${\displaystyle a\wedge a=a}$$

Эти аксиомы утверждают, что и и являются полурешетками . Законы поглощения, единственные аксиомы выше, в которых встречаются и объединяются, отличают решетку от произвольной пары полурешеточных структур и гарантируют, что две полурешетки взаимодействуют соответствующим образом. В частности, каждая полурешетка является дуальной по отношению к другой. Законы поглощения можно рассматривать как требование, чтобы полурешетки, встречающиеся и объединяющиеся, определяли один и тот же частичный порядок .${\displaystyle (L,\vee )}$${\displaystyle (L,\wedge )}$

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

Обратное также верно. При наличии алгебраически определенной решетки можно определить частичный порядок на , установив для всех элементов Законы поглощения гарантируют, что оба определения эквивалентны: и двойственно для другого направления.${\displaystyle (L,\vee ,\wedge ),}$${\displaystyle \leq }$${\displaystyle L}$$${\displaystyle a\leq b{\text{ if }}a=a\wedge b,{\text{ or }}}$$$${\displaystyle a\leq b{\text{ if }}b=a\vee b,}$$${\displaystyle a,b\in L.}$$${\displaystyle a=a\wedge b{\text{ implies }}b=b\vee (b\wedge a)=(a\wedge b)\vee b=a\vee b}$$

Теперь можно проверить, что отношение, введенное таким образом, определяет частичное упорядочение, в котором бинарные встречи и соединения задаются посредством исходных операций и${\displaystyle \leq }$${\displaystyle \vee }$${\displaystyle \wedge .}$

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

Ограниченная решетка — это решетка, которая дополнительно имеет наибольший элемент (также называемый максимальным или верхним элементом и обозначается как или как ) и наименьший элемент (также называемый минимальным или нижним элементом и обозначается как или как ), которые удовлетворяют${\displaystyle 1,}$${\displaystyle \top }$${\displaystyle 0}$${\displaystyle \bot }$$${\displaystyle 0\leq x\leq 1\;{\text{ for every }}x\in L.}$$

Ограниченную решетку можно также определить как алгебраическую структуру вида , в котором есть решетка, (дно решетки) является элементом идентичности для операции соединения , а (верх решетки) является элементом идентичности для операции встречи.${\displaystyle (L,\vee ,\wedge ,0,1)}$${\displaystyle (L,\vee ,\wedge )}$${\displaystyle 0}$${\displaystyle \vee ,}$${\displaystyle 1}$${\displaystyle \wedge .}$$${\displaystyle a\vee 0=a}$$$${\displaystyle a\wedge 1=a}$$

Частично упорядоченное множество является ограниченной решеткой тогда и только тогда, когда каждое конечное множество элементов (включая пустое множество) имеет соединение и встречу. Для каждого элемента частично упорядоченного множества пусто и верно , что и и, следовательно, каждый элемент частично упорядоченного множества является как верхней, так и нижней границей пустого множества. Это подразумевает, что соединение пустого множества является наименьшим элементом, а встреча пустого множества является наибольшим элементом Это согласуется с ассоциативностью и коммутативностью встречи и объединения: соединение объединения конечных множеств равно соединению объединений множеств, и, двойственно, встреча объединения конечных множеств равна встрече встреч множеств, то есть для конечных подмножеств и частично упорядоченного множества и удерживать. Взяв за пустое множество, и что согласуется с тем фактом, что${\displaystyle x}$${\displaystyle {\text{ for all }}a\in \varnothing ,x\leq a}$${\displaystyle {\text{ for all }}a\in \varnothing ,a\leq x,}$${\textstyle \bigvee \varnothing =0,}$${\textstyle \bigwedge \varnothing =1.}$${\displaystyle A}$${\displaystyle B}$${\displaystyle L,}$$${\displaystyle \bigvee (A\cup B)=\left(\bigvee A\right)\vee \left(\bigvee B\right)}$$$${\displaystyle \bigwedge (A\cup B)=\left(\bigwedge A\right)\wedge \left(\bigwedge B\right)}$$${\displaystyle B}$$${\displaystyle \bigvee (A\cup \varnothing )=\left(\bigvee A\right)\vee \left(\bigvee \varnothing \right)=\left(\bigvee A\right)\vee 0=\bigvee A}$$$${\displaystyle \bigwedge (A\cup \varnothing )=\left(\bigwedge A\right)\wedge \left(\bigwedge \varnothing \right)=\left(\bigwedge A\right)\wedge 1=\bigwedge A,}$$${\displaystyle A\cup \varnothing =A.}$

Каждая решетка может быть вложена в ограниченную решетку путем добавления наибольшего и наименьшего элемента. Более того, каждая непустая конечная решетка ограничена путем взятия соединения (соответственно, встречи) всех элементов, обозначаемого как (соответственно ), где — множество всех элементов.${\textstyle 1=\bigvee L=a_{1}\lor \cdots \lor a_{n}}$${\textstyle 0=\bigwedge L=a_{1}\land \cdots \land a_{n}}$${\displaystyle L=\left\{a_{1},\ldots ,a_{n}\right\}}$

Решетки имеют некоторые связи с семейством группоподобных алгебраических структур . Поскольку meet и join как коммутируют, так и ассоциируют, решетку можно рассматривать как состоящую из двух коммутативных полугрупп, имеющих одинаковую область определения. Для ограниченной решетки эти полугруппы фактически являются коммутативными моноидами . Закон поглощения является единственным определяющим тождеством, свойственным теории решеток. Ограниченную решетку можно также рассматривать как коммутативную установку без аксиомы дистрибутивности.

Благодаря коммутативности, ассоциативности и идемпотентности можно рассматривать join и meet как операции над непустыми конечными множествами, а не над парами элементов. В ограниченной решетке join и meet пустого множества также могут быть определены (как и соответственно). Это делает ограниченные решетки несколько более естественными, чем общие решетки, и многие авторы требуют, чтобы все решетки были ограниченными.${\displaystyle 0}$${\displaystyle 1,}$

Алгебраическая интерпретация решеток играет существенную роль в универсальной алгебре . ^{[ требуется ссылка ]}

• 
  Рис. 1: Подмножества подмножественного включения . Название «решетка» подсказано формой диаграммы Хассе, ее изображающей.${\displaystyle \{x,y,z\},}$
• 
  Рис. 2: Решетка целых делителей числа 60, упорядоченная по « делениям ».
• 
  Рис. 3: Решетка разбиений , упорядоченная по « уточнениям ».${\displaystyle \{1,2,3,4\},}$
• 
  Рис. 4: Решетка положительных целых чисел, упорядоченная по${\displaystyle \,\leq ,}$
• 
  Рис. 5: Решетка неотрицательных целых пар, упорядоченная покомпонентно.

• Для любого множества совокупность всех подмножеств (называемых множеством мощности ) можно упорядочить с помощью включения подмножества , чтобы получить решетку, ограниченную собой и пустым множеством. В этой решетке супремум обеспечивается объединением множеств , а инфимум обеспечивается пересечением множеств (см. рис. 1).${\displaystyle A,}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$
• Для любого множества совокупность всех конечных подмножеств, упорядоченных по включению, также является решеткой и будет ограниченной тогда и только тогда, когда является конечной.${\displaystyle A,}$${\displaystyle A,}$${\displaystyle A}$
• Для любого множества совокупность всех разбиений , упорядоченных по уточнению , представляет собой решетку (см. рис. 3).${\displaystyle A,}$${\displaystyle A,}$
• Положительные целые числа в их обычном порядке образуют неограниченную решетку с операциями «min» и «max». 1 — низ, верх отсутствует (см. рис. 4).
• Декартов квадрат натуральных чисел, упорядоченный таким образом, что если пара является нижним элементом, то верхнего элемента нет (см. рис. 5).${\displaystyle (a,b)\leq (c,d)}$${\displaystyle a\leq c{\text{ and }}b\leq d.}$${\displaystyle (0,0)}$
• Натуральные числа также образуют решетку относительно операций взятия наибольшего общего делителя и наименьшего общего кратного , с делимостью как отношением порядка: если делит, то является нижним; является верхним. На рис. 2 показана конечная подрешетка.${\displaystyle a\leq b}$${\displaystyle a}$${\displaystyle b.}$ ${\displaystyle 1}$${\displaystyle 0}$
• Каждая полная решетка (см. также ниже) является (довольно специфической) ограниченной решеткой. Этот класс порождает широкий спектр практических примеров .
• Множество компактных элементов арифметически полной решетки — это решетка с наименьшим элементом, где операции решетки задаются ограничением соответствующих операций арифметической решетки. Это специфическое свойство отличает арифметические решетки от алгебраических решеток , для которых компакты образуют только join-полурешетку . Оба эти класса полных решеток изучаются в теории доменов .

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

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

• Дискретный посет, то есть посет, такой что подразумевает, является решеткой тогда и только тогда, когда он имеет не более одного элемента. В частности, двухэлементный дискретный посет не является решеткой.${\displaystyle x\leq y}$${\displaystyle x=y,}$
• Хотя набор, частично упорядоченный по делимости, является решеткой, набор, упорядоченный таким образом, не является решеткой, поскольку пара 2, 3 не имеет соединения; аналогично, 2, 3 не имеет соединения в${\displaystyle \{1,2,3,6\}}$${\displaystyle \{1,2,3\}}$${\displaystyle \{2,3,6\}.}$
• Множество , частично упорядоченное по делимости, не является решеткой. Каждая пара элементов имеет верхнюю и нижнюю границы, но пара 2, 3 имеет три верхних границы, а именно 12, 18 и 36, ни одна из которых не является наименьшей из трех по делимости (12 и 18 не делят друг друга). Аналогично пара 12, 18 имеет три нижних границы, а именно 1, 2 и 3, ни одна из которых не является наибольшей из трех по делимости (2 и 3 не делят друг друга).${\displaystyle \{1,2,3,12,18,36\}}$

Соответствующее понятие морфизма между двумя решетками легко вытекает из приведенного выше алгебраического определения. Даны две решетки и гомоморфизм решеток из L в M — это функция такая, что для всех${\displaystyle \left(L,\vee _{L},\wedge _{L}\right)}$${\displaystyle \left(M,\vee _{M},\wedge _{M}\right),}$${\displaystyle f:L\to M}$${\displaystyle a,b\in L:}$$${\displaystyle f\left(a\vee _{L}b\right)=f(a)\vee _{M}f(b),{\text{ and }}}$$$${\displaystyle f\left(a\wedge _{L}b\right)=f(a)\wedge _{M}f(b).}$$

Таким образом, является гомоморфизмом двух базовых полурешеток . Когда рассматриваются решетки с большей структурой, морфизмы должны «уважать» и дополнительную структуру. В частности, гомоморфизм ограниченной решетки (обычно называемый просто «гомоморфизмом решетки») между двумя ограниченными решетками и должен также обладать следующим свойством:${\displaystyle f}$${\displaystyle f}$${\displaystyle L}$${\displaystyle M}$$${\displaystyle f\left(0_{L}\right)=0_{M},{\text{ and }}}$$$${\displaystyle f\left(1_{L}\right)=1_{M}.}$$

В теоретико-порядковой формулировке эти условия просто утверждают, что гомоморфизм решеток — это функция, сохраняющая бинарные meets и joins. Для ограниченных решеток сохранение наименьшего и наибольшего элементов — это просто сохранение join и meet пустого множества.

Любой гомоморфизм решеток обязательно монотонен относительно соответствующего отношения порядка; см. Функция сохранения предела . Обратное неверно: монотонность никоим образом не подразумевает требуемого сохранения встреч и соединений (см. рис. 9), хотя сохраняющая порядок биекция является гомоморфизмом, если ее обратная также сохраняет порядок.

Учитывая стандартное определение изоморфизмов как обратимых морфизмов, решеточный изоморфизм — это просто биективный решеточный гомоморфизм. Аналогично, решеточный эндоморфизм — это решеточный гомоморфизм из решетки в себя, а решеточный автоморфизм — это биективный решеточный эндоморфизм. Решетки и их гомоморфизмы образуют категорию .

Пусть и — две решетки с 0 и 1. Гомоморфизм из в называется 0 , 1 — разделяющим тогда и только тогда, когда ( разделяет 0 ) и ( разделяет 1).${\displaystyle \mathbb {L} }$${\displaystyle \mathbb {L} '}$${\displaystyle \mathbb {L} }$${\displaystyle \mathbb {L} '}$ ${\displaystyle f^{-1}\{f(0)\}=\{0\}}$${\displaystyle f}$${\displaystyle f^{-1}\{f(1)\}=\{1\}}$${\displaystyle f}$

Подрешетка решетки — это подмножество решетки , которое является решеткой с теми же операциями встречи и соединения, что и То есть, если — решетка и — подмножество такой, что для каждой пары элементов и находятся в , то — подрешетка ^[3]${\displaystyle L}$${\displaystyle L}$${\displaystyle L.}$${\displaystyle L}$${\displaystyle M}$${\displaystyle L}$${\displaystyle a,b\in M}$${\displaystyle a\wedge b}$${\displaystyle a\vee b}$${\displaystyle M,}$${\displaystyle M}$${\displaystyle L.}$

Подрешетка решетки является выпуклой подрешеткой , если и подразумевает, что принадлежит для всех элементов${\displaystyle M}$${\displaystyle L}$${\displaystyle L,}$${\displaystyle x\leq z\leq y}$${\displaystyle x,y\in M}$${\displaystyle z}$${\displaystyle M,}$${\displaystyle x,y,z\in L.}$

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

ЧУМ называется полной решеткой , если все его подмножества имеют как join, так и meet. В частности, каждая полная решетка является ограниченной решеткой. В то время как ограниченные гомоморфизмы решеток в общем случае сохраняют только конечные join и meet, полные гомоморфизмы решеток должны сохранять произвольные join и meet.

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

«Частичная решетка» не является противоположностью «полной решетке» — скорее, «частичная решетка», «решетка» и «полная решетка» являются все более ограничительными определениями.

Условно полная решетка — это решетка, в которой каждое непустое подмножество , имеющее верхнюю границу, имеет соединение (то есть наименьшую верхнюю границу). Такие решетки обеспечивают наиболее прямое обобщение аксиомы полноты действительных чисел . Условно полная решетка — это либо полная решетка, либо полная решетка без ее максимального элемента, либо ее минимального элемента, либо и то, и другое. ^{[4] [5]}${\displaystyle 1,}$${\displaystyle 0,}$

Поскольку решетки имеют две бинарные операции, естественно задаться вопросом, распределяется ли одна из них по другой, то есть выполняется ли один или другой из следующих дуальных законов для каждых трех элементов :${\displaystyle a,b,c\in L,}$

Распределение более${\displaystyle \vee }$${\displaystyle \wedge }$

$${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c).}$$

Распределение более${\displaystyle \wedge }$${\displaystyle \vee }$

$${\displaystyle a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c).}$$

Решетка, которая удовлетворяет первой или, что эквивалентно (как выясняется), второй аксиоме, называется дистрибутивной решеткой . Единственные недистрибутивные решетки с менее чем 6 элементами называются M ₃ и N ₅ ; ^[6] они показаны на рисунках 10 и 11 соответственно. Решетка является дистрибутивной тогда и только тогда, когда она не имеет подрешетки, изоморфной M ₃ или N ₅ . ^[7] Каждая дистрибутивная решетка изоморфна решетке множеств (с объединением и пересечением как join и meet соответственно). ^[8]

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

Для некоторых приложений условие дистрибутивности слишком сильное, и следующее более слабое свойство часто бывает полезным. Решетка является модулярной , если для всех элементов выполняется следующее тождество: ( Модулярное тождество ) Это условие эквивалентно следующей аксиоме: подразумевает ( Модулярный закон ) Решетка является модулярной тогда и только тогда, когда она не имеет подрешетки, изоморфной N ₅ (показано на рис. 11). ^[7] Помимо дистрибутивных решеток, примерами модулярных решеток являются решетка подмодулей модуля ( следовательно, модулярная ), решетка двусторонних идеалов кольца и решетка нормальных подгрупп группы . Набор членов первого порядка с упорядочением «более специфичен, чем» является немодулярной решеткой, используемой в автоматизированных рассуждениях .${\displaystyle (L,\vee ,\wedge )}$${\displaystyle a,b,c\in L,}$${\displaystyle (a\wedge c)\vee (b\wedge c)=((a\wedge c)\vee b)\wedge c.}$
${\displaystyle a\leq c}$${\displaystyle a\vee (b\wedge c)=(a\vee b)\wedge c.}$

Конечная решетка является модулярной тогда и только тогда, когда она является как верхней, так и нижней полумодулярностью . Для градуированной решетки (верхняя) полумодулярность эквивалентна следующему условию на ранговую функцию${\displaystyle r\colon }$

${\displaystyle r(x)+r(y)\geq r(x\wedge y)+r(x\vee y).}$

Другим эквивалентным (для градуированных решеток) условием является условие Биркгофа :

для каждого и в если и оба покрывают, то покрывает и и${\displaystyle x}$${\displaystyle y}$${\displaystyle L,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\wedge y,}$${\displaystyle x\vee y}$${\displaystyle x}$${\displaystyle y.}$

Решетка называется полумодулярной снизу, если ее дуальная решетка полумодулярна. Для конечных решеток это означает, что предыдущие условия выполняются с и меняются местами, «покрывает» меняется на «покрывается», а неравенства меняются местами. ^[9]${\displaystyle \vee }$${\displaystyle \wedge }$

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

• Непрерывная решетка — это полная решетка, которая непрерывна как частично упорядоченное множество.
• Алгебраическая решетка — это полная решетка, которая является алгебраической как частично упорядоченное множество.

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

Пусть — ограниченная решетка с наибольшим элементом 1 и наименьшим элементом 0. Два элемента и являются дополнениями друг друга тогда и только тогда, когда :${\displaystyle L}$${\displaystyle x}$${\displaystyle y}$${\displaystyle L}$$${\displaystyle x\vee y=1\quad {\text{ and }}\quad x\wedge y=0.}$$

В общем случае некоторые элементы ограниченной решетки могут не иметь дополнения, а другие могут иметь более одного дополнения. Например, множество с его обычным порядком является ограниченной решеткой и не имеет дополнения. В ограниченной решетке N ₅ элемент имеет два дополнения, а именно и (см. рис. 11). Ограниченная решетка, для которой каждый элемент имеет дополнение, называется дополненной решеткой .${\displaystyle \{0,1/2,1\}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

Дополняемая решетка, которая также является дистрибутивной, является булевой алгеброй . Для дистрибутивной решетки дополнение , когда оно существует, является единственным.${\displaystyle x,}$

В случае, если дополнение уникально, мы записываем и, что эквивалентно, Соответствующая унарная операция над , называемая дополнением, вводит аналог логического отрицания в теорию решеток.${\textstyle \lnot x=y}$${\textstyle \lnot y=x.}$${\displaystyle L,}$

Алгебры Гейтинга являются примером дистрибутивных решеток, в которых некоторые элементы могут не иметь дополнений. С другой стороны, каждый элемент алгебры Гейтинга имеет псевдодополнение , также обозначаемое Псевдодополнение — это наибольший элемент , такой что Если псевдодополнение каждого элемента алгебры Гейтинга на самом деле является дополнением, то алгебра Гейтинга на самом деле является булевой алгеброй.${\displaystyle z}$${\textstyle \lnot x.}$${\displaystyle y}$${\displaystyle x\wedge y=0.}$

Цепь от до — это множество , где Длина этой цепи равна n или на единицу меньше числа ее элементов. Цепь максимальна , если покрывает все${\displaystyle x_{0}}$${\displaystyle x_{n}}$${\displaystyle \left\{x_{0},x_{1},\ldots ,x_{n}\right\},}$${\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}.}$${\displaystyle x_{i}}$${\displaystyle x_{i-1}}$${\displaystyle 1\leq i\leq n.}$

Если для любой пары и где все максимальные цепи из имеют одинаковую длину, то говорят, что решетка удовлетворяет условию цепи Жордана–Дедекинда .${\displaystyle x}$${\displaystyle y,}$${\displaystyle x<y,}$${\displaystyle x}$${\displaystyle y}$

Решетка называется градуированной , иногда ранжированной (но см. Ранжированное частично упорядоченное множество для альтернативного значения), если она может быть снабжена функцией ранга иногда до , совместимой с порядком (так что всякий раз ), такой, что всякий раз покрывает то Значение функции ранга для элемента решетки называется его рангом .${\displaystyle (L,\leq )}$ ${\displaystyle r:L\to \mathbb {N} }$${\displaystyle \mathbb {Z} }$${\displaystyle r(x)<r(y)}$${\displaystyle x<y}$${\displaystyle y}$ ${\displaystyle x,}$${\displaystyle r(y)=r(x)+1.}$

Говорят, что элемент решетки покрывает другой элемент, если но не существует такого , что Здесь означает и${\displaystyle y}$${\displaystyle x,}$${\displaystyle y>x,}$${\displaystyle z}$${\displaystyle y>z>x.}$${\displaystyle y>x}$${\displaystyle x\leq y}$${\displaystyle x\neq y.}$

Любое множество может быть использовано для генерации свободной полурешетки Свободная полурешетка определяется как состоящая из всех конечных подмножеств с операцией полурешетки, заданной обычным объединением множеств . Свободная полурешетка обладает универсальным свойством . Для свободной решетки над множеством Уитмен дал конструкцию, основанную на многочленах над элементами . ^{[10] [11]}${\displaystyle X}$ ${\displaystyle FX.}$${\displaystyle X,}$${\displaystyle X,}$ ${\displaystyle X}$

Теперь мы определим некоторые понятия теории порядка, имеющие значение для теории решеток. В дальнейшем пусть будет элементом некоторой решетки, называемой:${\displaystyle x}$${\displaystyle L.}$ ${\displaystyle x}$

• Join unreducible if влечет for all If имеет нижний элемент некоторые авторы требуют . ^[12] Когда первое условие обобщается на произвольные соединения, оно называется полностью join unreducible (или -irreducible). Двойственное понятие — meet unreducibility ( -irreducible). Например, на рис. 2 элементы 2, 3, 4 и 5 являются join unreducible, в то время как 12, 15, 20 и 30 являются meet unreducible. В зависимости от определения нижний элемент 1 и верхний элемент 60 могут или не могут считаться join unreducible и meet unreducible соответственно. В решетке действительных чисел с обычным порядком каждый элемент является join unreducible, но ни один не является полностью join unreducible.${\displaystyle x=a\vee b}$${\displaystyle x=a{\text{ or }}x=b.}$${\displaystyle a,b\in L.}$${\displaystyle L}$${\displaystyle 0,}$${\displaystyle x\neq 0}$${\displaystyle \bigvee _{i\in I}a_{i},}$ ${\displaystyle x}$${\displaystyle \vee }$${\displaystyle \wedge }$
• Join prime if ought Опять же, некоторые авторы требуют , хотя это необычно. ^[13] Это также можно обобщить, чтобы получить понятие полностью join prime . Двойственное понятие — meet prime . Каждый join-prime элемент также join неприводим, и каждый meet-prime элемент также meet неприводим. Обратное верно, если является дистрибутивным.${\displaystyle x\leq a\vee b}$${\displaystyle x\leq a{\text{ or }}x\leq b.}$${\displaystyle x\neq 0}$${\displaystyle L}$

Пусть есть нижний элемент 0. Элемент является атомом , если и не существует такого элемента, что Тогда называется:${\displaystyle L}$${\displaystyle x}$${\displaystyle L}$${\displaystyle 0<x}$${\displaystyle y\in L}$${\displaystyle 0<y<x.}$${\displaystyle L}$

• Атомарный , если для каждого ненулевого элемента существует атом такой , что ^[14]${\displaystyle x}$${\displaystyle L,}$${\displaystyle a}$${\displaystyle L}$${\displaystyle a\leq x;}$
• Атомистический , если каждый элемент является супремумом атомов. ^[15]${\displaystyle L}$

Однако многие источники и математические сообщества используют термин «атомарный» в значении «атомистический», как определено выше. ^{[ необходима ссылка ]}

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

• Присоединяйтесь и знакомьтесь  – Концепция в теории порядка
• Карта решеток  – Концепция в математике
• Ортодополненная решетка
• Полный порядок  – порядок, все элементы которого сравнимы.
• Идеал  – непустое, ограниченное сверху, замкнутое вниз подмножество и фильтр (двойственные понятия)
• Косая решетка  – алгебраическая структура Pages displaying wikidata descriptions as a fallback(обобщение до некоммутативного соединения и встречи)
• Эйлерова решетка
• Решетка Поста  – решетка всех клонов (множеств логических связок, замкнутых относительно композиции и содержащих все проекции) на двухэлементном множестве {0, 1}, упорядоченная по включениюPages displaying wikidata descriptions as a fallback
• Решетка Тамари  – математический объект, образованный порядком по способу заключения выражения в скобки.Pages displaying wikidata descriptions as a fallback
• Решетка Юнга–Фибоначчи
• 0,1-простая решетка

This article is in list format but may read better as prose. You can help by converting this article, if appropriate. Editing help is available. (March 2017)

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

• Бессмысленная топология
• Решетка подгрупп
• Спектральное пространство
• Инвариантное подпространство
• Оператор закрытия
• Абстрактная интерпретация
• Решетка подчинения
• Теория нечетких множеств
• Алгебраизации логики первого порядка
• Семантика языков программирования
• Теория домена
• Онтология (информатика)
• Множественное наследование
• Формальный концептуальный анализ и Lattice Miner (теория и инструмент)
• Фильтр Блума
• Поток информации
• Порядковая оптимизация
• Квантовая логика
• Медианный график
• Пространство знаний
• Регулярное изучение языка
• Аналоговое моделирование