Оператор закрытия
В математике оператор замыкания множества S — это функция из степенного набора S в себя , который удовлетворяет следующим условиям для всех наборов
(cl обширен ), (cl увеличивается ), (cl идемпотент ).
Операторы замыкания определяются своими замкнутыми множествами , т. е. множествами вида cl( X ), поскольку замыкание cl( X ) множества X есть наименьшее замкнутое множество, X. содержащее Такие семейства «замкнутых множеств» иногда называют системами замыкания или « семействами Мура ». [1] Множество вместе с оператором замыкания на нем иногда называют пространством замыкания . Операторы замыкания также называются « операторами оболочки », что позволяет избежать путаницы с «операторами замыкания», изучаемыми в топологии .
История
[ редактировать ]Э. Х. Мур изучал операторы замыкания в своем «Введении в одну из форм общего анализа» 1910 года , тогда как концепция замыкания подмножества возникла в работах Фриджеса Рисса в связи с топологическими пространствами. [2] Хотя идея закрытия в то время не была формализована, она возникла в конце 19 века благодаря заметному вкладу Эрнста Шредера , Рихарда Дедекинда и Георга Кантора . [3]
Примеры
[ редактировать ]Обычное замыкание множества из топологии является оператором замыкания. Другие примеры включают линейную оболочку подмножества векторного пространства , выпуклую или аффинную оболочку подмножества векторного пространства или нижнюю полунепрерывную оболочку. функции , где например, нормированное пространство , определенное неявно , где это эпиграф функции .
Относительный интерьер не является оператором замыкания: хотя он идемпотентен, но не возрастает, и если это куб в и является одним из его лиц, то , но и , поэтому оно не увеличивается. [4]
В топологии операторы замыкания — это топологического операторы замыкания , которые должны удовлетворять
для всех (Обратите внимание, что для это дает ).
В алгебре и логике многие операторы замыкания являются операторами финитного замыкания , т. е. они удовлетворяют условиям
В теории частично упорядоченных множеств , которая важна для теоретической информатики , операторы замыкания имеют более общее определение, которое заменяет с . (См . § Операторы замыкания на частично упорядоченных множествах .)
Операторы замыкания в топологии
[ редактировать ]Топологическое замыкание подмножества X топологического пространства всех точек y пространства, таких, что каждая окрестность y X содержит точку состоит из . Функция, которая сопоставляет каждому подмножеству X его замыкание, является оператором топологического замыкания. И наоборот, каждый оператор топологического замыкания на множестве порождает топологическое пространство, замкнутые множества которого являются в точности замкнутыми множествами относительно оператора замыкания.
Операторы замыкания в алгебре
[ редактировать ]Операторы финитного замыкания играют относительно заметную роль в универсальной алгебре , и в этом контексте их традиционно называют операторами алгебраического замыкания . Каждое подмножество алгебры порождает подалгебру : . наименьшую подалгебру, содержащую это множество Это приводит к появлению оператора финитного замыкания.
Возможно, самым известным примером этого является функция, которая сопоставляет каждому подмножеству данного векторного пространства его линейный интервал . Аналогично, функция, которая сопоставляет каждому подмножеству данной группы полей порожденную ею подгруппу, и аналогично для и всех других типов алгебраических структур .
Линейная оболочка в векторном пространстве и аналогичное алгебраическое замыкание в поле удовлетворяют свойству обмена: если x находится в замыкании объединения A и { y }, но не в замыкании A , то y находится в замыкании объединения A и { x }. Оператор финитного замыкания, обладающий этим свойством, называется матроидом . Размерность степень векторного пространства или трансцендентности поля (над его простым полем ) равна в точности рангу соответствующего матроида.
Функция, которая отображает каждое подмножество данного поля в его алгебраическое замыкание , также является оператором финитного замыкания и в целом отличается от оператора, упомянутого ранее. Операторы финитного замыкания, которые обобщают эти два оператора, изучаются в теории моделей как dcl (для определимого замыкания ) и acl (для алгебраического замыкания ).
Выпуклая оболочка в n -мерном евклидовом пространстве является еще одним примером оператора финитного замыкания. Он удовлетворяет свойству антиобмена: если x находится в замыкании объединения { y } и A , но не в объединении { y } и замыкании A , то y не входит в замыкание объединения { х } А. и Операторы финитного замыкания с этим свойством порождают антиматроиды .
Другой пример оператора замыкания, используемого в алгебре: если некоторая алгебра имеет универсум A и X представляет собой набор пар A , то оператор, присваивающий X наименьшее сравнение, содержащее X, является оператором финитного замыкания на A x A . [5]
Операторы замыкания в логике
[ редактировать ]Предположим, у вас есть некий логический формализм , содержащий определенные правила, позволяющие выводить новые формулы из заданных. Рассмотрим множество F всех возможных формул, и пусть P — степеней набор F , упорядоченный по ⊆. Для набора X формул пусть cl( X ) будет набором всех формул, которые могут быть получены из X . оператор замыкания на P. Тогда cl — Точнее, мы можем получить cl следующим образом. Назовем «непрерывным» оператор J такой, что для направленного класса T каждого
- J (lim Т ) знак равно Lim J ( Т ).
Это условие непрерывности основано на теореме о неподвижной точке для 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 ).
Учитывая оператор финитного замыкания на множестве, замыкания конечных множеств являются в точности компактными элементами множества C замкнутых множеств. Отсюда следует, что C — алгебраическое ЧУМ .Поскольку C также является решеткой, в этом контексте ее часто называют алгебраической решеткой. И наоборот, если C — алгебраическое ЧУМ, то оператор замыкания финитирен.
Псевдозамкнутые множества
[ редактировать ]Каждый оператор замыкания на конечном множестве S однозначно определяется своими образами своих псевдозамкнутых множеств. [7] Они определяются рекурсивно: Множество является псевдозамкнутым, если оно не замкнуто и содержит замыкание каждого из своих собственных псевдозамкнутых подмножеств. Формально: P ⊆ S псевдозамкнуто тогда и только тогда, когда
- P ≠ cl( P ) и
- если Q ⊂ P псевдозамкнуто, то cl( Q ) ⊆ P .
Операторы замыкания на частично упорядоченных множествах
[ редактировать ]Частично упорядоченный набор (poset) — это набор вместе с частичным порядком ≤, т.е. бинарное отношение , которое является рефлексивным ( a ≤ a ), транзитивным ( a ≤ b ≤ c подразумевает a ≤ c ) и антисимметричным ( a ≤ b ≤ a подразумевает а = б ). Каждое степенное множество P ( S ) вместе с включением ⊆ является частично упорядоченным множеством.
Функция cl: P → P из частичного порядка P в себя называется оператором замыкания, если она удовлетворяет следующим аксиомам для всех x , y в P. элементов
х ≤ кл( х ) (cl обширен ) x ≤ y подразумевает cl( x ) ≤ cl( y ) (cl увеличивается ) кл(кл( х )) = кл( х ) (cl идемпотент )
Доступны более сжатые альтернативы: приведенное выше определение эквивалентно единственной аксиоме.
- 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 — степенная булева алгебра множества X , то семейство Мура на P называется замыкания на X. системой
Операторы замыкания на P сами образуют полную решетку; порядок операторов замыкания определяется как cl 1 ≤ cl 2 тогда и только тогда, когда cl 1 ( x ) ≤ cl 2 ( x ) для всех x в P .
См. также
[ редактировать ]- Оператор закрытия Čech – Оператор закрытия.
- Замыкание (топология) - все точки и предельные точки в подмножестве топологического пространства.
- Связь Галуа - Особое соответствие между двумя частично упорядоченными множествами.
- Внутренняя алгебра - Алгебраическая структура
- Интерьер (топология) - наибольшее открытое подмножество некоторого заданного набора.
- Аксиомы замыкания Куратовского - математическая концепция.
- Оператор предварительного закрытия – Оператор закрытия
Примечания
[ редактировать ]- ^ Диатта, Жан (14 ноября 2009 г.). «О критических множествах конечного семейства Мура» . Достижения в области анализа и классификации данных . 3 (3): 291–304. дои : 10.1007/s11634-009-0053-8 . ISSN 1862-5355 . S2CID 26138007 .
- ^ Блит , с. 11.
- ^ Марсель Эрне , Закрытие , Фредерик Минар, Эллиот Перл (Редакторы), Beyond Topology , Современная математика, том. 486, Американское математическое общество, 2009.
- ^ Рокафеллар, Ральф Тайрелл (1970). Выпуклый анализ . Издательство Принстонского университета. п. 44. дои : 10.1515/9781400873173 . ISBN 9781400873173 .
- ^ Клиффорд Бергман, Универсальная алгебра , 2012, Раздел 2.4.
- ^ Гантер, Алгоритм 1
- ^ Гантер, Раздел 3.2
- ^ Гирц, с. 26
- ^ Эрне, с. 2, используется операция закрытия (соответственно внутренняя)
- ^ Блит, с. 10
- ^ Блит, с. 10
Ссылки
[ редактировать ]- Гаррет Биркгоф . 1967 (1940). Теория решеток, 3-е изд . Американское математическое общество.
- Беррис, Стэнли Н. и HP Санкаппанавар (1981) Курс универсальной алгебры Springer-Verlag. ISBN 3-540-90578-2 Бесплатное онлайн-издание .
- Браун, DJ и Сушко, Р. (1973) «Абстрактная логика», Mathematical Dissertations 102-9-42.
- Кастеллини, Г. (2003) Операторы категориального замыкания . Бостон, Массачусетс: Биркхойзер.
- Эдельман, Пол Х. (1980) Дистрибутивные решетки и антиобменное замыкание, Algebra Universalis 10: 290-299.
- Гантер, Бернхард и Объедков, Сергей (2016) Концептуальное исследование . джемпер, ISBN 978-3-662-49290-1 .
- Герла, Г. (2000) Нечеткая логика: математические инструменты для приближенного рассуждения . Академическое издательство Kluwer .
- Ллойд, JW (1987) Основы логического программирования . Спрингер-Верлаг .
- Тарский, Альфред (1983) «Фундаментальные концепции методологии дедуктивных наук» в логике, семантике, метаматематике . Хакетт (изд. 1956 г., Oxford University Press ).
- Альфред Тарский (1956) Логика, семантика и метаматематика . Издательство Оксфордского университета .
- Уорд, Морган (1942) «Операторы замыкания решетки», Annals of Mathematics 43: 191–96.
- Г. Гирц, К. Х. Хофманн, К. Кеймел, Дж. Д. Лоусон, М. Мислов, Д. С. Скотт: непрерывные решетки и области , издательство Кембриджского университета, 2003 г.
- Т. С. Блит, Решетки и упорядоченные алгебраические структуры , Springer, 2005, ISBN 1-85233-905-5 .
- М. Эрне, Дж. Козловски, А. Мелтон, Дж. Э. Стрекер, Букварь по связям Галуа , в: Материалы летней конференции 1991 года по общей топологии и приложениям в честь Мэри Эллен Рудин и ее работ, Анналы Нью-Йоркской академии. наук, Vol. 704, 1993, стр. 103–125. Доступно онлайн в различных форматах файлов: PS.GZ PS.
Внешние ссылки
[ редактировать ]- Стэнфордская энциклопедия философии : « Алгебраическая логика высказываний » — Рамон Джансана.