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

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

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

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

Решетки как частично упорядоченные множества [ править ]

Если ( L , ≤) является частично упорядоченное множество (ч.у.м.), и S ⊆ L произвольное подмножество, то элемент U ∈ L называется быть верхняя граница из S , если s ≤ U для каждого s ∈ S . У набора может быть много верхних границ или вообще не быть. Верхняя граница u для S называется ее наименьшей верхней границей , соединением или супремумом , если u ≤ x для каждой верхней границых из S . У набора не обязательно должна быть наименьшая верхняя граница, но не может быть более одной. Двойственно , л ∈ L называется быть нижней границей из S , если л ≤ ева для каждого s ∈ S . Нижняя граница л из S назовем его точная нижняя граница , или встречаются , или инфимумом , если х ≤ л для каждой нижней грани х из S. Набор может иметь много нижних границ или не иметь вовсе, но может иметь не более одной наибольшей нижней границы.

Частично упорядоченное множество ( L , ≤) называется присоединиться к -полурешетка , если каждый из двух элементов подмножества { , Ь } ⊆ L имеет присоединиться (т.е. минимум до верхней границы), и называется Meet-полурешетка , если каждый из двух элементов подмножество имеет пересечение (т.е. точную нижнюю границу), обозначаемую соответственно a ∨ b и a ∧ b . ( L , ≤) называется решеткой, если она одновременно является полурешеткой соединения и встречной. Это определение делает бинарные операции ∨ и operations. Обе операции монотонны относительно заданного порядка: a ₁ ≤ a ₂ и b ₁ ≤ b ₂ означает, что a ₁ ∨ b ₁ ≤ a ₂ ∨ b ₂ и a ₁ ∧ b ₁ ≤ a ₂ ∧ b ₂ .

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

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

0 ≤ х ≤ 1 для каждого х в L .

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

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

${\displaystyle \bigvee \left(A\cup B\right)=\left(\bigvee A\right)\vee \left(\bigvee B\right)}$

и

${\displaystyle \bigwedge \left(A\cup B\right)=\left(\bigwedge A\right)\wedge \left(\bigwedge B\right)}$

держать. Принимая B за пустое множество,

${\displaystyle \bigvee \left(A\cup \emptyset \right)=\left(\bigvee A\right)\vee \left(\bigvee \emptyset \right)=\left(\bigvee A\right)\vee 0=\bigvee A}$

и

${\displaystyle \bigwedge \left(A\cup \emptyset \right)=\left(\bigwedge A\right)\wedge \left(\bigwedge \emptyset \right)=\left(\bigwedge A\right)\wedge 1=\bigwedge A}$

что согласуется с тем, что .${\displaystyle A\cup \emptyset =A}$

Говорят, что элемент решетки y покрывает другой элемент x , если y > x , но не существует z такого, что y > z > x . Здесь y > x означает x ≤ y и x ≠ y .

Решетка ( L , ≤) называется градуированной , иногда ранжированной (но см. Ранговое множество для альтернативного значения), если она может быть оснащена функцией ранга r от L до, иногда до ℤ, совместимой с упорядочением (так что r ( x ) < r ( y ) всякий раз, когда x < y ) такой, что всякий раз, когда y покрывает x , то r ( y ) = r ( x ) + 1. Значение функции ранга элемента решетки называется его рангом .

Учитывая подмножество решетки, H ⊆ L , встречаются и присоединитесь ограничиться частичными функциями - они не определены , если их стоимость не входит в подмножество Н . Полученная структура на 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}$

Следующие два тождества также обычно рассматриваются как аксиомы, даже если они следуют из двух законов поглощения, взятых вместе. ^{[примечание 1]} Это называется идемпотентными законами .

${\displaystyle a\vee a=a}$

${\displaystyle a\wedge a=a}$

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

Ограниченная решетка [ править ]

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

См. Полурешетку для получения дополнительной информации.

Связь с другими алгебраическими структурами [ править ]

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

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

Алгебраическая интерпретация решеток играет важную роль в универсальной алгебре .

Связь между двумя определениями [ править ]

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

Обратное также верно. Для данной алгебраически определенной решетки ( L , ∨, ∧) можно определить частичный порядок ≤ на L , положив

a ≤ b, если a = a ∧ b , или

a ≤ b, если b = a ∨ b ,

для всех элементов через и Ь из L . Законы поглощения гарантируют, что оба определения эквивалентны:

a = a ∧ b влечет b = b ∨ ( b ∧ a ) = ( a ∧ b ) ∨ b = a ∨ b

и вдвойне в другом направлении.

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

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

Примеры [ править ]

• Рис. 1: Подмножества {x, y, z} при включении множества . Название «решетка» подсказано формой изображающей ее диаграммы Хассе .

• Рис. 2: Решетка целых делителей 60, упорядоченная по принципу « делит ».

• Рис. 3: Решетка перегородок из {1, 2, 3, 4}, по заказу " уточняет ".

• Рис. 4: Решетка натуральных чисел, упорядоченная по ≤.

