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

Набор, пары которых имеют минимумы и максимумы

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

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

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

Определение

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

Как частично упорядоченный набор

Частично упорядоченное множество ( посет) называется решеткой , если оно является как 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\}}$

Морфизмы решеток

Рис. 9: Монотонное отображение между решетками, которое не сохраняет ни соединений, ни пересечений, поскольку и ${\displaystyle f}$ ${\displaystyle f(u)\vee f(v)=u^{\prime }\vee u^{\prime }=u^{\prime }}$ ${\displaystyle \neq }$ ${\displaystyle 1^{\prime }=f(1)=f(u\vee v)}$ ${\displaystyle f(u)\wedge f(v)=u^{\prime }\wedge u^{\prime }=u^{\prime }}$ ${\displaystyle \neq }$ ${\displaystyle 0^{\prime }=f(0)=f(u\wedge v).}$

Соответствующее понятие морфизма между двумя решетками легко вытекает из приведенного выше алгебраического определения. Даны две решетки и гомоморфизм решеток из 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-простая решетка

Приложения, использующие теорию решеток

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

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

Примечания

1. Грэтцер 2003, стр. 52.
2. Биркгоф 1948, стр. 18. "since and dually". Биркгоф приписывает это Дедекинду 1897, стр. 8 ${\displaystyle a=a\vee (a\wedge (a\vee a))=a\vee a}$
3. Беррис, Стэнли Н. и Санкаппанавар, Х. П., 1981. Курс универсальной алгебры. Springer-Verlag. ISBN  3-540-90578-2 .
4. Бейкер, Кирби (2010). "Полные решетки" (PDF) . Кафедра математики Калифорнийского университета в Лос-Анджелесе . Получено 8 июня 2022 г.
5. Капланский, Ирвинг (1972). Теория множеств и метрические пространства (2-е изд.). Нью-Йорк: AMS Chelsea Publishing . стр. 14. ISBN 9780821826942.
6. Дэйви и Пристли (2002), Упражнение 4.1, стр. 104.
7. Дэви и Пристли (2002), Теорема 4.10, стр. 89.
8. Дэви и Пристли (2002), Теорема 10.21, стр. 238–239.
9. Стэнли, Ричард П. (1997), Перечислительная комбинаторика (т. 1) , Cambridge University Press, стр. 103–104, ISBN 0-521-66351-2
10. Филип Уитмен (1941). «Свободные решетки I». Annals of Mathematics . 42 (1): 325–329. doi :10.2307/1969001. JSTOR  1969001.
11. Филип Уитмен (1942). «Свободные решетки II». Annals of Mathematics . 43 (1): 104–115. doi :10.2307/1968883. JSTOR  1968883.
12. Дэйви и Пристли 2002, стр. 53.
13. Хоффманн, Рудольф-Э. (1981). Непрерывные частично упорядоченные множества, простые спектры полностью дистрибутивных полных решеток и компактификации Хаусдорфа . Непрерывные решетки. Т. 871. С. 159–208. doi :10.1007/BFb0089907.
14. Грэтцер 2003, стр. 246, Упражнение 3.
15. Grätzer 2003, стр. 234, после Def.1.

Ссылки

Монографии доступны бесплатно онлайн:

• Беррис, Стэнли Н. и Санкаппанавар, Х. П., 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2 . 
• Джипсен, Питер и Генри Роуз, Многообразия решеток , Lecture Notes in Mathematics 1533, Springer Verlag, 1992. ISBN 0-387-56314-8 . 

Элементарные тексты, рекомендуемые для лиц с ограниченной математической зрелостью :

• Доннеллан, Томас, 1968. Теория решеток . Пергамон.
• Гретцер, Джордж , 1971. Теория решеток: первые концепции и распределительные решетки . WH Freeman.

Стандартный современный вводный текст, несколько сложнее, чем приведенный выше:

• Дэви, BA; Пристли, HA (2002), Введение в решетки и порядок , Cambridge University Press , ISBN 978-0-521-78451-1

Расширенные монографии:

• Гаррет Биркгофф , 1967. Теория решеток , 3-е изд. Том 25 AMS Colloquium Publications. Американское математическое общество .
• Роберт П. Дилворт и Кроули, Питер, 1973. Алгебраическая теория решеток . Prentice-Hall. ISBN 978-0-13-022269-5 . 
• Гретцер, Джордж (2003). Общая теория решеток (второе изд.). Базель: Birkhäuser. ISBN 978-3-7643-6996-5.

На свободных решетках:

• R. Freese, J. Jezek и JB Nation, 1985. "Свободные решетки". Математические обзоры и монографии, том 42. Математическая ассоциация Америки .
• Джонстон, ПТ , 1982. Стоун-пространства . Кембриджские исследования по высшей математике 3. Издательство Кембриджского университета.

Об истории теории решеток:

• Štĕpánka Bilová (2001). Eduard Fuchs (ред.). Теория решеток — ее рождение и жизнь (PDF) . Prometheus. стр. 250–257.
• Биркгоф, Гарретт (1948). Теория решеток (2-е изд.).Учебник с многочисленными ссылками в сносках.
• Шлимм, Дирк (ноябрь 2011 г.). «О творческой роли аксиоматики. Открытие решеток Шредером, Дедекиндом, Биркгофом и другими». Synthese . 183 (1): 47–68. CiteSeerX  10.1.1.594.8898 . doi :10.1007/s11229-009-9667-9. S2CID  11012081.Краткая история решеток.
• Дедекинд, Рихард (1897), «Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler» (PDF) , Braunschweiger Festschrift , doi : 10.24355/dbbs.084-200908140200-2

О приложениях теории решеток:

• Гаррет Биркгофф (1967). Джеймс С. Эббот (ред.). Что могут сделать для вас решетки? . Ван Ностранд.Оглавление

Внешние ссылки

• «Группа, упорядоченная по решетке», Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. "Решетка". MathWorld .
• JB Nation, Заметки по теории решеток, курсовые заметки, пересмотренные в 2017 году.
• Ральф Фриз, «Домашняя страница теории решеток».
• Последовательность OEIS A006966 (Количество немаркированных решеток с n элементами)