Полурешетка

Частичный порядок с соединениями

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

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

Решетка — это частично упорядоченное множество, которое является как meet-, так и join-полурешеткой относительно одного и того же частичного порядка. Алгебраически решетка — это множество с двумя ассоциативными, коммутативными идемпотентными бинарными операциями, связанными соответствующими законами поглощения .

Определение теории порядка

Множество S, частично упорядоченное бинарным отношением ≤ , является полурешеткой встреч, если

Для всех элементов x и y множества S существует точная нижняя граница множества { x , y } .

Точная нижняя граница множества { x , y } называется пересечением x и y и обозначается x ∧ y .

Замена «наибольшей нижней границы» на « наименьшую верхнюю границу » приводит к двойственной концепции join -полурешетки . Наименьшая верхняя граница { x , y } называется объединением x и y , обозначаемым x ∨ y . Meet и join являются бинарными операциями на S . Простой индукционный аргумент показывает, что существование всех возможных попарных супремумов (инфимов), согласно определению, подразумевает существование всех непустых конечных супремумов (инфимов).

Join-полурешетка ограничена , если она имеет наименьший элемент , join пустого множества. Двойственно , meet-полурешетка ограничена , если она имеет наибольший элемент , meet пустого множества.

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

Алгебраическое определение

Полурешетка meet — это алгебраическая структура, состоящая из множества S с бинарной операцией ∧ , называемой meet , такой, что для всех элементов x , y и z множества S выполняются следующие тождества : ${\displaystyle \langle S,\land \rangle }$

Ассоциативность

х ∧ ( у ∧ z ) = ( х ∧ у ) ∧ z

Коммутативность

х ∧ у = у ∧ х

Идемпотентность

х ∧ х = х

Полурешетка встреч ограничена , если S включает единичный элемент 1 такой, что x ∧ 1 = x для всех x из S. ${\displaystyle \langle S,\land \rangle }$

Если символ ∨ , называемый join , заменяет ∧ в только что данном определении, структура называется join-полурешеткой . Можно быть неоднозначным относительно конкретного выбора символа для операции и говорить просто о полурешетках .

Полурешетка — это коммутативная , идемпотентная полугруппа ; т.е. коммутативная связка . Ограниченная полурешетка — это идемпотентный коммутативный моноид .

Частичный порядок индуцируется на meet-полурешетке путем установки x ≤ y всякий раз, когда x ∧ y = x . Для join-полурешетки порядок индуцируется путем установки x ≤ y всякий раз, когда x ∨ y = y . В ограниченной meet-полурешетке единица 1 является наибольшим элементом S . Аналогично, единица в join-полурешетке является наименьшим элементом.

Связь между двумя определениями

Теоретическая по порядку встреча-полурешетка ⟨ S , ≤⟩ порождает бинарную операцию ∧ такую, что ⟨ S , ∧⟩ является алгебраической встречей-полурешеткой. Наоборот, встреча-полурешетка ⟨ S , ∧⟩ порождает бинарное отношение ≤, которое частично упорядочивает S следующим образом: для всех элементов x и y в S , x ≤ y тогда и только тогда, когда x = x ∧ y .

Отношение ≤, введенное таким образом, определяет частичное упорядочение, из которого может быть восстановлена ​​бинарная операция ∧ . Наоборот, порядок, индуцированный алгебраически определенной полурешеткой ⟨ S , ∧⟩, совпадает с порядком, индуцированным ≤.

Следовательно, эти два определения могут использоваться взаимозаменяемо, в зависимости от того, какое из них более удобно для конкретной цели. Аналогичный вывод справедлив для join-полурешеток и дуального порядка ≥.

Примеры

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

