Оператор закрытия

В математике оператор замыкания на множестве S — это функция из множества, являющегося степенью S , в себя, которая удовлетворяет следующим условиям для всех множеств: ${\displaystyle \operatorname {cl} :{\mathcal {P}}(S)\rightarrow {\mathcal {P}}(S)}$ ${\displaystyle X,Y\subseteq S}$

Операторы замыкания определяются их замкнутыми множествами , т. е. множествами вида cl( X ), поскольку замыкание cl( X ) множества X является наименьшим замкнутым множеством, содержащим X . Такие семейства «замкнутых множеств» иногда называют системами замыкания или « семействами Мура ». ^[1] Множество вместе с оператором замыкания на нем иногда называют пространством замыкания . Операторы замыкания также называют « операторами оболочки », что предотвращает путаницу с «операторами замыкания», изучаемыми в топологии .

История

Э. Х. Мур изучал операторы замыкания в своем «Введении в форму общего анализа» 1910 года , тогда как концепция замыкания подмножества возникла в работе Фридьеша Рисса в связи с топологическими пространствами. ^[2] Хотя в то время она не была формализована, идея замыкания возникла в конце 19 века благодаря заметному вкладу Эрнста Шредера , Рихарда Дедекинда и Георга Кантора . ^[3]

Примеры

Выпуклая оболочка (красная) многоугольника ( желтая)

Обычное замыкание множества из топологии — это оператор замыкания. Другие примеры включают линейную оболочку подмножества векторного пространства , выпуклую оболочку или аффинную оболочку подмножества векторного пространства или нижнюю полунепрерывную оболочку функции , где — например, нормированное пространство , определенное неявно , где — надграфик функции . ${\displaystyle {\overline {f}}}$ ${\displaystyle f\colon E\to \mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle E}$ ${\displaystyle \operatorname {epi} ({\overline {f}})={\overline {\operatorname {epi} (f)}}}$ ${\displaystyle \operatorname {epi} (f)}$ ${\displaystyle f}$

Относительная внутренняя часть не является оператором замыкания: хотя она идемпотентна, она не возрастает, и если является кубом в и является одной из его граней, то , но и , поэтому она не возрастает. ^[4] ${\displaystyle \operatorname {ri} }$ ${\displaystyle C_{1}}$ ${\displaystyle \mathbb {R} ^{3}}$ ${\displaystyle C_{2}}$ ${\displaystyle C_{2}\subset C_{1}}$ ${\displaystyle \operatorname {ri} (C_{1})\neq \emptyset \neq \operatorname {ri} (C_{2})}$ ${\displaystyle \operatorname {ri} (C_{1})\cap \operatorname {ri} (C_{2})=\emptyset }$

В топологии операторы замыкания являются топологическими операторами замыкания , которые должны удовлетворять

${\displaystyle \operatorname {cl} (X_{1}\cup \dots \cup X_{n})=\operatorname {cl} (X_{1})\cup \dots \cup \operatorname {cl} (X_{n})}$

для всех (Обратите внимание, что для это дает ). ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n=0}$ ${\displaystyle \operatorname {cl} (\varnothing )=\varnothing }$

В алгебре и логике многие операторы замыкания являются финитными операторами замыкания , т.е. они удовлетворяют

${\displaystyle \operatorname {cl} (X)=\bigcup \left\{\operatorname {cl} (Y):Y\subseteq X{\text{ and }}Y{\text{ finite}}\right\}.}$

В теории частично упорядоченных множеств , которые важны в теоретической информатике , операторы замыкания имеют более общее определение, которое заменяется на . (См. § Операторы замыкания на частично упорядоченных множествах.) ${\displaystyle \subseteq }$ ${\displaystyle \leq }$

Операторы замыкания в топологии

Топологическое замыкание подмножества X топологического пространства состоит из всех точек y этого пространства, таких, что каждая окрестность y содержит точку X. Функция , которая сопоставляет каждому подмножеству X его замыкание, является оператором топологического замыкания. Наоборот, каждый оператор топологического замыкания на множестве порождает топологическое пространство, замкнутые множества которого являются в точности замкнутыми множествами относительно оператора замыкания.

Операторы замыкания в алгебре

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

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