• Рис. 5: Решетка неотрицательных целочисленных пар, упорядоченная покомпонентно.

• Для любого множества А , совокупность всех подмножеств множества A ( так называемых силовой агрегат из А ) можно заказать с помощью включения подмножества , чтобы получить ограниченную решетку А сами и пустого множество. Задайте пересечение и объединение, интерпретацию, встречу и соединение соответственно (см. Рис. 1).
• Для любого множества A набор всех конечных подмножеств A , упорядоченных по включению, также является решеткой и будет ограниченным тогда и только тогда, когда A конечно.
• Для любого множества А , совокупность всех разделов из A , упорядоченных по утонченности , является решеткой (см. Фото 3).
• Эти положительные целые числа в их обычном порядке образуют решетку, в соответствии с операциями «мин» и «макс». 1 - нижний; верха нет (см. рис. 4).
• Декартовый квадрат из натуральных чисел, упорядочены так , что ( , б ) ≤ ( с , d ) , если ≤ C и B ≤ d . Пара (0, 0) - нижний элемент; верха нет (см. рис. 5).
• Натуральные числа также образуют решетку при операциях взятия наибольшего общего делителя и наименьшего общего кратного , с делимостью в качестве отношения порядка: a ≤ b, если a делит b . 1 - нижний; 0 - верх. Рис. 2 показана конечная подрешетка.
• Всякая полная решетка (см. Также ниже ) является (довольно специфической) ограниченной решеткой. Этот урок дает повод для широкого круга практических примеров .
• Множество компактных элементов в качестве арифметической полной решетки является решеткой с наималейшим элементом, где решетки операции заданного путем ограничения соответствующих операций арифметической решетки. Это специфическое свойство, которое отличает арифметические решетки от алгебраических решеток , для которых компакты образуют только полурешетку соединения . Оба эти класса полных решеток изучаются в теории областей .

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

Примеры нерешеток [ править ]

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

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

Морфизмы решеток [ править ]

Соответствующее понятие морфизма между двумя решетками легко вытекает из приведенного выше алгебраического определения. Принимая во внимание две решетки ( L , ∨ _L , ∧ _L ) и ( М , ∨ _М , ∧ _М ) , А решеточный гомоморфизм из L в M является функцией F  : L → М такое , что для всех в , б ∈ L :

f ( a ∨ _L b ) = f ( a ) ∨ _M f ( b ) и

f ( a ∧ _L b ) = f ( a ) ∧ _M f ( b ).

Таким образом, f является гомоморфизмом двух лежащих в основе полурешеток . Когда рассматриваются решетки с большей структурой, морфизмы также должны «уважать» дополнительную структуру. В частности, гомоморфизм ограниченной решетки (обычно называемый просто «решеточным гомоморфизмом») f между двумя ограниченными решетками L и M также должен обладать следующим свойством:

f (0 _L ) = 0 _M и

f (1 _л ) = 1 _м .

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

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

Подрешетки [ править ]

Подрешетки из решетки L представляет собой подмножество L , что является решеткой с одной и той же встречаются и присоединиться к операции , как L . То есть, если L является решеткой , и М представляет собой подмножество L таких , что для каждой пары элементов через , Ь в М и ∧ б и ∨ Ь находятся в М , то М является подструктурой L . ^[2]

Подрешетка М из решетки L является выпуклой подрешеткой из L , если х ≤ г ≤ у и х , у в М означают , что г принадлежит М , для всех элементов х , у , г в L .

Свойства решеток [ править ]

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

Полнота [ править ]

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

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

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

Условная полнота [ править ]

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

Распределительность [ править ]

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

Распределимость ∨ над ∨

a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ).

Распределимость ∧ над ∧

a ∧ ( b ∨ c ) = ( a ∧ b ) ∨ ( a ∧ c ).

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

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

Модульность [ править ]

Для некоторых приложений условие дистрибутивности слишком сильное, и часто бывает полезно следующее более слабое свойство. Решетка ( L , ∨, ∧) является модульной , если для всех элементов через , Ь , с из L , имеет место тождество.

Модульная идентичность

( a ∧ c ) ∨ ( b ∧ c ) = (( a ∧ c ) ∨ b ) ∧ c .

Это условие эквивалентно следующей аксиоме.

Модульное право

a ≤ c влечет a ∨ ( b ∧ c ) = ( a ∨ b ) ∧ c .

Решетка является модульной тогда и только тогда, когда в ней нет подрешетки, изоморфной N ₅ (показано на рис. 11). ^[4] Кроме распределительных решеток, примеры модульных решеток решетка двусторонних идеалов одного кольца , решетки подмодулей модуля , и решетка нормальных подгрупп одного группы . Набор терминов первого порядка с упорядочением « более конкретно , чем » не является модулярной решеткой используется в автоматизированных рассуждений .

Полумодулярность [ править ]

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

r ( x ) + r ( y ) ≥ r ( x ∧ y ) + r ( x ∨ y ).

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

для каждого x и y в L , если x и y покрывают x ∧ y , то x ∨ y покрывает и x, и y .

Решетка называется полумодулярной снизу, если двойственная к ней полумодулярна. Для конечных решеток это означает, что предыдущие условия выполняются с заменой ∨ и, заменой "покрытий" на "покрывается" и обращением неравенств. ^[6]

Непрерывность и алгебраичность [ править ]

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

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

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

Дополнения и псевдодополнения [ править ]

Пусть L ограниченная решетка с наибольшим элементом 1 и наименьшим элементом 0. Два элемента х и у из L являются дополняющими друг друга , если и только если:

х ∨ у = 1 и х ∧ у = 0 .

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

Дополненная решетка, которая также является дистрибутивной, является булевой алгеброй . Для дистрибутивной решетки дополнение к x , если оно существует, единственно.

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

Алгебры Гейтинга являются примером дистрибутивных решеток, в которых некоторые элементы могут не иметь дополнений. С другой стороны, каждый элемент x алгебры Гейтинга имеет псевдодополнение , также обозначаемое ¬ x . Псевдодополнение - это наибольший элемент y такой, что x ∧ y = 0 . Если псевдодополнение каждого элемента алгебры Гейтинга на самом деле является дополнением, то алгебра Гейтинга на самом деле является булевой алгеброй.

Условие цепи Джордана – Дедекинда [ править ]

Цепь от й ₀ до й _п представляет собой набора , где . Длина этой цепи п , или один меньше , чем его количество элементов. Цепь максимальна, если x _i покрывает x _{i −1} для всех 1 ≤ i ≤ n .${\displaystyle \{x_{0},x_{1},\ldots ,x_{n}\}}$${\displaystyle x_{0}<x_{1}<x_{2}<\ldots <x_{n}}$

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

Свободные решетки [ править ]

Любой набор X может быть использован для создания свободной полурешетки FX . Свободная полурешетка определяется как состоящая из всех конечных подмножеств X , а операция полурешетки задается обычным объединением множеств . Свободная полурешетка обладает универсальным свойством . Для свободной решетки над множеством X , Уитмен дал конструкцию , основанную на полиномы над X ' членами s. ^{[7] [8]}

Важные теоретико-решеточные понятия [ править ]

Теперь мы определим некоторые теоретико-порядковые понятия, важные для теории решеток. В дальнейшем пусть х быть элементом некоторой решетки L . Если L имеет нижний элемент 0, иногда требуется x ≠ 0 . x называется:

• Регистрация неприводимым , если х = ∨ Ь влечет х = а или х = Ь для всех а , Ь в Ь . Когда первое условие обобщается на произвольные соединения , x называется полностью неприводимым к соединению (или ∨-неприводимым). Двойственное понятие - это неприводимость (∧-неприводимость). Например, на рис. 2, элементы 2, 3, 4 и 5 являются неприводимыми к соединению, а элементы 12, 15, 20 и 30 - неприводимыми. В решетке действительных чисел${\displaystyle \bigvee _{i\in I}a_{i}}$ при обычном порядке каждый элемент является неприводимым к соединению, но ни один элемент не является полностью неприводимым к соединению.
• Регистрация простой , если х ≤ ∨ б влечет е ≤ а или х ≤ б . Это тоже можно обобщить, чтобы получить понятие полностью соединить простое число . Двойственное понятие - это простое совпадение . Каждый элемент с простым соединением также является неприводимым по соединению, и каждый элемент с простым соединением также является неприводимым. Обратное верно, если L дистрибутивна.

Пусть L имеет нижний элемент 0. Элемент x из L является атомом, если 0 < x и не существует такого элемента y из L , что 0 < y < x . Затем L вызывается:

• Атомарно, если для каждого ненулевого элемента x из L существует такой атом a из L , что a ≤ x ;
• Атомистично, если каждый элемент L является супремумом атомов.

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

См. Также [ править ]

• Присоединяйтесь и знакомьтесь
• Карта решеток
• Ортодополненная решетка
• Общий заказ
• Идеал и фильтр (двойственные понятия)
• Косая решетка (обобщение до некоммутативного соединения и встречи)
• Решетка Эйлера
• Решетка столба
• Решетка Тамари
• Решетка Юнга – Фибоначчи
• 0,1-простая решетка

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

Эта статья представлена ​​в виде списка , но может читаться лучше как проза . Вы можете помочь, преобразовав эту статью , если это необходимо. Доступна помощь по редактированию . ( Март 2017 г. )

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

• Бессмысленная топология
• Решетка подгрупп
• Спектральное пространство
• Инвариантное подпространство
• Оператор закрытия
• Абстрактная интерпретация
• Решетка поглощения
• Теория нечетких множеств

Примечания [ править ]

Ссылки [ править ]

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

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

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

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

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

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

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

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

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

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

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

• Štĕpánka Bilová (2001). Эдуард Фукс (ред.). Теория решеток - ее рождение и жизнь (PDF) . Прометей. С. 250–257.

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

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

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме решетки (порядка) .

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