В математике соединение -полурешетка (или верхняя полурешетка ) — это частично упорядоченное множество , имеющее соединение ( наименьшую верхнюю границу ) для любого непустого конечного подмножества . Двойственным образом встреча -полурешетка (или нижняя полурешетка ) представляет собой частично упорядоченное множество, которое имеет встречу (или максимальную нижнюю границу ) для любого непустого конечного подмножества. Каждая соединительная полурешетка является встречной полурешеткой в обратном порядке и наоборот.
Полурешетки также могут быть определены алгебраически : соединение и встреча являются ассоциативными , коммутативными , идемпотентными двоичными операциями , и любая такая операция индуцирует частичный порядок (и соответствующий обратный порядок), такой, что результатом операции для любых двух элементов является наименьшая верхняя граница. (или наибольшая нижняя граница) элементов относительно этого частичного порядка.
Решетка — это частично упорядоченное множество , которое является одновременно пересекающейся и соединяющейся полурешеткой относительно одного и того же частичного порядка. Алгебраически решетка представляет собой множество с двумя ассоциативными коммутативными идемпотентными бинарными операциями, связанными соответствующими законами поглощения .
Множество S, частично упорядоченное бинарным отношением ≤, является встречной полурешеткой , если
Наибольшая нижняя граница множества { x , y } называется пересечением x и y , обозначается x ∧ y .
Замена «наибольшей нижней границы» на « наименьшую верхнюю границу » приводит к двойственной концепции соединения -полурешетки . Наименьшая верхняя граница { x , y } называется объединением x и y , обозначается x ∨ y . Meet и join — это двоичные операции над S. Простой индукционный аргумент показывает, что существование всех возможных попарных супремумов (инфим) согласно определению влечет за собой существование всех непустых конечных супремумов (инфим).
Полурешетка соединения ограничена, если она имеет наименьший элемент — соединение пустого множества. Двойственно , встреча-полурешетка ограничена, если она имеет наибольший элемент , вершину пустого множества.
Могут быть приняты и другие свойства; дополнительную информацию по этому вопросу см. в статье о полноте в теории порядка . В этой статье также обсуждается, как мы можем перефразировать приведенное выше определение с точки зрения существования подходящих связей Галуа между связанными частично упорядоченными множествами - подход, представляющий особый интерес для теоретико-категорных исследований этой концепции.
Полурешетка встречи — это алгебраическая структура , состоящая из множества S с бинарной операцией ∧ , называемой meet , такой, что для всех членов x , y и z из S выполняются следующие тождества :
Встречающаяся полурешетка ограничена , если S включает единичный элемент 1 такой, что x ∧ 1 = x для всех x в S .
Если символ ∨ , называемый join , заменяет ∧ в только что данном определении, структура называется join-полурешеткой . Можно неоднозначно относиться к конкретному выбору символа для операции и говорить просто о полурешетках .
Полурешетка — коммутативная идемпотентная полугруппа ; т. е. коммутативная зона . Ограниченная полурешетка — это идемпотентный коммутативный моноид .
Частичный порядок индуцируется на встречной полурешетке установкой x ≤ y всякий раз, когда x ∧ y = x . Для соединения-полурешетки порядок индуцируется установкой x ≤ y всякий раз, когда x ∨ y = y . В ограниченной полурешетке тождество 1 является наибольшим элементом S . Аналогично, единичный элемент в полурешетке соединения является наименьшим элементом.
Теоретико-порядковая встреча-полурешетка ⟨ S , ≤⟩ порождает бинарную операцию ∧ такую, что ⟨ S , ∧⟩ является алгебраической встречей-полурешеткой. И наоборот, встреча-полурешетка ⟨ S , ∧⟩ порождает бинарное отношение ≤ , которое частично упорядочивает S следующим образом: для всех элементов x и y в S x ≤ y тогда и только тогда, когда x = x ∧ y .
Введенное таким образом отношение ≤ определяет частичный порядок, из которого может быть восстановлена бинарная операция ∧ . И наоборот, порядок, индуцированный алгебраически определенной полурешеткой ⟨ S , ∧⟩, совпадает с порядком, индуцированным ≤.
Следовательно, эти два определения могут использоваться как взаимозаменяемые, в зависимости от того, какое из них более удобно для конкретной цели. Аналогичный вывод справедлив для соединения-полурешеток и двойственного порядка ≥.
Полурешетки используются для построения других структур порядка или в сочетании с другими свойствами полноты.
Приведенное выше алгебраическое определение полурешетки предполагает понятие морфизма между двумя полурешетками. Для двух объединенных полурешеток ( S , ∨) и ( T , ∨) гомоморфизмом (соединяемых) полурешеток называется функция f : S → T такая, что
Следовательно, f — это просто гомоморфизм двух полугрупп, ассоциированных с каждой полурешеткой. Если S и T оба содержат наименьший элемент 0, то f также должен быть моноидным гомоморфизмом, т. е. мы дополнительно требуем, чтобы
В теоретико-порядковой формулировке эти условия просто утверждают, что гомоморфизм соединений-полурешеток — это функция, которая сохраняет бинарные соединения и наименьшие элементы, если таковые существуют. Очевидный двойственный подход — замена ∧ на ∨ и 0 на 1 — преобразует это определение гомоморфизма соединения полурешеток в его эквивалент в виде пересечения полурешеток.
Заметим, что любой полурешеточный гомоморфизм обязательно монотонен относительно связанного с ним отношения порядка. Объяснение см. в разделе « Сохранение ограничений» .
Известна эквивалентность категории объединенных полурешеток с нулем с -гомоморфизмами и категорией алгебраических решеток с сохраняющими компактность полными гомоморфизмами объединения следующим образом. Сопоставим объединению-полурешетке с нулем ее идеальную решетку . С -гомоморфизмом -полурешеток поставим в соответствие отображение , которое любому идеалу из сопоставляет идеал, порожденный . Это определяет функтор . Обратно, каждой алгебраической решетке мы сопоставляем -полурешетку всех компактных элементов из , а каждому сохраняющему компактность полному гомоморфизму соединения между алгебраическими решетками мы сопоставляем ограничение . Это определяет функтор . Пара определяет эквивалентность категорий между и .
Удивительно, но существует понятие «дистрибутивности», применимое к полурешеткам, хотя традиционно дистрибутивность требует взаимодействия двух бинарных операций. Это понятие требует всего лишь одной операции и обобщает условие дистрибутивности решеток. Объединение-полурешетка является дистрибутивной, если для всех a , b и x , для которых x ≤ a ∨ b, существуют a' ≤ a и b' ≤ b такие, что x = a' ∨ b' . Дистрибутивные встречи-полурешетки определяются двойственно. Эти определения оправданы тем фактом, что любая дистрибутивная полурешетка соединения, в которой существуют двоичные пересечения, является дистрибутивной решеткой. См. дистрибутивность входа (теория порядка) .
Объединение-полурешетка дистрибутивна тогда и только тогда, когда решетка ее идеалов (по включению) дистрибутивна.
В настоящее время термин «полная полурешетка» не имеет общепринятого значения и существуют различные взаимопротиворечивые определения. Если считать, что полнота требует существования всех бесконечных соединений или всех бесконечных встреч, в зависимости от случая, а также конечных, это немедленно приводит к частичным порядкам, которые на самом деле являются полными решетками . Почему существование всех возможных бесконечных соединений влечет за собой существование всех возможных бесконечных встреч (и наоборот), см. Полнота записи (теория порядка) .
Тем не менее, в литературе иногда по-прежнему принимают за полные решетки полные соединения или встречи. В этом случае «полнота» означает ограничение области применения гомоморфизмов . В частности, полное соединение-полурешетка требует, чтобы гомоморфизмы сохраняли все соединения, но в отличие от ситуации, которую мы наблюдаем для свойств полноты, это не требует, чтобы гомоморфизмы сохраняли все соединения. С другой стороны, можно заключить, что каждое такое отображение является нижним сопряженным некоторой связности Галуа . Тогда соответствующий (единственный) верхний сопряженный будет гомоморфизмом полных встреч-полурешеток. Это порождает ряд полезных категориальных двойственностей между категориями всех полных полурешеток с морфизмами, сохраняющими все пересечения или соединения соответственно.
Другое использование термина «полная встреча-полурешетка» относится к ограниченному полному cpo . Полная встреча-полурешетка в этом смысле, возможно, является «наиболее полной» встречей-полурешеткой, которая не обязательно является полной решеткой. Действительно, полная встреча-полурешетка имеет все непустые встречи (что эквивалентно ограниченной полной) и все направленные соединения. Если такая структура имеет еще и наибольший элемент (связку пустого множества), то она также является полной решеткой. Таким образом, полная полурешетка оказывается «полной решеткой, возможно, лишенной вершины». Это определение представляет интерес именно в теории областей , где ограниченные полные алгебраические cpos изучаются как области Скотта . Поэтому области Скотта были названы алгебраическими полурешетками .
Понятия полноты полурешеток, ограниченные по мощности, редко рассматривались в литературе. [1]
Этот раздел предполагает некоторые знания теории категорий . В различных ситуациях существуют свободные полурешетки. Например, функтор забывчивости из категории объединений-полурешеток (и их гомоморфизмов) в категорию множеств (и функций) допускает левый сопряженный . Следовательно , свободная полурешетка соединения F ( S ) над множеством S строится путем взятия совокупности всех непустых конечных подмножеств S , упорядоченных путем включения подмножеств. Очевидно, что S можно вложить в F ( S ) с помощью отображения e , которое переводит любой элемент s из S в одноэлементное множество { s }. Тогда любая функция f из S в объединенную полурешетку T (более формально, в базовое множество T ) индуцирует уникальный гомоморфизм f' между объединенными полурешетками F ( S ) и T , такой что f = f' ○ e . Явно f' задается формулой Теперь очевидной единственности f' достаточно, чтобы получить требуемое присоединение — морфизмная часть функтора F может быть выведена из общих соображений (см. сопряженные функторы ). Случай свободных встречных полурешеток является двойственным, в нем в качестве упорядочения используется включение противоположного подмножества. Для соединения-полурешеток с низом мы просто добавляем пустое множество в приведенную выше коллекцию подмножеств.
Кроме того, полурешетки часто служат генераторами свободных объектов других категорий. Примечательно, что как функторы забывания из категории фреймов и фрейм-гомоморфизмов, так и из категории дистрибутивных решеток и решеточных гомоморфизмов имеют левый сопряженный.
Часто бывает так, что стандартные трактовки теории решеток определяют полурешетку и больше ничего не говорят. См. ссылки в статьях « Теория порядка» и «Теория решеток» . Более того, по полурешеткам нет литературы, сравнимой по величине с литературой по полугруппам .
