Полные решетки: определение и свойства

Введение

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

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

Частично упорядоченное множество (L, ≤) является полной решеткой, если для каждого подмножества A множества L существуют как наибольшая нижняя граница (инфимум, также называемый получением), так и наименьшая верхняя граница (супремум, также называемый объединением) в (L, ≤). Получение обозначается ∧, а объединение – ∨. В частном случае, когда A является пустым множеством, получением A будет наибольший элемент L. Аналогично, объединение пустого множества дает наименьший элемент L. Таким образом, полные решетки образуют особый класс ограниченных решеток.

Полные подсетки

Подрешетка M полной решетки L называется полной подрешеткой L, если для любого подмножества A из M элементы inf(A) и sup(A), как определено в L, фактически принадлежат M.

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

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

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

Примеры

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

Any non empty finite lattice is trivially complete. The power set of a given set is ordered by inclusion. The supremum is given by the union and the infimum by the intersection of subsets. The unit interval [0,1] and the extended real number line, with the familiar total order and the ordinary suprema and infima. Indeed, a completely ordered set (with its order topology) is compact as a topological space if it is complete as a lattice. The non negative integers, ordered by divisibility. The least element of this lattice is the number 1, since it divides any other number. Perhaps surprisingly, the greatest element is 0, because it can be divided by any other number. The supremum of finite sets is given by the least common multiple and the infimum by the greatest common divisor. For infinite sets, the supremum will always be 0 while the infimum can well be greater than 1. For example, the set of all even numbers has 2 as the greatest common divisor. If 0 is removed from this structure it remains a lattice but ceases to be complete. The subgroups of any given group under inclusion. (While the infimum here is the usual set theoretic intersection, the supremum of a set of subgroups is the subgroup generated by the set theoretic union of the subgroups, not the set theoretic union itself.) If e is the identity of G, then the trivial group {e} is the minimum subgroup of G, while the maximum subgroup is the group G itself. The submodules of a module, ordered by inclusion. The supremum is given by the sum of submodules and the infimum by the intersection. The ideals of a ring, ordered by inclusion. The supremum is given by the sum of ideals and the infimum by the intersection. The open sets of a topological space, ordered by inclusion. The supremum is given by the union of open sets and the infimum by the interior of the intersection. The convex subsets of a real or complex vector space, ordered by inclusion. The infimum is given by the intersection of convex sets and the supremum by the convex hull of the union. The topologies on a set, ordered by inclusion. The infimum is given by the intersection of topologies, and the supremum by the topology generated by the union of topologies. The lattice of all transitive relations on a set. The lattice of all sub multisets of a multiset. The lattice of all equivalence relations on a set; the equivalence relation ~ is considered to be smaller (or "finer") than ≈ if x~y always implies x≈y. The lattice of self adjoint projections (also known as orthogonal projections) of a von Neumann algebra.

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

Полная решетка L называется локально конечной, если супремум любого бесконечного подмножества равен 1, или, что эквивалентно, множество {x ∈ L | x < a} конечно для любого a ∈ L. Решетка (N, |) является локально конечной. В этой решетке элемент, обычно обозначаемый "0", на самом деле является 1, а элемент, обычно обозначаемый "1", является 0.

Стыки и соединения Галуа

Кроме того, морфизмы, сохраняющие все объединения, эквивалентно характеризуются как нижняя сопряженная часть уникального галуа-сопряжения. Для любой пары предпорядков P и Q, они задаются парами монотонных функций f и g, где f называется нижней сопряженной, а g – верхней сопряженной. Согласно теореме о сопряженных функторах, монотонное отображение между любой парой предпорядков сохраняет все объединения тогда и только тогда, когда оно является нижней сопряженной, и сохраняет все пересечения тогда и только тогда, когда оно является верхней сопряженной. Таким образом, каждый морфизм, сохраняющий объединения, определяет уникальную верхнюю сопряженную в обратном направлении, которая сохраняет все пересечения. Следовательно, рассмотрение полных решеток с полными полурешеточными морфизмами сводится к рассмотрению галуа-сопряжений как морфизмов. Это также дает понимание того, что введенные морфизмы по сути описывают лишь две различные категории полных решеток: одну с полными гомоморфизмами и одну с функциями, сохраняющими пересечения (верхние сопряженные), двойственную к категории с отображениями, сохраняющими объединения (нижние сопряженные). Особенно важным частным случаем является случай решеток подмножеств P(X) и P(Y) и функции из X в Y. В этом случае прямое и обратное отображения между множествами степеней являются верхней и нижней сопряженными друг к другу, соответственно.

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

