Введение

Множество, пары элементов которого имеют минимумы и максимумы.

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

Определение

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

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

Частично упорядоченное множество (посеть) называется решеткой, если оно одновременно является объединяющей и встречающейся полурешеткой, то есть для любого двухэлементного подмножества существует объединение (то есть наименьшая верхняя граница, обозначаемая ∨) и, двойственно, встреча (то есть наибольшая нижняя граница, обозначаемая ∧). Это определение делает ∨ и ∧ бинарными операциями. Обе операции монотонны относительно заданного порядка: a ≤ b и c ≤ d влечет за собой a ∨ c ≤ b ∨ d и a ∧ c ≥ b ∧ d.

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

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

Сетки имеют некоторое отношение к семейству алгебраических структур, подобных группам. Поскольку операции встречи и объединения обладают как коммутативностью, так и ассоциативностью, решетку можно рассматривать как состоящую из двух коммутативных полугрупп с одинаковым носителем. Для ограниченной решетки эти полугруппы фактически являются коммутативными моноидами. Закон поглощения – единственное определяющее тождество, специфичное для теории решеток. Ограниченную решетку также можно рассматривать как коммутативное кольцо без дистрибутивного закона. Благодаря коммутативности, ассоциативности и идемпотентности, операции объединения и встречи можно рассматривать как операции над непустыми конечными множествами, а не над парами элементов. В ограниченной решетке объединение и встреча пустого множества также могут быть определены (как ⊤ и ⊥ соответственно). Это делает ограниченные решетки несколько более естественными, чем общие решетки, и многие авторы требуют, чтобы все решетки были ограниченными. Алгебраическая интерпретация решеток играет существенную роль в универсальной алгебре.

Примеры

Для любого множества коллекция всех его подмножеств (называемая множеством мощностей) может быть упорядочена по включению подмножеств, образуя решетку, ограниченную самим собой и пустым множеством. В этой решетке супремум задается объединением множеств, а инфимум – пересечением множеств (см. рис. 1). Для любого множества коллекция всех конечных подмножеств, упорядоченная по включению, также является решеткой и будет ограниченной тогда и только тогда, когда само множество конечно. Для любого множества, множество всех разбиений, упорядоченное по уточнению, является решеткой (см. рис. 3). Положительные целые числа в их обычном порядке образуют неограниченную решетку, с операциями "min" и "max". 1 является наименьшим элементом; наибольшего элемента нет (см. рис. 4). Декартово произведение натуральных чисел, упорядоченное так, что если , то пара является наименьшим элементом; наибольшего элемента нет (см. рис. 5). Натуральные числа также образуют решетку относительно операций взятия наибольшего общего делителя и наименьшего общего кратного, с делимостью в качестве отношения порядка: если делит , то является наименьшим элементом; является наибольшим элементом. Рис. 2 показывает конечную подрешетку. Каждая полная решетка (см. также ниже) является (в определенном смысле специфической) ограниченной решеткой. Этот класс порождает широкий спектр практических примеров. Множество компактных элементов арифметической полной решетки является решеткой с наименьшим элементом, где операции решетки задаются ограничением соответствующих операций арифметической решетки. Это специфическое свойство отличает арифметические решетки от алгебраических решеток, для которых компактные элементы образуют лишь полурешетку соединения. Оба этих класса полных решеток изучаются в теории областей. Дальнейшие примеры решеток приводятся для каждого из дополнительных свойств, обсуждаемых ниже.

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

Соответствующее понятие морфизма между двумя решетками естественно вытекает из вышеприведенного алгебраического определения. Для двух решеток L и M, гомоморфизм решеток из L в M – это функция f, такая что для всех x, y ∈ L выполняется f(x ∧ y) = f(x) ∧ f(y) и f(x ∨ y) = f(x) ∨ f(y).

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

В формулировке, основанной на теории порядка, эти условия просто означают, что гомоморфизм решеток – это функция, сохраняющая бинарные встречи и соединения. Для ограниченных решеток сохранение наименьшего и наибольшего элементов эквивалентно сохранению соединения и встречи пустого множества. Любой гомоморфизм решеток обязательно монотонный относительно соответствующего отношения порядка; см. Функция сохранения пределов. Обратное неверно: монотонность ни в коем случае не подразумевает необходимого сохранения встреч и соединений (см. рис. 9), хотя биекция, сохраняющая порядок, является гомоморфизмом, если ее обратная также сохраняет порядок. При стандартном определении изоморфизмов как обратимых морфизмов, изоморфизм – это просто биективный гомоморфизм решеток. Аналогично, эндоморфизм – это гомоморфизм решетки из решетки в саму себя, а автоморфизм – биективный эндоморфизм решетки. Решетки и их гомоморфизмы образуют категорию. Пусть L и M – две решетки с 0 и 1. Гомоморфизм из L в M называется 0,1-разделимым, если и только если f(x) = 0M тогда и только тогда, когда x = 0L, и f(x) = 1M тогда и только тогда, когда x = 1L.

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

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

Полная информация

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

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

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

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

В теории доменов естественно стремиться аппроксимировать элементы в частично упорядоченном множестве "гораздо более простыми" элементами. Это приводит к классу непрерывных частично упорядоченных множеств, состоящих из множеств, где каждый элемент может быть получен как супремум направленного множества элементов, которые существенно меньше этого элемента. Если дополнительно можно ограничить эти множества компактными элементами частично упорядоченного множества для получения этих направленных множеств, то частично упорядоченное множество является даже алгебраическим. Оба этих понятия применимы к решёткам следующим образом: непрерывная решётка – это полная решётка, которая непрерывна как частично упорядоченное множество. Алгебраическая решётка – это полная решётка, которая алгебраична как частично упорядоченное множество. Оба этих класса обладают интересными свойствами. Например, непрерывные решётки можно характеризовать как алгебраические структуры (с бесконечноточными операциями), удовлетворяющие определённым тождествам. Хотя подобная характеристика неизвестна для алгебраических решёток, их можно описать "синтаксически" с помощью информационных систем Скотта.

Дополнения и псевдодополнения

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

В общем случае, некоторые элементы ограниченной решетки могут не иметь дополнения, а другие – более одного дополнения. Например, множество [0,1] с его обычным порядком является ограниченной решеткой, и элемент 0 не имеет дополнения. В ограниченной решетке N5 элемент 2 имеет два дополнения, а именно 3 и 4 (см. рис. 11). Ограниченная решетка, в которой каждый элемент имеет дополнение, называется комплементированной решеткой. Комплементированная решетка, которая также является распределительной, является булевой алгеброй. Для распределительной решетки дополнение, если оно существует, единственно. В случае, когда дополнение единственно, мы пишем a' и эквивалентно, 'a. Соответствующая унарная операция, называемая комплементацией, вводит в теорию решеток аналог логического отрицания. Алгебры Хейтинга являются примером распределительных решеток, в которых некоторым элементам может не хватать дополнений. Каждый элемент a алгебры Хейтинга имеет, с другой стороны, псевдодополнение, также обозначаемое a∨0. Псевдодополнение является наибольшим элементом b таким, что a∧b = 0. Если псевдодополнение каждого элемента алгебры Хейтинга является на самом деле дополнением, то алгебра Хейтинга является булевой алгеброй.

Свободные решетки

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