Решетка (заказать)

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

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

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

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

Определение

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

Как частично заказанный набор

Частично упорядоченное множество ( ЧУУ) называется решеткой, если оно является одновременно объединенной и встречно- полурешеткой , т. е. каждое двухэлементное подмножество имеет соединение (т. е. наименьшую верхнюю границу, обозначаемое ) и двойственное соединение (т. е. наибольшую нижнюю границу) . связанный, обозначается ). Это определение делает и бинарные операции . Обе операции монотонны относительно заданного порядка: из нее следует, что и ${\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}.}$

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

Учитывая подмножество решетки, функции meet и join ограничиваются частичными функциями — они не определены, если их значение не находится в подмножестве. Результирующая структура называется ${\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 \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\}}$

Подключение к другим алгебраическим структурам

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

Благодаря коммутативности, ассоциативности и идемпотентности соединение и встречу можно рассматривать как операции над непустыми конечными множествами, а не над парами элементов. В ограниченной решетке также можно определить соединение и соединение пустого множества (как и соответственно). Это делает ограниченные решетки несколько более естественными, чем общие решетки, и многие авторы требуют, чтобы все решетки были ограниченными. ${\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}$
• Всякая полная решетка (см. также ниже) является (достаточно специфичной) ограниченной решеткой. Этот класс дает начало широкому спектру практических примеров .
• Множество компактных элементов арифметической полной решетки представляет собой решетку с наименьшим элементом, где операции решетки задаются ограничением соответствующих операций арифметической решетки. Это специфическое свойство, которое отличает арифметические решетки от алгебраических решеток , для которых компакты образуют только соединение-полурешетку . Оба эти класса полных решеток изучаются в теории областей .

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

Примеры нерешеток

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

• Дискретное ЧУ-множество, то есть такое ЧУ-множество, из которого следует, что оно является решеткой тогда и только тогда, когда оно имеет не более одного элемента. В частности, двухэлементное дискретное ЧУУ не является решеткой. ${\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}.}$$

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

Любой гомоморфизм решеток обязательно монотонен относительно связанного с ним отношения порядка; см. функцию сохранения предела . Обратное неверно: монотонность ни в коем случае не предполагает требуемого сохранения встреч и объединений (см. рис. 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.}$

Подрешетка решетки — это выпуклая подрешетка оператора if и подразумевает, принадлежащая для всех элементов ${\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.}$

Свойства решеток

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

Полнота

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

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

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

Условная полнота

Условно полная решетка — это решетка, в которой каждое непустое подмножество , имеющее верхнюю границу, имеет соединение (то есть наименьшую верхнюю границу). Такие решетки обеспечивают наиболее прямое обобщение аксиомы полноты действительных чисел . Условно полная решетка — это либо полная решетка, либо полная решетка без максимального элемента, минимального элемента или того и другого. ^{[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] Каждая дистрибутивная решетка изоморфна решетке множеств (с объединением и пересечением как соединением и пересечением соответственно). ^[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}$

• Соединение нередуцируемого if подразумевает для всех If имеет нижний элемент, который требуется некоторым авторам . ^[12] Когда первое условие обобщается на произвольные соединения, называется полностью несводимым (или -несводимым) соединением . Двойственное понятие — это неприводимость ( -irreducible). Например, на Рис. 2 элементы 2, 3, 4 и 5 объединены неприводимыми, а элементы 12, 15, 20 и 30 — несократимыми. В зависимости от определения нижний элемент 1 и верхний элемент 60 могут считаться или не считаться соединяемыми и несоединяемыми соответственно. В решетке действительных чисел обычного порядка каждый элемент несократим по объединению, но ни один из них не является полностью неприводимым по объединению. ${\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 подразумевает И снова некоторые авторы требуют , хотя это необычно. ^[13] Это тоже можно обобщить, чтобы получить понятие « полное соединение простого числа» . Двойственное понятие — это встретить простое число . Каждый простой элемент соединения также неприводим к соединению, и каждый элемент простого соединения также неприводим. Обратное верно, если дистрибутивно. ${\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. «так как и двойственно». Биркгоф приписывает это Дедекинду 1897, с. 8 ${\displaystyle a=a\vee (a\wedge (a\vee a))=a\vee a}$
3. Беррис, Стэнли Н. и Санкаппанавар, HP, 1981. Курс универсальной алгебры. Спрингер-Верлаг. 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». Анналы математики . 42 (1): 325–329. дои : 10.2307/1969001. JSTOR  1969001.
11. Филип Уитмен (1942). «Свободные решетки II». Анналы математики . 43 (1): 104–115. дои : 10.2307/1968883. JSTOR  1968883.
12. Дэйви и Пристли 2002, с. 53.
13. Хоффманн, Рудольф-Э. (1981). Непрерывные частично упорядоченные множества, простые спектры вполне дистрибутивных полных решеток и хаусдорфовы компактификации . Непрерывные решетки. Том. 871. стр. 159–208. дои : 10.1007/BFb0089907.
14. Гретцер 2003, с. 246, Упражнение 3.
15. Гретцер 2003, с. 234, после Def.1.

Рекомендации

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

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

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

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

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

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

Передовые монографии:

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

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

• Р. Фриз, Дж. Джезек и Дж. Б. Нэйшн, 1985. «Свободные решетки». Математические обзоры и монографии Vol. 42. Математическая ассоциация Америки .
• Джонстон, ПТ , 1982. Каменные пространства . Кембриджские исследования по высшей математике 3. Издательство Кембриджского университета.

К истории теории решеток:

• Штепанка Билова (2001). Эдуард Фукс (ред.). Теория решеток — ее рождение и жизнь (PDF) . Прометей. стр. 250–257.
• Биркгоф, Гаррет (1948). Теория решеток (2-е изд.).Учебник с многочисленными ссылками в сносках.
• Шлимм, Дирк (ноябрь 2011 г.). «О творческой роли аксиоматики. Открытие решеток Шредером, Дедекиндом, Биркгофом и другими». Синтезируйте . 183 (1): 47–68. CiteSeerX  10.1.1.594.8898 . дои : 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]
• Вайсштейн, Эрик В. «Решетка». Математический мир .
• JB Nation, Заметки по теории решеток, конспекты курса, переработанные в 2017 г.
• Ральф Фриз, «Домашняя страница теории решеток».
• Последовательность OEIS A006966 (Количество немаркированных решеток с n элементами)