В математике , оператор замыкания на множестве S является функцией из набора степеней S в себя, который удовлетворяет следующим условиям для всех множеств
(cl является обширным ), (cl монотонный ), (cl идемпотентно ).
Операторы Затворы определяются их замкнутых множеств , т.е. множествами вида Cl ( X ), так как замыкание сл ( Х ) множества X представляет собой наименьшее замкнутое множество , содержащее X . Такие семейства «замкнутых множеств» иногда называют системами замыкания или « семействами Мура » в честь Э. Х. Мура, который изучал операторы замыкания в своем « Введении» 1910 г. в форму общего анализа , тогда как концепция замыкания подмножества возникла в работа Фриджеса Рисса в связи с топологическими пространствами. [1] Хотя в то время это не было официально оформлено, идея закрытия возникла в конце 19 века при заметном вкладе Эрнста Шредера , Ричарда Дедекинда и Георга Кантора . [2]
Операторы замыкания также называются « операторами оболочки », что позволяет избежать путаницы с «операторами замыкания», изучаемыми в топологии . Множество вместе с оператором замыкания на нем иногда называют закрывающим пространством .
Приложения
Операторы замыкания имеют множество применений:
В топологии операторы замыкания являются топологическими операторами замыкания , которые должны удовлетворять
для всех (Обратите внимание, что для это дает ).
В алгебре и логике многие операторы замыкания являются операторами конечного замыкания , т. Е. Удовлетворяют
В теории частично упорядоченных множеств , которые важны в теоретической информатике , операторы замыкания имеют более общее определение, которое заменяет с участием . (См. § Операторы замыкания на частично упорядоченных множествах .)
Операторы замыкания в топологии
Топологическое замыкание подмножества X в виде топологического пространства состоит из всех точек у пространства, таким образом, что каждая окрестность в г содержит точку X . Функция, которая связывает с каждым подмножеством X его замыкание, является оператором топологического замыкания. И наоборот, каждый топологический оператор замыкания на множестве порождает топологическое пространство, замкнутые множества которого являются в точности замкнутыми множествами относительно оператора замыкания.
Операторы замыкания в алгебре
Операторы конечного замыкания играют относительно важную роль в универсальной алгебре , и в этом контексте они традиционно называются операторами алгебраического замыкания . Каждое подмножество алгебры порождает в подалгебру : наименьшая подалгебра , содержащая множество. Это дает начало оператору финального закрытия.
Возможно, наиболее известным примером этого является функция, которая связывает с каждым подмножеством данного векторного пространства его линейную оболочку . Аналогично, функция , которая сопоставляет каждую подгруппу данной группы подгруппы , порожденная ней, а так же для полей и всех других типов алгебраических структур .
Линейная оболочка в векторном пространстве и аналогичное алгебраическое замыкание в поле удовлетворяют свойству обмена: если x находится в замыкании объединения A и { y }, но не в замыкании A , то y находится в замыкании объединения A и { x }. Оператор финитарного замыкания с этим свойством называется матроидом . Размерность векторного пространства, или степени трансцендентности поля (над его простым полем ) именно ранг соответствующей матроиды.
Функция, отображающая каждое подмножество данного поля в его алгебраическое замыкание , также является оператором конечного замыкания и в целом отличается от оператора, упомянутого ранее. Операторы финитарного замыкания, которые обобщают эти два оператора, изучаются в теории моделей как dcl (для определимого замыкания ) и acl (для алгебраического замыкания ).
Выпуклая оболочка в п - мерное евклидово пространства является еще одним примером финитарного оператора замыкания. Он удовлетворяет свойству анти-обмена: если x находится в замыкании объединения { y } и A , но не в объединении { y } и замыкании A , то y не входит в замыкание объединения { х } и . Операторы финитарного замыкания с этим свойством порождают антиматроидов .
В качестве другого примера оператора замыкания , используемого в алгебре, если некоторая алгебра имеет вселенную А и Х представляет собой набор пара А , то оператор присваивания X наималейшую конгруэнтность , содержащую X является финитным оператором замыкания A X A . [3]
Операторы замыкания в логике
Предположим, у вас есть некоторый логический формализм , содержащий определенные правила, позволяющие выводить новые формулы из заданных. Рассмотрим множество F всех возможных формул, и пусть P будет булеан из F , по заказу ⊆. Для множества X формул, пусть сл ( Х ) будет множество всех формул , которые могут быть получены из X . Тогда сл является оператором замыкания на P . Точнее, cl можно получить следующим образом. Вызов «непрерывный» оператор J такой , что для каждого направленного класса Т ,
- 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, является оператором замыкания.
Существует простой и быстрый алгоритм генерации всех замкнутых множеств данного оператора замыкания. [4]
Оператор замыкания на множестве топологичен тогда и только тогда, когда множество замкнутых множеств замкнуто относительно конечных объединений, т. Е. C является полностью полной подрешеткой в P ( S ). Даже для нетопологических операторов замыкания C можно рассматривать как имеющую структуру решетки. (Соединение двух множеств X , Y ⊆ P ( S ) является cl ( X Y ).) Но тогда C не является подрешеткой решетки P ( S ).
Для данного оператора конечного замыкания на множестве замыкания конечных множеств - это в точности компактные элементы множества C замкнутых множеств. Отсюда следует, что C - алгебраическое уп . Поскольку C также является решеткой, в этом контексте ее часто называют алгебраической решеткой. Наоборот, если C - алгебраическое ч.у., то оператор замыкания финитен.
Каждый оператор замыкания на конечном множестве S однозначно определяется своими образами его псевдозамкнутых множеств. [5] Они определены рекурсивно: множество является псевдозамкнутым, если оно не замкнуто, и содержит замыкание каждого из своих псевдозамкнутых собственных подмножеств. Формально: P ⊆ S псевдозамкнуто тогда и только тогда, когда
- P ≠ cl ( P ) и
- если Q ⊂ P является псевдо-замкнут, то сл ( Q ) ⊆ P .
Операторы замыкания на частично упорядоченных множествах
Частично упорядоченное множество (ч.у.м.) представляет собой набор вместе с частичным порядком ≤, т.е. бинарное отношение , которое рефлексивно ( ≤ с ), переходной ( ≤ б ≤ C означает на ≤ C ) и антисимметричные ( ≤ B ≤ следует a = b ). Любое мощное множество P ( S ) вместе с включением ⊆ является частично упорядоченным множеством.
Функция сл: P → P из частичного порядка P в себя называется оператором замыкания , если он удовлетворяет следующие аксиомы для всех элементов х , у в Р .
х ≤ cl ( х ) (cl является обширным ) x ≤ y влечет cl ( x ) ≤ cl ( y ) (cl увеличивается ) cl (cl ( x )) = cl ( x ) (cl идемпотентно )
Доступны более сжатые альтернативы: приведенное выше определение эквивалентно единственной аксиоме
- x ≤ cl ( y ) тогда и только тогда, когда cl ( x ) ≤ cl ( y )
для всех х , у в Р .
Используя точечный порядок функций между множествами, можно в качестве альтернативы записать свойство экстенсивности как id P ≤ cl, где id - функция идентичности . Самостоятельно карта к , что растет и идемпотентный, но удовлетворяет двойное свойство экстенсивности, то есть к ≤ идентификатор Р называются оператором ядра , [6] оператором интерьер , [7] или двойным замыканием . [8] В качестве примера, если A является подмножеством множества B , то отображение себя на powerset множества B, заданное как μ A ( X ) = A ∪ X, является оператором замыкания, тогда как λ A ( X ) = A ∩ X - оператор ядра. Функция потолка от действительных чисел к действительным числам, которая присваивает каждому действительному x наименьшее целое число не меньше x , является еще одним примером оператора замыкания.
Fixpoint функции п, т.е. элемента с из Р , который удовлетворяет сл ( с ) = с , называется закрытым элементом . Оператор замыкания на частично упорядоченном множестве определяется его замкнутыми элементами. Если c - замкнутый элемент, то x ≤ c и cl ( x ) ≤ c - эквивалентные условия.
Каждое соединение Галуа (или остаточное отображение ) порождает закрывающий оператор (как объясняется в этой статье). Фактически, каждый оператор замыкания возникает таким образом из подходящей связности Галуа. [9] Связность Галуа не определяется однозначно с помощью оператора замыкания. Одна связность Галуа, которая порождает оператор замыкания cl, может быть описана следующим образом: если A - множество замкнутых элементов относительно cl, то cl: P → A - нижний сопряженный элемент связи Галуа между P и A , причем верхний сопряженный быть вложения A в P . Более того, каждый нижний сопряженный элемент вложения некоторого подмножества в P является оператором замыкания. «Операторы замыкания - это нижние сопряжения вложений». Однако обратите внимание, что не каждое вложение имеет нижний сопряженный элемент.
Любое частично упорядоченное множество P можно рассматривать как категорию с единственным морфизмом от x до y тогда и только тогда, когда x ≤ y . Операторы замыкания на частично упорядоченное множество P не то иное, как монады по категории Р . Эквивалентно, оператор замыкания можно рассматривать как эндофунктор в категории частично упорядоченных множеств, обладающих дополнительными идемпотентными и обширными свойствами.
Если P - полная решетка , то подмножество A в P является набором замкнутых элементов для некоторого оператора замыкания на P тогда и только тогда, когда A является семейством Мура на P , т. Е. Наибольший элемент P находится в A , а нижняя грань (встречаются) любого непустого подмножества A снова в A . Любой такой набор A сам по себе является полной решеткой с порядком, унаследованным от P (но операция супремума (соединения) может отличаться от таковой для P ). Когда P является Powerset Булева алгебра из множества X , то семейство Мур на Р называется системой замыкания на X .
Операторы замыкания на P образуют полную решетку; порядок на операторов замыкания определяется сл 1 ≤ сл 2 тогда и только тогда сл 1 ( х ) ≤ сл 2 ( х ) для всех х в Р .
Смотрите также
- Čech оператор закрытия
- Связь Галуа
- Внутренняя алгебра
- Аксиомы замыкания Куратовского
- Замыкание (топология) и Интерьер (топология)
Заметки
- ^ Блит стр.11
- ^ Марсель Эрне , Замыкание , в Фредерик Минар, Эллиотт Перл (редакторы), Вне топологии , Современная математика, т. 486, Американское математическое общество, 2009.
- ^ Клиффорд Бергман, Универсальная алгебра , 2012, раздел 2.4.
- ^ Гантер, Алгоритм 1
- ^ Гантер, Раздел 3.2
- ^ Giertz, стр. 26 год
- ^ Эрне, стр. 2, использует закрывающую (или внутреннюю) операцию
- ^ Блит, стр. 10
- ^ Блит, стр. 10
Рекомендации
- Гаррет Биркгоф . 1967 (1940). Теория решеток, 3-е изд . Американское математическое общество.
- Беррис, Стэнли Н. и HP Sankappanavar (1981) Курс универсальной алгебры Springer-Verlag. ISBN 3-540-90578-2 Бесплатная онлайн-версия .
- Браун Д. Д. и Сушко Р. (1973) "Абстрактная логика", Математические диссертации 102-9-42.
- Кастеллини, Г. (2003) Операторы категориального замыкания . Бостон Массачусетс: Birkhaeuser.
- Эдельман, Пол Х. (1980) Встречно-распределительные решетки и анти-обменное замыкание, Algebra Universalis 10: 290-299.
- Гантер, Бернхард и Обьедков, Сергей (2016) Концептуальные исследования . Спрингер, ISBN 978-3-662-49290-1 .
- Герла, Г. (2000) Нечеткая логика: математические инструменты для приближенного рассуждения . Kluwer Academic Publishers .
- Ллойд, JW (1987) Основы логического программирования . Springer-Verlag .
- Тарский, Альфред (1983) «Основные концепции методологии дедуктивных наук» в логике, семантике, метаматематике . Hackett (изд. 1956 г., Oxford University Press ).
- Альфред Тарский (1956) Логика, семантика и метаматематика . Издательство Оксфордского университета .
- Уорд, Морган (1942) "Операторы замыкания решетки", Annals of Mathematics 43: 191-96.
- Г. Гирц, К. Х. Хофманн, К. Кеймель, Дж. Д. Лоусон, М. Мислав, Д. С. Скотт: Непрерывные решетки и домены , Cambridge University Press, 2003
- Т. С. Блит, Решетки и упорядоченные алгебраические структуры , Springer, 2005, ISBN 1-85233-905-5 .
- М. Эрне, Дж. Кословски, А. Мелтон, Г. Е. Стрекер, Букварь по связям Галуа , в: Материалы Летней конференции 1991 г. по общей топологии и приложениям в честь Мэри Эллен Рудин и ее работ, Анналы Нью-Йоркской академии наук, Vol. 704, 1993, с. 103–125. Доступно в Интернете в различных форматах файлов: PS.GZ PS
Внешние ссылки
- Стэнфордская энциклопедия философии : « Алгебраическая логика высказываний» - Рамон Янсана.