Линейная оболочка в векторном пространстве и аналогичное алгебраическое замыкание в поле удовлетворяют свойству обмена: если x находится в замыкании объединения A и { y }, но не в замыкании A , то y находится в замыкании объединения A и { x }. Финитарный оператор замыкания с этим свойством называется матроидом . Размерность векторного пространства или степень трансцендентности поля (над его простым полем ) в точности равна рангу соответствующего матроида.

Функция, которая отображает каждое подмножество заданного поля в его алгебраическое замыкание , также является финитным оператором замыкания, и в общем случае он отличается от оператора, упомянутого ранее. Финитные операторы замыкания, которые обобщают эти два оператора, изучаются в теории моделей как dcl (для определимого замыкания ) и acl (для алгебраического замыкания ).

Выпуклая оболочка в n -мерном евклидовом пространстве является еще одним примером оператора финитарного замыкания. Он удовлетворяет свойству антиобмена: если x находится в замыкании объединения { y } и A , но не в объединении { y } и замыкании A , то y не находится в замыкании объединения { x } и A . Операторы финитарного замыкания с этим свойством порождают антиматроиды .

В качестве другого примера оператора замыкания, используемого в алгебре, если некоторая алгебра имеет универсум A , а X является множеством пар A , то оператор, присваивающий X наименьшую конгруэнцию, содержащую X, является финитным оператором замыкания на A x A. [ ^5]

Операторы замыкания в логике

Предположим, у вас есть некоторый логический формализм , содержащий определенные правила, позволяющие вам выводить новые формулы из заданных. Рассмотрим множество F всех возможных формул, и пусть P будет множеством степеней F , упорядоченным по ⊆. Для множества X формул пусть cl( X ) будет множеством всех формул, которые могут быть выведены из X . Тогда cl является оператором замыкания на P . Точнее, мы можем получить cl следующим образом. Назовем «непрерывным» оператор J такой, что для каждого направленного класса T ,

J (lim T ) = lim J ( T ).

Это условие непрерывности основано на теореме о неподвижной точке для J . Рассмотрим одношаговый оператор J монотонной логики. Это оператор, связывающий любое множество X формул с множеством J ( X ) формул, которые являются либо логическими аксиомами, либо получены с помощью правила вывода из формул в X или находятся в X . Тогда такой оператор непрерывен, и мы можем определить cl( X ) как наименьшую неподвижную точку для J , большего или равного X . В соответствии с такой точкой зрения Тарский, Браун, Сушко и другие авторы предложили общий подход к логике, основанный на теории операторов замыкания. Также такая идея предлагается в логике программирования (см. Lloyd 1987) и в нечеткой логике (см. Gerla 2000).

Операторы следствия

Около 1930 года Альфред Тарский разработал абстрактную теорию логических выводов, которая моделирует некоторые свойства логических исчислений. Математически то, что он описал, является просто финитным оператором замыкания на множестве (множестве предложений ). В абстрактной алгебраической логике финитные операторы замыкания до сих пор изучаются под названием оператор следствия , которое было придумано Тарским. Множество S представляет собой множество предложений, подмножество T теории S , а cl( T ) — множество всех предложений, которые следуют из теории. В настоящее время этот термин может относиться к операторам замыкания, которые не обязательно должны быть финитными; финитные операторы замыкания тогда иногда называются конечными операторами следствия .

Закрытые наборы

Замкнутые множества относительно оператора замыкания на S образуют подмножество C множества P ( S ). Любое пересечение множеств в C снова находится в C . Другими словами, C является полной встречной подполурешеткой P ( S ). Обратно, если C ⊆ P ( S ) замкнуто относительно произвольных пересечений, то функция, которая сопоставляет каждому подмножеству X множества S наименьшее множество Y ∈ C такое, что X ⊆ Y , является оператором замыкания.

Существует простой и быстрый алгоритм для генерации всех замкнутых множеств заданного оператора замыкания. ^[6]

Оператор замыкания на множестве является топологическим тогда и только тогда, когда множество замкнутых множеств замкнуто относительно конечных объединений, т. е. C является полной подрешеткой решетки P ( S ). Даже для нетопологических операторов замыкания C можно рассматривать как имеющий структуру решетки. (Объединение двух множеств X , Y ⊆ P ( S ) есть cl( X Y ).) Но тогда C не является подрешеткой решетки P ( S ). ${\displaystyle \cup }$

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

