Полная решетка - Complete lattice

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

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

Формальное определение

Частично упорядоченное множество ( L , ≤) является полной решеткой , если каждое подмножество из L имеет как точная нижняя грань (The инфимумом , называемый также встречаются ) и не менее верхняя граница ( грань , которая также называется присоединиться к ) в ( L , ≤).

Встречаются обозначается , и присоединиться к по . ${\ displaystyle \ bigwedge A}$${\ displaystyle \ bigvee A}$

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

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

Полные полурешетки

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

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

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

Полные подрешетки

Подрешетка М полной решетки L называется полной подрешетки из L , если для каждого подмножества A из M элементов , и , как это определено в L , на самом деле в М . ${\ displaystyle \ bigwedge A}$${\ displaystyle \ bigvee A}$

Если указанное требование уменьшило требовать только непустой встретиться и присоединяется быть в L , подструктура М называется замкнутая подрешеткой из М .

Примеры

• Любая непустая конечная решетка тривиально полна.
• Набор мощности данного набора, упорядоченный по включению . Супремум задается объединением, а нижняя грань - пересечением подмножеств.
• Единичный интервал [0,1] , и расширенная действительное число линия , со знакомым общим порядком и обычными супремумами и нижними гранями . В самом деле, вполне упорядоченное множество (с его порядковой топологией ) компактно как топологическое пространство, если оно полно как решетка.
• Неотрицательные целые числа , упорядоченные по делимости . Наименьшим элементом этой решетки является число 1, так как оно делит любое другое число. Возможно, что удивительно, но самый большой элемент - это 0, потому что его можно разделить на любое другое число. Верхняя грань конечных множеств задается наименьшим общим кратным, а точная нижняя грань - наибольшим общим делителем . Для бесконечных множеств верхняя грань всегда будет равна 0, в то время как нижняя грань может быть больше 1. Например, набор всех четных чисел имеет 2 в качестве наибольшего общего делителя. Если убрать 0 из этой структуры, она останется решеткой, но перестает быть полной.
• Подгруппы любой данной группы при включении. (Хотя нижняя грань здесь является обычным теоретико-множественным пересечением, верхняя грань множества подгрупп - это подгруппа, порожденная теоретико-множественным объединением подгрупп, а не само теоретико-множественное объединение.) Если e является единицей G , то тривиальная группа { e } является минимальной подгруппой в G , а максимальная подгруппа - это сама группа G.
• Подмодули модуля , упорядоченные по включению. Супремум задается суммой подмодулей, а точная нижняя грань - пересечением.
• Эти идеалы из в кольце , упорядочены по включению. Верхняя грань дается суммой идеалов, а нижняя грань - пересечением.
• Открытые множества топологического пространства , упорядоченные по включению. Супремум задается объединением открытых множеств, а точная нижняя грань - внутренностью пересечения.
• В выпуклых подмножествах из в реальном или комплексном векторном пространстве , упорядоченные по включению. Нижняя грань задается пересечением выпуклых множеств, а супремум - выпуклой оболочкой объединения.
• В топологии на множестве, упорядочены по включению. Нижняя грань задается пересечением топологий, а верхняя грань - топологией, порожденной объединением топологий.
• Решетка всех транзитивных отношений на множестве.
• Решетка всех подмножеств мультимножества .
• Решетка всех отношений эквивалентности на множестве; отношение эквивалентности ~ считается меньшим (или «более тонким»), чем ≈, если x ~ y всегда подразумевает x ≈ y .
• Решетка самосопряженных проекций (также известных как ортогональные проекции) алгебры фон Неймана.

Локально конечные полные решетки

Полная решетка L называется локально конечной, если супремум любого бесконечного подмножества равен 1, или, что то же самое, множество конечно для любого . Решетка ( N , |) локально конечна. Обратите внимание, что в этой решетке элемент, обычно обозначаемый «0», на самом деле равен 1, и наоборот. ${\ Displaystyle \ {у \ в L ~ | ~ у \ Leq х \} \, \!}$${\ displaystyle 1 \ neq x \ in L}$