• Решетка является как join- , так и meet-полурешеткой. Взаимодействие этих двух полурешеток посредством закона поглощения — это то, что действительно отличает решетку от полурешетки.
• Компактные элементы алгебраической решетки при индуцированном частичном порядке образуют ограниченную полурешетку соединений.
• По индукции по числу элементов любая непустая конечная полурешетка пересечений имеет наименьший элемент, а любая непустая конечная полурешетка пересечений имеет наибольший элемент. (Ни в одном из случаев полурешетка не обязательно будет ограниченной.)
• Полностью упорядоченное множество является дистрибутивной решеткой , а следовательно, и полурешеткой пересечения и полурешеткой объединения: любые два различных элемента имеют больший и меньший элементы, которые являются их пересечением и объединением.
  • Вполне упорядоченное множество далее является ограниченной соединительной полурешеткой, поскольку множество в целом имеет наименьший элемент, следовательно, оно ограничено.
    • Натуральные числа с их обычным порядком ≤ представляют собой ограниченную полурешетку соединений с наименьшим элементом 0, хотя у них нет наибольшего элемента: они представляют собой наименьшее бесконечное вполне упорядоченное множество. ${\displaystyle \mathbb {N} }$
• Любое однокорневое дерево (с единственным корнем в качестве наименьшего элемента) высоты является (обычно неограниченной) meet-полурешеткой. Рассмотрим, например, множество конечных слов в некотором алфавите, упорядоченное по префиксу order . Оно имеет наименьший элемент (пустое слово), который является аннигиляторным элементом операции meet, но не имеет наибольшего (тождественного) элемента. ${\displaystyle \leq \omega }$
• Домен Скотта представляет собой стыковочную полурешетку.
• Членство в любом множестве L можно рассматривать как модель полурешетки с базовым множеством L , поскольку полурешетка отражает суть экстенсиональности множеств . Пусть a ∧ b обозначает a ∈ L & b ∈ L . Два множества, отличающиеся только одним или обоими из:

1. Порядок, в котором перечислены их члены;
2. Множественность одного или нескольких членов,

фактически являются одним и тем же множеством. Коммутативность и ассоциативность ∧ гарантируют (1), идемпотентность , (2). Эта полурешетка является свободной полурешеткой над L . Она не ограничена L , поскольку множество не является членом самого себя.

• Классическая экстенсиональная мереология определяет соединение-полурешетку, где соединение читается как бинарное слияние. Эта полурешетка ограничена сверху мировым индивидом.
• При наличии множества S совокупность разбиений S является полурешеткой соединения. Фактически, частичный порядок задается как , если такое , что и соединение двух разбиений задается как . Эта полурешетка ограничена, причем наименьшим элементом является разбиение из одного элемента . ${\displaystyle \xi }$ ${\displaystyle \xi \leq \eta }$ ${\displaystyle \forall Q\in \eta ,\exists P\in \xi }$ ${\displaystyle Q\subset P}$ ${\displaystyle \xi \vee \eta =\{P\cap Q\mid P\in \xi \ \&\ Q\in \eta \}}$ ${\displaystyle \{S\}}$

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

Приведенное выше алгебраическое определение полурешетки предполагает понятие морфизма между двумя полурешетками. Для двух полурешеток соединения ( S , ∨) и ( T , ∨) гомоморфизм полурешеток (соединения) — это функция f : S → T такая, что

f ( x ∨ y ) = f ( x ) ∨ f ( y ).

Следовательно, f — это просто гомоморфизм двух полугрупп, связанных с каждой полурешеткой. Если S и T оба включают наименьший элемент 0, то f также должен быть моноидным гомоморфизмом, т.е. мы дополнительно требуем, чтобы

ф (0) = 0.

В теоретико-порядковой формулировке эти условия просто утверждают, что гомоморфизм join-полурешеток является функцией, которая сохраняет бинарные соединения и наименьшие элементы, если таковые имеются. Очевидная двойственность — замена ∧ на ∨ и 0 на 1 — преобразует это определение гомоморфизма join-полурешетки в его эквивалент meet-полурешетки.

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

Эквивалентность с алгебраическими решетками