Псевдозакрытые множества

Каждый оператор замыкания на конечном множестве S однозначно определяется его образами его псевдозамкнутых множеств. ^[7] Они определяются рекурсивно: множество псевдозамкнуто, если оно не замкнуто и содержит замыкание каждого из своих псевдозамкнутых собственных подмножеств. Формально: P  ⊆  S псевдозамкнуто тогда и только тогда, когда

• P  ≠ cl( P ) и
• если Q  ⊂  P псевдозамкнуто, то cl( Q ) ⊆  P .

Операторы замыкания на частично упорядоченных множествах

Частично упорядоченное множество ( посет) — это множество вместе с частичным порядком ≤, т. е. бинарное отношение , которое является рефлексивным ( a ≤ a ), транзитивным ( a ≤ b ≤ c подразумевает a ≤ c ) и антисимметричным ( a ≤ b ≤ a подразумевает a  =  b ). Каждое множество мощности P ( S ) вместе с включением ⊆ является частично упорядоченным множеством.

Функция cl: P → P из частичного порядка P в себя называется оператором замыкания, если она удовлетворяет следующим аксиомам для всех элементов x , y из P.

Доступны более краткие альтернативы: определение выше эквивалентно единственной аксиоме

x ≤ cl( y ) тогда и только тогда, когда cl( x ) ≤ cl( y )

для всех x , y в P.

Используя точечный порядок функций между частично упорядоченными множествами, можно альтернативно записать свойство экстенсивности как id _P ≤ cl, где id — функция тождества . Самоотображение k , которое является возрастающим и идемпотентным, но удовлетворяет двойственному свойству экстенсивности, т. е. k ≤ id _P , называется оператором ядра , ^[8] внутренним оператором , ^[9] или дуальным замыканием . ^[10] Например, если A — подмножество множества B , то самоотображение на супермножестве B , заданное как μ _A ( X ) = A ∪ X , является оператором замыкания, тогда как λ _A ( X ) = A ∩ X — оператором ядра. Функция потолка от действительных чисел к действительным числам, которая присваивает каждому действительному x наименьшее целое число , не меньшее x , является еще одним примером оператора замыкания.

Неподвижная точка функции cl, т. е. элемент c из P , удовлетворяющий cl( c ) =  c , называется замкнутым элементом . Оператор замыкания на частично упорядоченном множестве определяется его замкнутыми элементами. Если c — замкнутый элемент, то x ≤ c и cl( x ) ≤ c — эквивалентные условия.

Каждое соединение Галуа (или остаточное отображение ) порождает оператор замыкания (как объясняется в этой статье). Фактически, каждый оператор замыкания возникает таким образом из подходящего соединения Галуа. ^[11] Соединение Галуа не определяется однозначно оператором замыкания. Одно соединение Галуа, которое порождает оператор замыкания cl, можно описать следующим образом: если A — множество замкнутых элементов относительно cl, то cl: P → A — нижний сопряженный элемент соединения Галуа между P и A , причем верхний сопряженный элемент является вложением A в P. Более того, каждый нижний сопряженный элемент вложения некоторого подмножества в P является оператором замыкания. «Операторы замыкания являются нижними сопряженными элементами вложений». Однако следует отметить, что не каждое вложение имеет нижний сопряженный элемент.

Любое частично упорядоченное множество P можно рассматривать как категорию с единственным морфизмом из x в y тогда и только тогда, когда x ≤ y . Операторы замыкания на частично упорядоченном множестве P тогда являются не чем иным, как монадами в категории P. Эквивалентно, оператор замыкания можно рассматривать как эндофунктор в категории частично упорядоченных множеств, который обладает дополнительными свойствами идемпотента и экстенсивности .

Если P — полная решетка , то подмножество A из P является множеством замкнутых элементов для некоторого оператора замыкания на P тогда и только тогда, когда A — семейство Мура на P , т. е. наибольший элемент P принадлежит A , а инфимум (встреча) любого непустого подмножества A снова принадлежит A. Любое такое множество A само является полной решеткой с порядком, унаследованным от P (но операция супремума (соединения) может отличаться от операции P ) . Когда P — булевская алгебра powerset множества X , то семейство Мура на P называется системой замыкания на X.