Морфизмы полных решеток

Традиционные морфизмы между полными решетками - это полные гомоморфизмы (или полные решеточные гомоморфизмы ). Они характеризуются как функции, сохраняющие все соединения и все встречи. Явно это означает, что функция f: L → M между двумя полными решетками L и M является полным гомоморфизмом, если

• ${\ Displaystyle е \ влево (\ bigwedge A \ right) = \ bigwedge \ {f (a) \ mid a \ in A \}}$ а также
• ${\ Displaystyle е \ влево (\ bigvee A \ right) = \ bigvee \ {е (а) \ середина а \ в A \}}$,

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

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

Бесплатное строительство и достройка

Бесплатные "полные полурешетки"

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

Используя стандартное определение из универсальной алгебры , свободная полная решетка над порождающим множеством S - это полная решетка L вместе с функцией i : S → L , такая, что любая функция f из S в базовое множество некоторой полной решетки M может быть однозначно учитываться через морфизм F ° от L до М . Другими словами, для каждого элемента s из S мы находим, что f ( s ) = f ° ( i ( s )) и что f ° - единственный морфизм с этим свойством. Эти условия в основном сводятся к утверждению, что существует функтор из категории множеств и функций в категорию полных решеток и функций, сохраняющих соединение, который остается присоединенным к забывчивому функтору из полных решеток в их базовые множества.

Свободные полные решетки в этом смысле могут быть построены очень легко: полная решетка, порожденная некоторым множеством S, является просто powerset 2 ^S , то есть множеством всех подмножеств S , упорядоченных по включению подмножеств . Требуемый модуль i : S → 2 ^S отображает любой элемент s из S в одноэлементный набор { s }. Для отображения f, как указано выше, функция f °: 2 ^S → M определяется формулой

${\ displaystyle f ^ {\ circ} (X) = \ bigvee \ {f (s) | s \ in X \}}$.

Затем f ° преобразует объединения в супрему и, таким образом, сохраняет соединения.

Наши рассуждения также дают бесплатную конструкцию для морфизмов, которые действительно сохраняют встречи вместо соединений (т. Е. Верхние сопряжения связностей Галуа). Фактически, мы просто должны дуализировать то, что было сказано выше: свободные объекты задаются как наборы мощности, упорядоченные путем обратного включения, так что объединение множеств обеспечивает операцию встречи, а функция f ° определяется в терминах встреч вместо соединений. Результат этой конструкции можно было бы назвать свободной полной встречно-полурешеткой . Следует также отметить, как эти свободные конструкции расширяют те, которые используются для получения свободных полурешеток , где нам нужно рассматривать только конечные множества.

Бесплатные комплектные решетки

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

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

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

Свободной полной решетки на трех образующих не существует; это правильный класс .

Доказательство этого утверждения дает Джонстон; исходный аргумент приписывается Альфреду В. Хейлзу ; также статью о свободных решетках .

Завершение

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

Если рассматривать функции, сохраняющие встречу или соединение, как морфизмы, этого легко добиться с помощью так называемого пополнения Дедекинда – МакНейла . Для этого процесса элементы poset отображаются в (Dedekind-) разрезы , которые затем могут быть отображены в базовые множества произвольных полных решеток почти так же, как это сделано для множеств и свободных полных (полу) решеток выше.

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

Представление

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

Частный пример конструкции Биркгофа начинается с произвольного чугуна (P, ≤) и строит связь Галуа из отношения порядка ≤ между P и самим собой. Полученная полная решетка является пополнением Дедекинда-МакНейля . Когда это завершение применяется к объектному множеству, который уже является полной решеткой, тогда результат изоморфен исходному. Таким образом, мы сразу обнаруживаем, что всякая полная решетка представляется методом Биркгофа с точностью до изоморфизма.

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

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

Дальнейшие результаты

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

Смотрите также

• решетка (заказ) .

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