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

Частично упорядоченное множество, в котором все подмножества имеют как супремум, так и инфимум

Полная решетка подгрупп для D4, диэдральной группы квадрата. Это пример полной решетки.

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

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

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

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

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

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

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

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

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

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

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

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

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

Более подробное обсуждение обоих определений см . в разделе «Полурешетки» .

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

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

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

Примеры

• Любая непустая конечная решетка тривиально полна.
• Мощность множества заданного множества, упорядоченного по включению . Супремум задается объединением , а инфимум — пересечением подмножеств .
• Неотрицательные целые числа, упорядоченные по делимости . Наименьшим элементом этой решетки является число 1, поскольку оно делит любое другое число. Возможно, это удивительно, но наибольшим элементом является 0, поскольку его можно разделить на любое другое число. Супремум конечных множеств задается наименьшим общим кратным , а инфимум — наибольшим общим делителем . Для бесконечных множеств супремум всегда будет равен 0, в то время как инфимум вполне может быть больше 1. Например, множество всех четных чисел имеет 2 в качестве наибольшего общего делителя. Если 0 удалить из этой структуры, она останется решеткой, но перестанет быть полной.
• Подгруппы любой заданной группы при включении. (В то время как инфимум здесь является обычным теоретико-множественным пересечением, супремум множества подгрупп является подгруппой, порожденной теоретико-множественным объединением подгрупп, а не самим теоретико-множественным объединением.) Если e является единицей G , то тривиальная группа { e } является минимальной подгруппой G , в то время как максимальной подгруппой является сама группа G.
• Идеалы кольца , упорядоченные по включению. Супремум задается суммой идеалов, а инфимум — пересечением .
• Открытые множества топологического пространства , упорядоченные по включению. Супремум задается объединением открытых множеств, а инфимум — внутренней частью пересечения.

Не примеры

• Пустое множество не является полной решеткой. Если бы это была полная решетка, то, в частности, пустое множество имело бы инфимум и супремум в пустом множестве, противоречие.
• Рациональные числа с обычным порядком ≤ не являются полной решеткой. Это решетка с и . Однако само по себе не имеет инфимума или супремума, как и . ${\displaystyle \mathbb {Q} }$ ${\displaystyle \bigwedge \{x,y\}=\min\{x,y\}}$ ${\displaystyle \bigvee \{x,y\}=\max\{x,y\}}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle \{x\in \mathbb {Q} |x^{2}<2\}}$

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

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

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

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

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

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

Связности Галуа и сопряженные

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

${\displaystyle f(x)\leq y\iff x\leq g(y)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Завершение

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Burris, Stanley N. и HP Sankappanavar, HP, 1981. Курс универсальной алгебры. Springer-Verlag. ISBN  3-540-90578-2 (Монография доступна бесплатно онлайн).
2. Бейкер, Кирби (2010). "Полные решетки" (PDF) . Кафедра математики Калифорнийского университета в Лос-Анджелесе . Получено 8 июня 2022 г.
3. PT Johnstone, Stone Spaces , Cambridge University Press, 1982; (см. параграф 4.7)
4. AW Hales , О несуществовании свободных полных булевых алгебр , Fundamenta Mathematicae 54: стр.45-66.
5. Биркгофф, Гарретт (1967). "Полные решетки". Теория решеток . Публикации коллоквиума Американского математического общества. Т. XXV (3-е изд.). Провиденс, Род-Айленд, США: Американское математическое общество. стр. 124. ISBN 978-0821810255.