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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

${ Displaystyle е влево ( bigwedge A right) = bigwedge {f (a) mid a in A }}$ и
${ Displaystyle е влево ( bigvee A right) = bigvee {f (a) mid a in A }}$ ,

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

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

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

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

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

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

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

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

.

потом ж° превращает союзы в супрему и таким образом сохраняет соединения.

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

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

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

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

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

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

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

Завершение

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

^ Беррис, Стэнли Н. и Х.П. Санкаппанавар, Х. П., 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2 (Монография доступна бесплатно в Интернете).
^ П. Т. Джонстон, Каменные Пространства, Cambridge University Press, 1982; (см. параграф 4.7)
^ А. В. Хейлз, Об отсутствии свободных полных булевых алгебр, Fundamenta Mathematicae 54: pp.45-66.
^ Гаррет Биркгоф, Теория решеток, AMS Colloquium Publications Vol. 25, ISBN 978-0821810255

[1] Беррис, Стэнли Н. и Х.П. Санкаппанавар, Х. П., 1981. Курс универсальной алгебры. Springer-Verlag. ISBN 3-540-90578-2 (Монография доступна бесплатно в Интернете).

[2] П. Т. Джонстон, Каменные Пространства, Cambridge University Press, 1982; (см. параграф 4.7)

[3] А. В. Хейлз, Об отсутствии свободных полных булевых алгебр, Fundamenta Mathematicae 54: pp.45-66.

[Birkhoff-4] Гаррет Биркгоф, Теория решеток, AMS Colloquium Publications Vol. 25, ISBN 978-0821810255

[1]

[2]

[3]

[4]