Войти
В математике полная решетка - это частично упорядоченный набор, в котором все подмножества имеют как верхнюю грань (соединение), так и нижнюю границу (соответствовать). Полные решетки используются во многих приложениях в математике и информатике. Являясь частным случаем решеток, они изучаются как в теории порядка, так и в универсальной алгебре.
Полные решетки не следует путать с полными частичными порядками (cpos), которые составляют строго более общий класс частично упорядоченных множеств. Более конкретные полные решетки - это полные булевы алгебры и полные алгебры Гейтинга (locales).
A частично упорядоченный набор (L, ≤) является полной решеткой, если каждое подмножество A из L имеет как наибольшую нижнюю границу (инфимум, также называемое соединением) и наименьшей верхней границей (супремум, также называемое соединением) в (L, ≤).
Встреча обозначается 
Примечание. что в особом случае, когда A - это пустое множество, пересечение A будет наибольшим элементом L. Аналогично, объединение пустого набора дает наименьшее элемент. Так как определение также гарантирует существование двоичных встреч и объединений, полные решетки, таким образом, образуют специальный класс ограниченных решеток.
Дополнительные последствия приведенного выше определения обсуждаются в статье о свойствах полноты в теория порядка.
В теории порядка произвольные встречи могут быть выражены в терминах произвольных соединений и наоборот (подробности см. В разделе полнота (теория порядка) ). Фактически это означает, что для получения класса всех полных решеток достаточно потребовать существования либо всех встреч, либо всех объединений.
Как следствие, некоторые авторы используют термины полная встреча-полурешетка или полная полурешетка соединения как еще один способ обозначения полных решеток. Хотя эти термины похожи на объекты, они влекут за собой разные понятия гомоморфизма, как будет объяснено ниже в разделе о морфизмах.
С другой стороны, некоторые авторы не используют это различие морфизмов (особенно с учетом того, что возникающие концепции «полных морфизмов полурешеток» также могут быть определены в общих терминах). Следовательно, полные встречные полурешетки также были определены как те встречающиеся полурешетки, которые также являются полными частичными порядками. Эта концепция, возможно, является «наиболее полным» понятием встречной полурешетки, которая еще не является решеткой (фактически, может отсутствовать только верхний элемент). Это обсуждение также можно найти в статье о полурешетках.
Подрешетка M полной решетки L называется полной подрешеткой L, если для каждого подмножества A из M элементы
Если вышеупомянутое требование уменьшается и требует, чтобы в L находились только непустые соединения и соединения, подрешетка M называется замкнутой подрешеткой M.
Полная решетка L называется локально конечной, если верхняя грань любого бесконечного подмножества равна 1, или, что то же самое, множество 
Традиционные морфизмы между полными решетками - это полные гомоморфизмы (или полные гомоморфизмы решетки). Они характеризуются как функции, которые сохраняют все соединения и все встречи. Явно это означает, что функция f: L → M между двумя полными решетками L и M является полным гомоморфизмом, если
и
,для всех подмножеств A из L. Такие функции автоматически монотонный, но условие полного гомоморфизма на самом деле гораздо более конкретное. По этой причине может быть полезно рассмотреть более слабые понятия морфизмов, которые требуются только для сохранения всех объединений (давая категорию Sup ) или всех соответствий (давая категорию Inf ), которые действительно являются неэквивалентными условиями. Это понятие можно рассматривать как гомоморфизм полных встреч-полурешеток или полных джойн-полурешеток соответственно.
Кроме того, морфизмы, сохраняющие все соединения, эквивалентно характеризуются как нижняя сопряженная часть уникальной связи Галуа. Каждый из них определяет уникальный верхний сопряженный в обратном направлении, который сохраняет все встречи. Следовательно, рассмотрение полных решеток с полными морфизмами полурешеток сводится к рассмотрению связностей Галуа как морфизмов. Это также приводит к пониманию того, что введенные морфизмы в основном описывают только две разные категории полных решеток: одну с полными гомоморфизмами, а другую с функциями, сохраняющими встречи (верхнее сопряжение), дуальными к той, которая сохраняет соединение. отображения (нижние сопряжения).
Как обычно, построение свободных объектов зависит от выбранного класса морфизмов. Рассмотрим сначала функции, сохраняющие все джойны (т.е. нижние сопряжения связностей Галуа), так как этот случай проще, чем ситуация для полных гомоморфизмов. Используя вышеупомянутую терминологию, это можно было бы назвать свободной полной полурешеткой соединения.
Используя стандартное определение из универсальной алгебры, свободная полная решетка над порождающим множеством S - это полная решетка L вместе с функцией i: S → L, такая, что любая функция f из S в основной набор некоторой полной решетки M может быть однозначно факторизован с помощью морфизма f ° из L в M. Другими словами, для каждого элемента s из S мы находим, что f (s) = f ° (i (s)) и что f ° - единственный морфизм с этим свойством. Эти условия в основном сводятся к тому, чтобы сказать, что существует функтор из категории множеств и функций в категорию полных решеток и функций, сохраняющих соединение, который присоединен слева к забывчивому функтору из полные решетки в их базовые множества.
Свободные полные решетки в этом смысле могут быть построены очень легко: полная решетка, порожденная некоторым множеством S, является просто powerset 2, то есть множеством всех подмножеств S, упорядоченных включение подмножества. Требуемый модуль i: S → 2 отображает любой элемент s из S в одноэлементный набор {s}. Для отображения f, как указано выше, функция f °: 2 → M определяется следующим образом:
.Тогда f ° преобразует объединения в супремумы и, таким образом, сохраняет соединения.
Наши рассуждения также дают бесплатную конструкцию для морфизмов, которые действительно сохраняют пересечения вместо соединений (т.е. верхние сопряжения связностей Галуа). Фактически, нам просто нужно дуализовать то, что было сказано выше: свободные объекты задаются как наборы мощности, упорядоченные обратным включением, так что объединение множеств обеспечивает операцию встречи, а функция f ° определяется в терминах встреч вместо присоединения. Результат этой конструкции можно было бы назвать свободной полной встречно-полурешеткой. Следует также отметить, как эти свободные конструкции расширяют те, которые используются для получения свободных полурешеток, где нам нужно рассматривать только конечные множества.
Очевидно, что ситуация для полных решеток с полными гомоморфизмами сложнее. На самом деле свободных полных решеток вообще не существует. Конечно, можно сформулировать проблему со словами, аналогичную той, что была для случая решеток, но совокупность всех возможных слов (или «терминов») в этом случае была бы правильный класс, поскольку произвольные встречи и соединения содержат операции для наборов аргументов любой мощности.
Это свойство само по себе не является проблемой: как показывает приведенный выше случай свободных полных полурешеток, оно может хорошо быть, что решение проблемы слова оставляет только набор классов эквивалентности. Другими словами, вполне возможно, что соответствующие классы класса всех терминов имеют одинаковое значение и, таким образом, идентифицируются в свободной конструкции. Однако классы эквивалентности для проблемы слов полных решеток «слишком малы», так что свободная полная решетка все равно будет надлежащим классом, что недопустимо.
Теперь можно еще надеяться, что есть несколько полезных случаев, когда набор образующих достаточно мал для существования свободной полной решетки. К сожалению, ограничение на размер очень низкое, и у нас есть следующая теорема:
Доказательство этого утверждения дает Джонстон; исходный аргумент приписывается Альфреду В. Хейлзу ; см. также статью о свободных решетках.
Если полная решетка свободно генерируется из заданного poset, используемого вместо набора генераторов, рассмотренного выше, то говорят о завершении посеть. Определение результата этой операции аналогично приведенному выше определению свободных объектов, где «множества» и «функции» заменены «посетами» и «монотонными отображениями». Точно так же можно описать процесс пополнения как функтор из категории множеств с монотонными функциями в некоторую категорию полных решеток с соответствующими морфизмами, которая остается сопряженной с забывчивым функтором в обратном направлении.
Если рассматривать функции, сохраняющие встречу или соединение, как морфизмы, этого можно легко достичь с помощью так называемого завершения Дедекинда – МакНейла. Для этого процесса элементы poset отображаются в (Dedekind-) разрезы, которые затем могут быть отображены в базовые множества произвольных полных решеток почти так же, как это сделано для множеств и свободных полных (полу) решеток выше.
Вышеупомянутый результат о том, что свободных полных решеток не существует, влечет за собой, что соответствующее свободное построение из чугуна также невозможно. В этом легко убедиться, рассматривая позы с дискретным порядком, где каждый элемент относится только к себе. Это в точности свободные позы в нижележащем наборе. Если бы было свободное построение полных решеток из посетов, то можно было бы составить обе конструкции, что противоречит отрицательному результату выше.
Книга по теории решеток Г. Биркгофа уже содержит очень полезный метод представления. Он связывает полную решетку с любым бинарным отношением между двумя наборами, создавая связь Галуа из отношения, которая затем приводит к двум двойственно изоморфным замкнутым системам. Замкнутые системы - это семейства множеств, замкнутые по пересечению. Когда они упорядочены отношением подмножества ⊆, они являются полными решетками.
Особый пример конструкции Биркгофа начинается с произвольного чугуна (P, ≤) и строит связь Галуа из отношения порядка ≤ между P и самим собой. Полученная полная решетка является пополнением Дедекинда-МакНейля. Когда это завершение применяется к объектному набору, который уже является полной решеткой, тогда результат изоморфен исходному. Таким образом, мы сразу же находим, что всякая полная решетка представляется методом Биркгофа с точностью до изоморфизма.
Конструкция используется в анализе формальных понятий, где данные в реальном слове представляются двоичными отношениями (называемыми формальными контекстами) и используются связанные полные решетки (называемые решетками понятий) для анализа данных.. Следовательно, математика, лежащая в основе анализа формальных понятий, - это теория полных решеток.
Другое представление получается следующим образом: подмножество полной решетки само является полной решеткой (когда упорядочено с индуцированным порядком) тогда и только тогда, когда оно является образом возрастающей и идемпотентной Самостоятельная карта (но не обязательно обширная). Очевидно, что тождественное отображение обладает этими двумя свойствами. Таким образом, возникают все полные решетки.
Помимо результатов предыдущего представления, есть некоторые другие утверждения, которые могут быть сделаны о полных решетках или которые в этом случае принимают особенно простую форму. Примером может служить теорема Кнастера – Тарского, которая утверждает, что множество неподвижных точек монотонной функции на полной решетке снова является полной решеткой. Легко видеть, что это обобщение вышеупомянутого наблюдения об образах возрастающих и идемпотентных функций, поскольку это примеры теоремы.