Операторы замыкания на P образуют полную решетку; порядок операторов замыкания определяется соотношением cl ₁ ≤ cl ₂ тогда и только тогда, когда cl ₁ ( x ) ≤ cl ₂ ( x ) для всех x из P .

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

• Чех оператор закрытия  – Оператор закрытияPages displaying short descriptions of redirect targets
• Замыкание (топология)  – все точки и предельные точки в подмножестве топологического пространства.
• Связь Галуа  – Частное соответствие между двумя частично упорядоченными множествами
• Внутренняя алгебра  – Алгебраическая структура
• Интерьер (топология)  – наибольшее открытое подмножество некоторого заданного множества.
• Аксиомы замыкания Куратовского  – математическая концепцияPages displaying wikidata descriptions as a fallback
• Оператор предварительного закрытия  – Оператор закрытия

Примечания

1. Диатта, Джин (14.11.2009). «О критических множествах конечного семейства Мура». Advances in Data Analysis and Classification . 3 (3): 291–304. doi :10.1007/s11634-009-0053-8. ISSN  1862-5355. S2CID  26138007.
2. Блит, стр. 11.
3. Марсель Эрне, Замыкание , в Фредерик Минар, Эллиотт Перл (редакторы), За пределами топологии , Современная математика, т. 486, Американское математическое общество, 2009.
4. Рокафеллар, Ральф Тайрелл (1970). Выпуклый анализ. Princeton University Press. стр. 44. doi :10.1515/9781400873173. ISBN 9781400873173.
5. Клиффорд Бергман, Универсальная алгебра , 2012, раздел 2.4.
6. Гантер, Алгоритм 1
7. Гантер, Раздел 3.2
8. Герц, стр. 26
9. Эрне, стр. 2, использует операцию закрытия (соответственно, внутреннюю)
10. Блит, стр. 10
11. Блит, стр. 10

Ссылки

• Гаррет Биркгоф . 1967 (1940). Теория решеток, 3-е изд . Американское математическое общество.
• Беррис, Стэнли Н. и Х. П. Санкаппанавар (1981) Курс универсальной алгебры Springer-Verlag. ISBN 3-540-90578-2 Бесплатное онлайн-издание . 
• Браун Д.Д. и Сушко Р. (1973) «Абстрактная логика», Dissertationes Mathematicae 102-9-42.
• Кастеллини, Г. (2003) Категориальные операторы замыкания . Бостон, Массачусетс: Birkhaeuser.
• Эдельман, Пол Х. (1980) Решетки встречно-дистрибутивных уравнений и замыкание антиобмена, Algebra Universalis 10: 290-299.
• Гантер, Бернхард и Объедков, Сергей (2016) Концептуальное исследование . Спрингер, ISBN 978-3-662-49290-1 . 
• Герла, Г. (2000) Нечеткая логика: математические инструменты для приближенных рассуждений . Kluwer Academic Publishers .
• Ллойд, Дж. У. (1987) Основы логического программирования . Springer-Verlag .
• Тарский, Альфред (1983) «Основные понятия методологии дедуктивных наук» в « Логике, семантике, метаматематике» . Хакетт (изд. 1956 г., Oxford University Press ).
• Альфред Тарский (1956) Логика, семантика и метаматематика . Oxford University Press .
• Уорд, Морган (1942) «Операторы замыкания решетки», Annals of Mathematics 43: 191-96.
• G. Gierz, KH Hofmann, K. Keimel, JD Lawson, M. Mislove, DS Scott: Непрерывные решетки и домены , Cambridge University Press, 2003
• Т. С. Блит, Решетки и упорядоченные алгебраические структуры , Springer, 2005, ISBN 1-85233-905-5 . 
• M. Erné, J. Koslowski, A. Melton, GE Strecker, A primer on Galois links , в: Труды летней конференции 1991 года по общей топологии и приложениям в честь Мэри Эллен Рудин и ее работы, Annals of the New York Academy of Sciences, том 704, 1993, стр. 103–125. Доступно онлайн в различных форматах файлов: PS.GZ PS

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

• Стэнфордская энциклопедия философии : «Алгебраическая пропозициональная логика» — Рамон Джансана.