Полурешетка

показывать Транзитивные   бинарные отношения
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all $a,b$ and $S\neq \varnothing :$ ${\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}$ ${\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}$ ${\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}$ ${\begin{aligned}\min S\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}$ ${\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}$ $aRa$ ${\text{not }}aRa$ ${\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}$
Y indicates that the column's property is always true the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Y in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation $R$ be transitive: for all $a,b,c,$ if $aRb$ and $bRc$ then $aRc.$ A term's definition may require additional properties that are not listed in this table.

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

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

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

Теоретико-порядковое определение

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

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

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

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

Полурешетка соединения ограничена, если она имеет наименьший элемент — соединение пустого множества. Двойственно , встреча-полурешетка ограничена, если она имеет наибольший элемент , вершину пустого множества.

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

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

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

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

Икс ∧ ( y ∧ z ) знак равно ( Икс ∧ y ) ∧ z

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

х ∧ у = у ∧ х

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

х ∧ х = х

На встрече-полурешетке $\langle S,\land \rangle$ ограничен , если 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 , ∧⟩, совпадает с порядком, индуцированным ≤.

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

Примеры

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

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

1. Порядок перечисления их членов;
2. Кратность одного или нескольких членов,

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

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

Полурешеточные

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

ж ( Икс ∨ y ) знак равно ж ( Икс ) ∨ ж ( y ).

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

ж (0) = 0.

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

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

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

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

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

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

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

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

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

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

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

Понятия полноты полурешеток, ограниченные по мощности, редко рассматривались в литературе.

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

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

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

См. также

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

Ссылки

• Дэйви, бакалавр; Пристли, ХА (2002). Введение в решетки и порядок (второе изд.). Издательство Кембриджского университета . ISBN  0-521-78451-4 .
• Викерс, Стивен (1989). Топология через логику . Издательство Кембриджского университета . ISBN  0-521-36062-5 .

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

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

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