Полная решетка

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

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

Полные решетки не следует путать с полными частичными порядками (cpos), более общим классом частично упорядоченных множеств. Более конкретные полные решетки — это полные булевы алгебры и полные гейтинговы алгебры (локали). ^{[ нужна ссылка ]}

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

Полная решетка — это частично упорядоченное множество ( L , ≤), такое, что каждое подмножество A из L имеет как наибольшую нижнюю границу ( нижнюю границу , также называемую пересечением ) , так и наименьшую верхнюю границу ( верхнюю границу , также называемую соединением ) в ( Л , ≤).

Встреча обозначается $\bigwedge A$ , и соединение по $\bigvee A$ .

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

Завершите подрешетки

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

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

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

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

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

См. полурешетки для дальнейшего обсуждения обоих определений.

Условно полные решетки.

Решетка называется « условно полной », если она удовлетворяет одному или обоим из следующих свойств: ^[2]

Любое подмножество, ограниченное сверху, имеет наименьшую верхнюю границу .
Любое подмножество, ограниченное снизу, имеет максимальную нижнюю границу .

Примеры

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

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

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

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

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

$f\left(\bigwedge A\right)=\bigwedge \{f(a)\mid a\in A\}$ и
$f\left(\bigvee A\right)=\bigvee \{f(a)\mid a\in A\}$ ,

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

Связи Галуа и депутаты

Более того, морфизмы, сохраняющие все соединения, эквивалентно характеризуются как нижняя присоединенная часть уникальной связности Галуа . Для любой пары предпорядков P и Q они задаются парами монотонных функций f и g таких, что

f(x)\leq y\iff x\leq g(y)

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

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

Особенно важным частным случаем являются решетки подмножеств ⁠ $P(X)$ ⁠ и ⁠ $P(Y)$ ⁠ функция от X до Y. и В этом случае карты прямого изображения и обратного изображения между наборами степеней являются верхними и нижними сопряженными друг к другу соответственно.

Бесплатное строительство и завершение

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

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

Стандартное определение универсальной алгебры гласит, что свободная полная решетка над порождающим множеством $S$ представляет собой полную решетку $L$ вместе с функцией $i:S\rightarrow L$ , такая, что любая функция $f$ от $S$ к основному множеству некоторой полной решетки M можно однозначно факторизовать через морфизм $f^{\circ }$ от $L$ к $M$ . Другими словами, для каждого элемента $s$ из $S$ можно найти, что $f(s)=f^{\circ }(i(s))$ и это $f^{\circ }$ — единственный морфизм, обладающий этим свойством. Следовательно, существует функтор из категории множеств и функций в категорию полных решеток и функций, сохраняющих объединение, который слева сопряжен с функтором забывания из полных решеток в лежащие в их основе множества.

Таким образом, можно построить свободные полные решетки так, что полная решетка, порожденная некоторым набором S, является просто набором степеней. $2^{S}$ , множество всех подмножеств S, упорядоченных по включению подмножества . Требуемая единица $i:S\rightarrow 2^{S}$ отображает любой элемент s из S в одноэлементный набор ${s}$ . Учитывая отображение $f$ как и выше, функция $f^{\circ }:2^{S}\rightarrow M$ определяется

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

.

Затем $f^{\circ }$ преобразует союзы в супремы и, таким образом, сохраняет соединения.

Эти соображения также приводят к свободной конструкции морфизмов, которые сохраняют встречи вместо соединений (т.е. верхние сопряжения связностей Галуа). Вышеупомянутое может быть двойственно : свободные объекты задаются как наборы степеней, упорядоченные обратным включением, так что объединение множеств обеспечивает операцию встречи, а функция $f^{\circ }$ определяется с точки зрения встреч, а не объединений. Результат этого построения известен как свободная полная встреча-полурешетка . Можно отметить, что эти свободные конструкции расширяют те, которые используются для получения свободных полурешеток , где необходимо рассматривать конечные множества.

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

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

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

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

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

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

Завершение

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

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

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

Представительство

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

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

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

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

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

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

Ссылки

^ Беррис, Стэнли Н. и HP Санкаппанавар, HP, 1981. Курс универсальной алгебры. Спрингер-Верлаг. ISBN 3-540-90578-2 (монография доступна бесплатно в Интернете).
^ Бейкер, Кирби (2010). «Полные решетки» (PDF) . Математический факультет Калифорнийского университета в Лос-Анджелесе . Проверено 8 июня 2022 г.
^ PT Джонстон, Stone Spaces , издательство Кембриджского университета, 1982; (см. пункт 4.7)
^ AW Hales , О несуществовании свободных полных булевых алгебр , Fundamenta Mathematicae 54: стр. 45-66.
^ Биркгоф, Гаррет (1967). «Полные решетки». Теория решетки . Публикации коллоквиума Американского математического общества. Том. XXV (3-е изд.). Провиденс, Род-Айленд, США: Американское математическое общество. п. 124. ИСБН 978-0821810255 .

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

[2] Бейкер, Кирби (2010). «Полные решетки» (PDF) . Математический факультет Калифорнийского университета в Лос-Анджелесе . Проверено 8 июня 2022 г.

[3] PT Джонстон, Stone Spaces , издательство Кембриджского университета, 1982; (см. пункт 4.7)

[4] AW Hales , О несуществовании свободных полных булевых алгебр , Fundamenta Mathematicae 54: стр. 45-66.

[birkhoff-5] Биркгоф, Гаррет (1967). «Полные решетки». Теория решетки . Публикации коллоквиума Американского математического общества. Том. XXV (3-е изд.). Провиденс, Род-Айленд, США: Американское математическое общество. п. 124. ИСБН 978-0821810255 .

[1]

[2]

[3]

[4]

[5]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice