В математике , А присоединиться к -полурешетка (или верхней полурешеткой ) является частично упорядоченное множество , что имеет присоединиться к (а не менее верхняя граница ) для любого непустого конечного подмножества . Двойственно , встреча-полурешетка (или нижняя полурешетка ) - это частично упорядоченное множество, которое имеет пересечение (или точную нижнюю границу ) для любого непустого конечного подмножества. Каждая джойн-полурешетка является встречной полурешёткой в обратном порядке и наоборот.
Полурешетки также могут быть определены алгебраически : объединение и встреча являются ассоциативными , коммутативными , идемпотентными бинарными операциями , и любая такая операция индуцирует частичный порядок (и соответствующий обратный порядок), так что результат операции для любых двух элементов является наименьшей верхней границей (или точная нижняя граница) элементов относительно этого частичного порядка.
Решетка представляет собой частично упорядоченное множество , что является одновременно meet- и Join-полурешетка по отношению к одной и тому же частичному порядку. Алгебраически решетка - это набор с двумя ассоциативными коммутативными идемпотентными бинарными операциями, связанными соответствующими законами поглощения .
Теоретико-упорядоченное определение
Множество S частично упорядоченное по бинарному отношению ≤ является Meet-полурешетка , если
- Для всех элементов х и у из S , то нижняя грань множества { х , у } существует.
Нижняя грань множества { х , у } называется встречаются по х и у , обозначаемое х ∧ у .
Замена «точной нижней границы» на « точной верхней границы » приводит к двойственному понятию объединенной полурешетки . Верхняя граница { х , у } называется присоединиться к по х и у , обозначаемое х ∨ у . Знакомства и присоединиться являются бинарными операциями на S . Простой аргумент индукции показывает, что существование всех возможных попарных супрем (infima) согласно определению влечет существование всех непустых конечных супремумов (infima).
Джойн-полурешётка ограничена, если у неё есть наименьший элемент - джойн пустого множества. Двойственно полурешетка является ограниченной, если у нее есть наибольший элемент - пересечение пустого множества.
Могут быть приняты другие свойства; см. статью о полноте в теории порядка для более подробного обсуждения этого вопроса. В этой статье также обсуждается, как мы можем перефразировать приведенное выше определение в терминах существования подходящих связей Галуа между связанными посетами - подход, представляющий особый интерес для теоретико-категорийных исследований этого понятия.
Алгебраическое определение
Meet-полурешетка является алгебраической структурой состоящий из множества S с бинарной операцией ∧, называемой meet , такой, что для всех членов x , y и z группы S выполняются следующие тождества :
- Ассоциативность
- х ∧ ( у ∧ г ) = ( х ∧ у ) ∧ г
- Коммутативность
- х ∧ у = у ∧ х
- Идемпотентность
- х ∧ х = х
Встреча-полурешетка является ограниченным , если S содержит единичный элемент 1 таким образом, что х ∧ 1 = х для всех х в S .
Если символ ∨, называемый соединением , заменяет в только что данном определении, структура называется полурешёткой соединения . Можно неоднозначно относиться к конкретному выбору символа для операции и говорить просто о полурешетках .
Полурешетка является коммутативной , идемпотентной полугруппа ; т. е. коммутативная лента . Ограниченная полурешетка - это идемпотентный коммутативный моноид .
Частичный порядок индуцируется на встречной полурешетке, полагая x ≤ y всякий раз, когда x ∧ y = x . Для полурешетки соединения порядок индуцируется положением x ≤ y всякий раз, когда x ∨ y = y . В ограниченной Meet-полурешетке, идентичность 1 является наибольшим элементом S . Точно так же единичный элемент в полурешетке соединения является наименьшим элементом.
Связь между двумя определениями
Заказ Теоретико Meet-полурешетка ⟨ S , ≤⟩ приводит к бинарной операции ∧ таким образом, что ⟨ S , ∧⟩ является алгебраической Meet-полурешеткой. С другой стороны , встречается-полурешетка ⟨ S , ∧⟩ приводит к бинарному отношению ≤ , что частично заказам ˙s следующим образом: для всех элементов х и у в S , х ≤ у тогда и только тогда , когда х = х ∧ у .
Введенное таким образом отношение ≤ определяет частичный порядок, из которого может быть восстановлена двоичная операция. С другой стороны , порядок , индуцированный алгебраически определенной полурешетке ⟨ S , ∧⟩ совпадает с таковым , индуцированным ≤.
Следовательно, эти два определения могут использоваться взаимозаменяемо, в зависимости от того, какое из них более удобно для конкретной цели. Аналогичный вывод верен для джойн-полурешеток и двойственного порядка ≥.
Примеры
Полурешетки используются для построения других порядковых структур или в сочетании с другими свойствами полноты.
- Решетка является одновременно сшиваемой и встречающей-полурешеткой. Взаимодействие этих двух полурешеток через закон поглощения - вот что действительно отличает решетку от полурешетки.
- Эти компактные элементы алгебраической решетки , при индуцированном частичном упорядочении, образуют ограниченное нарисуй полурешетки.
- Любая конечная полурешетка ограничена по индукции.
- Упорядоченное множество является дистрибутивной решеткой , следовательно , в частности , в Meet-полурешетке и нарисуйте полурешетку: любые два различных элемента имеет большой и меньшие один, которые являются их встречаются и присоединиться.
- Хорошо упорядоченное множество является далее , а ограниченная присоединиться к -полурешетка, как множество в целом имеет наименьший элемент, следовательно , оно ограничено.
- Неотрицательные целые числа ℕ с их обычным порядком ≤ представляют собой ограниченную полурешетку соединения с наименьшим элементом 0, хотя у них нет наибольшего элемента: они представляют собой наименьшее бесконечное упорядоченное множество.
- Хорошо упорядоченное множество является далее , а ограниченная присоединиться к -полурешетка, как множество в целом имеет наименьший элемент, следовательно , оно ограничено.
- Любое однокорневое дерево (с единственным корнем в качестве наименьшего элемента) высотыявляется встречно-полурешёткой (вообще говоря, неограниченной). Рассмотрим, например, набор конечных слов в некотором алфавите, упорядоченных по порядку префиксов . Он имеет наименьший элемент (пустое слово), который является аннулирующим элементом операции встречи, но не имеет наибольшего (единичного) элемента.
- Скотт домен является Meet-полурешетка.
- Членство в любом множестве L может быть принято в качестве модели полурешетки с базовым множеством L , потому что полурешетка захваты сути множества объемности . Пусть а ∧ б обозначают ∈ L & б ∈ L . Два набора, отличающиеся только одним или обоими:
- Порядок, в котором перечислены их участники;
- Множественность одного или нескольких членов,
- фактически один и тот же набор. Коммутативность и ассоциативность гарантируют (1), идемпотентность , (2). Это полурешетка является свободной полурешеткой над L . Он не ограничен L , потому что набор не является членом самого себя.
- Классическая экстенсиональная мереология определяет соединение-полурешетку, при этом соединение читается как двоичное слияние. Эта полурешетка ограничена сверху мировым индивидом.
- Для набора S набор разделовгруппы S является полурешеткой джойна. Фактически, частичный порядок определяется выражением если такой, что и соединение двух разделов задается . Эта полурешетка ограничена, причем наименьшим элементом является одноэлементное разбиение.
Полурешеточные морфизмы
Приведенное выше алгебраическое определение полурешетки предполагает понятие морфизма между двумя полурешетками. Принимая во внимание два присоединиться к -полурешеток ( S , ∨) и ( Т , ∨) , А гомоморфизм из (сшиваемых) полурешёток является функцией F : S → T такое , что
- е ( х ∨ у ) = е ( х ) ∨ е ( у ).
Следовательно, f является просто гомоморфизмом двух полугрупп, связанных с каждой полурешеткой. Если S и T оба содержат наименьший элемент 0, то f также должен быть гомоморфизмом моноида , т. Е. Мы дополнительно требуем, чтобы
- f (0) = 0.
В теоретико-порядковой формулировке эти условия просто утверждают, что гомоморфизм полурешеток соединений - это функция, которая сохраняет бинарные соединения и наименьшие элементы, если таковые существуют. Очевидное двойственное - замена на и 0 на 1 - превращает это определение гомоморфизма полурешеток в его эквивалент в полурешетках.
Заметим, что любой полурешеточный гомоморфизм обязательно монотонен относительно соответствующего отношения порядка. Объяснение см. В разделе « Сохранение пределов входа» .
Эквивалентность алгебраическим решеткам
Существует хорошо известная эквивалентность между категорией джойн-полурешёток с нулем с -гомоморфизмы и категория из алгебраических решеток с компактностью -preserving полных Join-гомоморфизмами, следующим образом . С стыковочной полурешёткой нулю свяжем его идеальную решетку . С-гомоморфизм из -полурешеткам сопоставим отображение , что с любым идеалом из связывает идеал создан . Это определяет функтор. Наоборот, с любой алгебраической решеткой мы связываем -полурешетка все компактные элементы из, и с любым сохраняющим компактность полным гомоморфизмом соединения между алгебраическими решетками ставим в соответствие ограничение . Это определяет функтор. Пара определяет эквивалентность категорий между а также .
Распределительные полурешетки
Удивительно, но понятие «дистрибутивность» применимо к полурешеткам, хотя обычно дистрибутивность требует взаимодействия двух бинарных операций. Это понятие требует всего одной операции и обобщает условие дистрибутивности для решеток. Джойн-полурешетка дистрибутивна, если для всех a , b и x с x ≤ a ∨ b существуют такие a ' ≤ a и b' ≤ b , что x = a ' ∨ b' . Дистрибутивные встречные полурешетки определяются двойственно. Эти определения оправданы тем фактом, что любая дистрибутивная полурешетка соединений, в которой существуют бинарные пересечения, является дистрибутивной решеткой. См. Раздел о распределении входов (теория порядка) .
Джойн-полурешетка дистрибутивна тогда и только тогда, когда решетка ее идеалов (по включению) дистрибутивна.
Полные полурешетки
В настоящее время термин «полная полурешетка» не имеет общепринятого значения, и существуют различные взаимно несовместимые определения. Если для полноты требуется наличие всех бесконечных соединений или всех бесконечных пересечений, в зависимости от случая, а также конечных, это немедленно приводит к частичным порядкам, которые фактически являются полными решетками . О том, почему существование всех возможных бесконечных объединений влечет за собой существование всех возможных бесконечных встреч (и наоборот), см. Полноту входа (теория порядка) .
Тем не менее в литературе иногда все еще рассматриваются полные полурешетки соединения или пересечения как полные решетки. В этом случае «полнота» означает ограничение на объем гомоморфизмов . В частности, полная полурешетка соединений требует, чтобы гомоморфизмы сохраняли все соединения, но в отличие от ситуации, которую мы находим для свойств полноты, это не требует, чтобы гомоморфизмы сохраняли все соединения. С другой стороны, мы можем заключить, что каждое такое отображение является нижним сопряженным элементом некоторой связности Галуа . Соответствующий (единственный) верхний сопряженный элемент будет тогда гомоморфизмом полных встреч-полурешеток. Это порождает ряд полезных категориальных двойственностей между категориями всех полных полурешеток с морфизмами, сохраняющими все встречи или соединения, соответственно.
Другое использование термина «полная встреча-полурешетка» относится к ограниченной полной cpo . Полная встречающаяся полурешетка в этом смысле, возможно, является «наиболее полной» встречной полурешеткой, которая не обязательно является полной решеткой. Действительно, полная встреча-полурешетка имеет все непустые пересечения (что эквивалентно ограниченно полной полноте) и все направленные соединения. Если такая структура также имеет наибольший элемент (пересечение пустого множества), она также является полной решеткой. Таким образом, полная полурешетка оказывается «полной решеткой, возможно, без волчка». Это определение представляет особый интерес для теории областей , где ограниченные полные алгебраические cpos изучаются как области Скотта . Поэтому области Скотта были названы алгебраическими полурешетками .
Понятия полноты для полурешеток с ограничением по мощности редко рассматривались в литературе. [1] [2]
Свободные полурешетки
Этот раздел предполагает некоторые знания теории категорий . В различных ситуациях существуют свободные полурешетки. Например, забывчивый функтор из категории джойн-полурешеток (и их гомоморфизмов) в категорию множеств (и функций) допускает левое сопряжение . Таким образом, свободный присоединиться к -полурешетка F ( S ) над множеством S строится путем принятия совокупность всех непустых конечных подмножеств из S , упорядоченных по включению подмножества. Ясно, что S можно вложить в F ( S ) с помощью отображения e, которое переводит любой элемент s из S в одноэлементное множество { s }. Тогда любая функция f из a S в полурешётку соединения T (более формально, на базовое множество T ) индуцирует единственный гомоморфизм f ' между полурешётками соединения F ( S ) и T , такой что f = f' o e . Явно f ' определяется как f' ( A ) ={ f ( s ) | s в A }. Теперь очевидной единственности f ' достаточно для получения требуемого присоединения - морфизм-часть функтора F может быть получен из общих соображений (см. Присоединенные функторы ). Случай свободных встреч-полурешеток двойственен, поскольку в качестве упорядочения используется включение противоположного подмножества. Для соединений-полурешеток с основанием мы просто добавляем пустое множество к вышеуказанному набору подмножеств.
Кроме того, полурешетки часто служат генераторами свободных объектов других категорий. Примечательно, что и забывчивые функторы из категории фреймов и фрейм-гомоморфизмов, а также из категории дистрибутивных решеток и решеточных гомоморфизмов имеют левое сопряжение.
Смотрите также
- Направленное множество , обобщение полурешетки соединения
- Список тем заказа
- Полукруглый
Заметки
- ^ EG Manes, Алгебраические теории , Тексты для выпускников по математике Том 26, Springer 1976, стр. 57
- ^ полные полурешетки на Planetmath.org
Рекомендации
- Дэйви, BA; Пристли, HA (2002). Введение в решетки и порядок (второе изд.). Издательство Кембриджского университета . ISBN 0-521-78451-4.
- Викерс, Стивен (1989). Топология через логику . Издательство Кембриджского университета . ISBN 0-521-36062-5. CS1 maint: обескураженный параметр ( ссылка )
Часто бывает, что стандартные трактовки теории решеток определяют полурешетку, если это так, а потом больше ничего не говорят. См. Ссылки в теории порядка элементов и теории решеток . Более того, нет литературы о полурешетках, сопоставимых по величине с литературой о полугруппах .
Внешние ссылки
- Страница структур алгебры Джипсена : Полурешетки.