Существует хорошо известная эквивалентность между категорией join-полурешеток с нулем с -гомоморфизмами и категорией алгебраических решеток с сохраняющими компактность -полными join-гомоморфизмами, как следует. С join-полурешеткой с нулем мы связываем ее идеальную решетку . С -гомоморфизмом -полурешеток мы связываем отображение , которое с любым идеалом из связывает идеал из , порожденный . Это определяет функтор . Обратно, с каждой алгебраической решеткой мы связываем -полурешетку всех компактных элементов из , а с каждым сохраняющим компактность полным join-гомоморфизмом между алгебраическими решетками мы связываем ограничение . Это определяет функтор . Пара определяет эквивалентность категорий между и . ${\displaystyle {\mathcal {S}}}$ ${\displaystyle (\vee ,0)}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle S}$ ${\displaystyle \operatorname {Id} \ S}$ ${\displaystyle (\vee ,0)}$ ${\displaystyle f\colon S\to T}$ ${\displaystyle (\vee ,0)}$ ${\displaystyle \operatorname {Id} \ f\colon \operatorname {Id} \ S\to \operatorname {Id} \ T}$ ${\displaystyle I}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle f(I)}$ ${\displaystyle \operatorname {Id} \colon {\mathcal {S}}\to {\mathcal {A}}}$ ${\displaystyle A}$ ${\displaystyle (\vee ,0)}$ ${\displaystyle K(A)}$ ${\displaystyle A}$ ${\displaystyle f\colon A\to B}$ ${\displaystyle K(f)\colon K(A)\to K(B)}$ ${\displaystyle K\colon {\mathcal {A}}\to {\mathcal {S}}}$ ${\displaystyle (\operatorname {Id} ,K)}$ ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {A}}}$

Дистрибутивные полурешетки

Удивительно, но существует понятие «дистрибутивности», применимое к полурешеткам, хотя дистрибутивность традиционно требует взаимодействия двух бинарных операций. Это понятие требует только одной операции и обобщает условие дистрибутивности для решеток. Join-полурешетка является дистрибутивной, если для всех a , b , и x с x ≤ a ∨ b существуют a' ≤ a и b' ≤ b такие, что x = a' ∨ b' . Дистрибутивные meet-полурешетки определяются двойственно. Эти определения оправдываются тем фактом, что любая дистрибутивная join-полурешетка, в которой существуют бинарные meet, является дистрибутивной решеткой. См. статью distributivity (order theory) .

Объединенная полурешетка дистрибутивна тогда и только тогда, когда решетка ее идеалов (по включению) дистрибутивна.

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

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

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

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

Ограниченные по мощности понятия полноты для полурешеток редко рассматривались в литературе. ^[1]

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

Этот раздел предполагает некоторые знания теории категорий . В различных ситуациях существуют свободные полурешетки. Например, забывающий функтор из категории join-полурешеток (и их гомоморфизмов) в категорию множеств (и функций) допускает левый сопряженный . Следовательно, свободная join-полурешетка F ( S ) над множеством S строится путем взятия набора всех непустых конечных подмножеств S , упорядоченных по включению подмножеств. Очевидно, S может быть вложено в F ( S ) с помощью отображения e , которое переводит любой элемент s из S в синглтонное множество { s }. Тогда любая функция f из S в join-полурешетку T (более формально, в базовое множество T ) индуцирует уникальный гомоморфизм f' между join-полурешетками F ( S ) и T , такой что f = f' ○ e . Явно, f' задается как Теперь очевидной единственности f' достаточно, чтобы получить требуемое присоединение — морфизм-часть функтора F может быть выведена из общих соображений (см. сопряженные функторы ). Случай свободных meet-полурешеток является двойственным, используя включение противоположного подмножества в качестве упорядочения. Для join-полурешеток с дном мы просто добавляем пустое множество к вышеуказанному набору подмножеств. ${\textstyle f'(A)=\bigvee \{f(s)|s\in A\}.}$

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

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

• Направленный набор  – Математическое упорядочение с верхними границами – обобщение полурешетки соединений
• Список тем заказа
• Полукольцо  – алгебраическое кольцо, которое не обязательно должно иметь аддитивные отрицательные элементы.

Примечания

1. EG Manes, Алгебраические теории , Graduate Texts in Mathematics Volume 26, Springer 1976, стр. 57

Ссылки

• Davey, BA; Priestley, HA (2002). Введение в решетки и порядок (второе издание). Cambridge University Press . ISBN 0-521-78451-4.
• Викерс, Стивен (1989). Топология через логику . Cambridge University Press . ISBN 0-521-36062-5.

Часто бывает так, что стандартные трактовки теории решеток определяют полурешетку, если это так, и больше ничего не говорят. См. ссылки в статьях order theory и registry theory . Более того, нет литературы по полурешеткам сопоставимой величины с литературой по полугруппам .

Внешние ссылки

• Страница структур алгебры Джипсена: Полурешетки.