Как обычно, построение свободных объектов зависит от выбранного класса морфизмов. Давайте сначала рассмотрим функции, сохраняющие все объединения (т. е. нижние сопряженные к связям Галуа), поскольку этот случай проще, чем ситуация для полных гомоморфизмов. Используя вышеупомянутую терминологию, это можно назвать свободной полной полурешеткой объединений. Используя стандартное определение из универсальной алгебры, свободная полная решетка над порождающим множеством S – это полная решетка L вместе с функцией i: S → L, такая что любая функция f из S в базовое множество некоторой полной решетки M может быть однозначно факторизована через морфизм f° из L в M. Другими словами, для каждого элемента s из S мы имеем f(s) = f°(i(s)), и f° – единственный морфизм с этим свойством. Эти условия по сути означают, что существует функтор из категории множеств и функций в категорию полных решеток и функций, сохраняющих объединения, который является левым сопряженным к забывающему функтору из полных решеток в их базовые множества. Свободные полные решетки в этом смысле могут быть построены очень легко: полная решетка, порожденная множеством S, – это просто множество всех подмножеств S, то есть булеан 2S, упорядоченный по включению подмножеств. Требуемая единица i: S → 2S отображает любой элемент s из S в одноэлементное множество {s}. Для заданного отображения f, как указано выше, функция f°: 2S → M определяется как Затем f° преобразует объединения в супремумы и, таким образом, сохраняет объединения. Наши рассуждения также дают свободную конструкцию для морфизмов, сохраняющих пересечения вместо объединений (т. е. верхние сопряженные к связям Галуа). Фактически, нам нужно лишь дуализировать сказанное выше: свободные объекты представляются как булеаны, упорядоченные обратным включением, так что объединение множеств обеспечивает операцию пересечения, а функция f° определяется через пересечения вместо объединений. Результат этой конструкции можно назвать свободной полной полурешеткой пересечений. Также следует отметить, как эти свободные конструкции расширяют те, которые используются для получения свободных полурешеток, где нам нужно рассматривать только конечные множества.

As usual, the construction of free objects depends on the chosen class of morphisms. Let us first consider functions that preserve all joins (i. e. lower adjoints of Galois connections), since this case is simpler than the situation for complete homomorphisms. Using the aforementioned terminology, this could be called a free complete join semilattice. Using the standard definition from universal algebra, a free complete lattice over a generating set S is a complete lattice L together with a function i:S→L, such that any function f from S to the underlying set of some complete lattice M can be factored uniquely through a morphism f° from L to M. Stated differently, for every element s of S we find that f(s) = f°(i(s)) and that f° is the only morphism with this property. These conditions basically amount to saying that there is a functor from the category of sets and functions to the category of complete lattices and join preserving functions which is left adjoint to the forgetful functor from complete lattices to their underlying sets. Free complete lattices in this sense can be constructed very easily: the complete lattice generated by some set S is just the powerset 2S, i. e. the set of all subsets of S, ordered by subset inclusion. The required unit i:S→2S maps any element s of S to the singleton set {s}. Given a mapping f as above, the function f°:2S→M is defined by

Then f° transforms unions into suprema and thus preserves joins. Our considerations also yield a free construction for morphisms that do preserve meets instead of joins (i. e. upper adjoints of Galois connections). In fact, we merely have to dualize what was said above: free objects are given as powersets ordered by reverse inclusion, such that set union provides the meet operation, and the function f° is defined in terms of meets instead of joins. The result of this construction could be called a free complete meet semilattice. One should also note how these free constructions extend those that are used to obtain free semilattices, where we only need to consider finite sets.

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

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

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

Завершение

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

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

Уже в книге Г. Бирхоффа «Теория решёток» содержится очень полезный метод представления. Он сопоставляет полную решётку любой бинарной связи между двумя множествами, строя соединение Галуа из этой связи, что приводит к двум дуально изоморфным системам замыкания. Системы замыкания – это семейства множеств, замкнутые относительно пересечения. При упорядочении отношением подмножества ⊆ они являются полными решётками. Особый случай конструкции Бирхоффа начинается с произвольного частично упорядоченного множества (P, ≤) и строит соединение Галуа из отношения порядка ≤ между P и самим собой. Получающаяся полная решётка является завершением Дедекинда — Макнейла. При применении этого завершения к частично упорядоченному множеству, которое уже является полной решёткой, результат изоморфен исходному. Таким образом, мы сразу видим, что любая полная решётка может быть представлена методом Бирхоффа с точностью до изоморфизма. Эта конструкция используется в формальном концептуальном анализе, где реальные данные представляются бинарными отношениями (называемыми формальными контекстами), а связанные с ними полные решётки (называемые решётками концепций) используются для анализа данных. Следовательно, математическая основа формального концептуального анализа – это теория полных решёток. Другое представление получается следующим образом: Подмножество полной решётки само по себе является полной решёткой (при упорядочении индуцированным порядком) тогда и только тогда, когда оно является образом растущего и идемпотентного (но не обязательно расширяющего) самоотображения. Отображение тождества обладает этими двумя свойствами. Таким образом, все полные решётки могут быть представлены.

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

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